結果
問題 | No.916 Encounter On A Tree |
ユーザー |
![]() |
提出日時 | 2019-10-25 22:52:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,779 bytes |
コンパイル時間 | 723 ms |
コンパイル使用メモリ | 74,836 KB |
最終ジャッジ日時 | 2025-01-08 01:33:59 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 41 WA * 15 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:92:8: warning: ‘dl’ may be used uninitialized [-Wmaybe-uninitialized] 92 | ll d = dl-dr; | ^ main.cpp:82:16: note: ‘dl’ was declared here 82 | ll D,L,R,K,dl,dr; | ^~ main.cpp:92:8: warning: ‘dr’ may be used uninitialized [-Wmaybe-uninitialized] 92 | ll d = dl-dr; | ^ main.cpp:82:19: note: ‘dr’ was declared here 82 | ll D,L,R,K,dl,dr; | ^~
ソースコード
#include <iostream> #include <vector> using namespace std; typedef long long ll; const ll mod = 1e9+7; struct mint { ll x; mint(ll x=0):x((x%mod+mod)%mod){} mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint a) const { mint res(*this); return res+=a; } mint operator-(const mint a) const { mint res(*this); return res-=a; } mint operator*(const mint a) const { mint res(*this); return res*=a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod-2); } mint& operator/=(const mint a) { return (*this) *= a.inv(); } mint operator/(const mint a) const { mint res(*this); return res/=a; } }; class combination{ private: vector<mint> fact,finv; public: combination(int N){ fact = finv = vector<mint>(N+1); fact[0] = fact[1] = 1; finv[0] = finv[1] = 1; for(ll i=2;i<=N;i++){ fact[i] = fact[i-1]*i; finv[i] = fact[i].inv(); } } mint f(int i){ return fact[i]; } mint comb(int n,int k){ if(n<k) return 0; if(n<0 || k<0) return 0; return fact[n]*finv[k]*finv[n-k]; } mint hcomb(int n,int k){ if(n==0 && k==0) return 1; return comb(n+k-1,k); } }; int main(){ ll D,L,R,K,dl,dr; cin >> D >> L >> R >> K; if(L<R) swap(L,R); for(int i=0;i<D;i++){ int mi = (1<<i),ma = (1<<(i+1))-1; if(mi<=L && L<=ma) dl = i; if(mi<=R && R<=ma) dr = i; } vector<mint> fact(1<<D,1); for(ll i=1;i<(1<<D);i++) fact[i] = fact[i-1]*i; ll d = dl-dr; //cerr << dl << " " << dr << endl; if(d!=0 && d<K){ cout << 0 << endl; return 0; } K -= d; if(K%2){ cout << 0 << endl; return 0; } if(2*dr<K){ cout << 0 << endl; return 0; } K /= 2; ll cnt; if(K==0) cnt = 1; else cnt = (1<<K)-(1<<(K-1)); mint ans = 1; //cerr << dl << " " << dr << " " << cnt << endl; for(int i=0;i<D;i++){ if(i==dr){ mint p; if(dr==0) p = 1; else if(dr!=dl) p = fact[(1<<dr)-1]; else p = fact[(1<<dr)-2]*(1<<dl); ans *= p*cnt; }else ans *= fact[1<<i]; } cout << ans.x << endl; }