結果
問題 | No.1227 I hate ThREE |
ユーザー | uni_python |
提出日時 | 2020-09-13 14:30:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 390 ms / 2,000 ms |
コード長 | 2,452 bytes |
コンパイル時間 | 294 ms |
コンパイル使用メモリ | 87,088 KB |
実行使用メモリ | 124,148 KB |
最終ジャッジ日時 | 2023-09-03 13:12:58 |
合計ジャッジ時間 | 12,936 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 178 ms
80,704 KB |
testcase_01 | AC | 171 ms
80,788 KB |
testcase_02 | AC | 181 ms
80,856 KB |
testcase_03 | AC | 213 ms
83,924 KB |
testcase_04 | AC | 214 ms
84,016 KB |
testcase_05 | AC | 212 ms
84,016 KB |
testcase_06 | AC | 177 ms
80,800 KB |
testcase_07 | AC | 174 ms
80,996 KB |
testcase_08 | AC | 208 ms
83,100 KB |
testcase_09 | AC | 200 ms
82,980 KB |
testcase_10 | AC | 191 ms
82,892 KB |
testcase_11 | AC | 359 ms
124,148 KB |
testcase_12 | AC | 374 ms
123,932 KB |
testcase_13 | AC | 183 ms
83,120 KB |
testcase_14 | AC | 197 ms
83,012 KB |
testcase_15 | AC | 207 ms
83,592 KB |
testcase_16 | AC | 264 ms
101,512 KB |
testcase_17 | AC | 218 ms
83,464 KB |
testcase_18 | AC | 294 ms
101,268 KB |
testcase_19 | AC | 275 ms
101,600 KB |
testcase_20 | AC | 310 ms
98,972 KB |
testcase_21 | AC | 180 ms
82,124 KB |
testcase_22 | AC | 279 ms
101,428 KB |
testcase_23 | AC | 381 ms
121,416 KB |
testcase_24 | AC | 386 ms
121,936 KB |
testcase_25 | AC | 389 ms
121,600 KB |
testcase_26 | AC | 376 ms
119,488 KB |
testcase_27 | AC | 390 ms
121,588 KB |
testcase_28 | AC | 386 ms
120,552 KB |
testcase_29 | AC | 386 ms
121,548 KB |
testcase_30 | AC | 379 ms
121,688 KB |
testcase_31 | AC | 377 ms
121,684 KB |
testcase_32 | AC | 389 ms
121,264 KB |
testcase_33 | AC | 378 ms
120,848 KB |
testcase_34 | AC | 378 ms
121,176 KB |
testcase_35 | AC | 365 ms
119,684 KB |
ソースコード
import sys input=sys.stdin.readline def I(): return int(input()) def MI(): return map(int, input().split()) def LI(): return list(map(int, input().split())) """ 根からスタートして+3 or -3 して根まで行きたい,その中で制約を満たさなきゃダメ(1<=p<=C) N<=1000なので,全部+3とかしても高々+3000しか行かない. ひとまず制約無視,根を0に固定して(2^(N-1)通り) 最大値,最小値をそれぞれで考えてダメなものを外す?...微妙 木dpとかしたい.O(NC)だけど,Cが大きく根の値が中途半端な時は全通り(=2^(N-1))可能か 根が3N以下ならC=6Nとみなして計算できる """ def main(): mod=10**9+7 N,C=MI() adj=[[]for _ in range(N)] for _ in range(N-1): a,b=MI() a-=1 b-=1 adj[a].append(b) adj[b].append(a) ch=[[]for _ in range(N)] P=[-1]*N import queue q=queue.Queue() q.put((0,-1)) L=[] # bfsで見る順 while not q.empty(): v,p=q.get() L.append(v) for nv in adj[v]: if nv!=p: ch[v].append(nv) P[nv]=v q.put((nv,v)) L=L[::-1] # dpで見る順 def calc_X(X,flag): # 制約が1~X dp=[[1]*X for _ in range(N)] # dp[i][j]はi番目の頂点の値がjであるとき,此の頂点を根とした部分木の通り数 for v in L: p=P[v] if p==-1: continue for j in range(X): temp=0 if j+3<X: temp+=dp[v][j+3] if j-3>=0: temp+=dp[v][j-3] dp[p][j]*=temp dp[p][j]%=mod ans=0 if flag==0: for j in range(X): ans=(ans+dp[0][j])%mod else: for j in range(3*N): ans=(ans+dp[0][j])%mod # for i in range(N): # print(dp[i]) return ans if C<=6*N: ans=calc_X(C,0) print(ans) else: temp=calc_X(6*N,1) rem=C-6*N temp2=pow(2,N-1,mod) ans= (temp*2 + temp2*rem)%mod print(ans) main()