結果
問題 | No.916 Encounter On A Tree |
ユーザー |
![]() |
提出日時 | 2019-10-25 22:35:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 932 bytes |
コンパイル時間 | 1,537 ms |
コンパイル使用メモリ | 169,352 KB |
実行使用メモリ | 11,488 KB |
最終ジャッジ日時 | 2024-09-13 04:52:42 |
合計ジャッジ時間 | 3,212 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 56 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:16:5: warning: 'dr' may be used uninitialized [-Wmaybe-uninitialized] 16 | if(dl > dr) swap(dl, dr); | ^~ main.cpp:11:12: note: 'dr' was declared here 11 | ll dl, dr; | ^~ main.cpp:16:5: warning: 'dl' may be used uninitialized [-Wmaybe-uninitialized] 16 | if(dl > dr) swap(dl, dr); | ^~ main.cpp:11:8: note: 'dl' was declared here 11 | ll dl, dr; | ^~
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long int ll;constexpr int INF = INT_MAX;constexpr ll MOD = ll(1e9) + 7;int main() {ll D, L, R, K;cin >> D >> L >> R >> K;ll dl, dr;for(int i=0;i<D;i++){if(L >= (1<<i) && L < (1<<(i+1))) dl = i+1;if(R >= (1<<i) && R < (1<<(i+1))) dr = i+1;}if(dl > dr) swap(dl, dr);ll lca = (dl+dr-K)/2;if(abs(dl-dr)%2 != K%2 || abs(dl-dr) > K || lca <= 0){cout << 0 << endl;return 0;}vector<ll> fact(1<<D);fact[0] = 1;for(ll i=1;i<=1<<D;i++){fact[i] = fact[i-1]*i%MOD;}ll ans = ((1LL<<max(dl-lca-1,0LL))%MOD)*((1LL<<max(dr-lca-1,0LL))%MOD) %MOD *((1LL<<(lca-1))*2%MOD) %MOD;for(int i=1;i<=D;i++){ll x = 1LL<<(i-1);if(i == dl) x--;if(i == dr) x--;ans *= fact[x];ans %= MOD;}cout << ans << endl;return 0;}