結果

問題 No.916 Encounter On A Tree
コンテスト
ユーザー ntuda
提出日時 2025-11-29 10:50:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 67 ms / 2,000 ms
コード長 1,204 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,636 KB
実行使用メモリ 77,208 KB
最終ジャッジ日時 2025-11-29 10:50:22
合計ジャッジ時間 5,781 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 56
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

d, l, r, k = map(int, input().split())

# N = int(input())
# C = list(map(int,input().split()))
N = (1 << d)
MOD = 10 ** 9 + 7
fact = [1] * (N + 1)
rfact = [1] * (N + 1)
r0 = 1
for i in range(1, N + 1):
    fact[i] = r0 = r0 * i % MOD
rfact[N] = r0 = pow(fact[N], -1, MOD)
for i in range(N, 0, -1):
    rfact[i - 1] = r0 = r0 * i % MOD
def comb(x,y):
    return fact[x] * rfact[x-y] * rfact[y]

dl = l.bit_length() - 1
dr = r.bit_length() - 1
if dl > dr:
    dl, dr = dr, dl
if k < abs(dr - dl):
    print(0)
    exit()
if k > abs(dl + dr):
    print(0)
    exit()
if (dl + dr - k) % 2 == 1:
    print(0)
    exit()
dm = (dl + dr - k) // 2

ans = 1
for i in range(d):
    ans *= fact[1 << i]
    ans %= MOD
if dl != dr:
    ans *= pow(1 << dl, -1, MOD)
    ans %= MOD
    ans *= pow(1 << dr, -1, MOD)
    ans %= MOD
    ans *= (1 << dm)
    ans %= MOD
    ans *= (1 << (dr - dm))
    ans %= MOD
    if dl != dm:
        ans *= (1 << (dl - dm) - 1)
        ans %= MOD
    print(ans)
else:
    a = 1 << dl
    ans *= pow(a, -1, MOD)
    ans %= MOD
    ans *= pow(a-1, -1, MOD)
    ans %= MOD
    ans *= (1 << dm)
    ans %= MOD
    b = 1<< (dl - dm - 1)
    ans *= 2 * b ** 2
    ans %= MOD
    print(ans)
0