結果

問題 No.916 Encounter On A Tree
コンテスト
ユーザー kurimupy
提出日時 2020-06-18 14:26:05
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,135 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 81 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 61,184 KB
最終ジャッジ日時 2024-07-03 12:49:41
合計ジャッジ時間 37,691 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4 WA * 1
other AC * 38 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

d, l, r, k = map(int, input().split())
mod = 10**9 + 7
depthl = 0
depthr = 0
for i in range(30):
    if 2**i <= l < 2**(i+1):
        depthl = i+1

for i in range(30):
    if 2**i <= r < 2**(i+1):
        depthr = i+1
ans = 0
power = [1 for i in range(10**6*2)]
for i in range(1, 10**6+10**5):
    power[i] = power[i-1]*i
    power[i] %= mod

for i in range(1, d+1):
    # lcaの高さを固定
    lca = i
    res = 2*pow(2, lca-1, mod)
    if depthl+depthr-2*lca != k:
        continue
    if depthl < lca:
        continue
    if lca < depthl:
        res = res*pow(2, depthl-lca-1, mod)*pow(2, depthr-lca-1, mod)
        D = {depth: 2**(depth-1) for depth in range(1, d+1)}
        D[depthr] -= 1
        D[depthl] -= 1
        D[lca] -= 1
        for depth in D.keys():
            res *= power[D[depth]]
            res %= mod
    elif lca == depthl:
        res *= pow(2, depthr-lca-1, mod)
        D = {depth: 2**(depth-1) for depth in range(1, d+1)}
        D[depthr] -= 1
        D[lca] -= 1
        for depth in D.keys():
            res *= power[D[depth]]
            res %= mod
    ans += res
    ans %= mod
print(ans%mod)
0