結果
| 問題 | No.916 Encounter On A Tree |
| ユーザー |
 Jiro_tech15
|
| 提出日時 | 2019-10-25 22:04:39 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 2,613 bytes |
| コンパイル時間 | 747 ms |
| コンパイル使用メモリ | 90,232 KB |
| 実行使用メモリ | 1,636,000 KB |
| 最終ジャッジ日時 | 2024-09-13 03:52:45 |
| 合計ジャッジ時間 | 5,225 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | MLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
ソースコード
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(1e18+1)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()
const int N = (int)3e5;
ll mpow(ll a, ll b){
if(b==0) return 1;
else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
else return mpow(a,b-1) * a % MOD;
}
ll lpow(ll a, ll b){
if(b==0) return 1;
else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;}
else return lpow(a,b-1) * a;
}
ll gcd(ll a, ll b){
if(b==0) return a;
else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
if(kaijo_memo.size() > n) return kaijo_memo[n];
if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
return kaijo_memo[n];
}
vector<ll> gyaku_kaijo_memo;
ll gyaku_kaijo(ll n){
if(gyaku_kaijo_memo.size() > n) return gyaku_kaijo_memo[n];
if(gyaku_kaijo_memo.size() == 0) gyaku_kaijo_memo.push_back(1);
while(gyaku_kaijo_memo.size() <= n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1] * mpow(gyaku_kaijo_memo.size(), MOD-2) % MOD);
return gyaku_kaijo_memo[n];
}
ll nCr(ll n, ll r){
if(n == r) return 1;//0個の丸と-1個の棒みたいな時に時に効く？不安.
if(n < r || r < 0) return 0;
ll ret = 1;
ret *= kaijo(n); ret %= MOD;
ret *= gyaku_kaijo(r); ret %= MOD;
ret *= gyaku_kaijo(n-r); ret %= MOD;
return ret;
}
ll log_2(ll a){
ll ret = 0;
while(lpow(2,ret) <= a) ret++;
ret--;
return ret;
}
int main(void){
ll d,l,r,k;cin>>d>>l>>r>>k;
ll hl = (ll)log_2(l);
ll hr = (ll)log_2(r);
if((hl+hr-k+1000000)%2 == 1){
cout<<0<<endl;
return 0;
}
ll hp = (hl+hr-k)/2;
if(hp < 0){
cout<<0<<endl;
return 0;
}
ll ans = 1;
ans *= mpow(2, hp);
ans *= mpow(2, hl-hp);
ans %= MOD;
ans *= mpow(2, hr-hp-1);
ans %= MOD;
rep(h, d){
reps(kai,mpow(2,h) - (hl==h?1:0) - (hr==h?1:0)){
ans *= kai;
ans %= MOD;
}
ans %= MOD;
}
cout<<ans<<endl;
return 0;
}