結果
問題 | No.1227 I hate ThREE |
ユーザー | 37zigen |
提出日時 | 2020-07-28 21:49:01 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 526 ms / 2,000 ms |
コード長 | 4,367 bytes |
コンパイル時間 | 3,475 ms |
コンパイル使用メモリ | 77,676 KB |
実行使用メモリ | 268,036 KB |
最終ジャッジ日時 | 2023-08-30 14:24:00 |
合計ジャッジ時間 | 18,832 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 248 ms
264,412 KB |
testcase_01 | AC | 250 ms
264,324 KB |
testcase_02 | AC | 242 ms
264,200 KB |
testcase_03 | AC | 435 ms
267,672 KB |
testcase_04 | AC | 403 ms
266,712 KB |
testcase_05 | AC | 348 ms
267,556 KB |
testcase_06 | AC | 201 ms
259,404 KB |
testcase_07 | AC | 197 ms
259,456 KB |
testcase_08 | AC | 320 ms
267,084 KB |
testcase_09 | AC | 321 ms
264,868 KB |
testcase_10 | AC | 308 ms
264,428 KB |
testcase_11 | AC | 411 ms
267,468 KB |
testcase_12 | AC | 427 ms
267,744 KB |
testcase_13 | AC | 297 ms
264,940 KB |
testcase_14 | AC | 361 ms
265,336 KB |
testcase_15 | AC | 464 ms
268,036 KB |
testcase_16 | AC | 496 ms
267,420 KB |
testcase_17 | AC | 456 ms
267,392 KB |
testcase_18 | AC | 426 ms
266,664 KB |
testcase_19 | AC | 406 ms
265,452 KB |
testcase_20 | AC | 507 ms
267,680 KB |
testcase_21 | AC | 289 ms
264,536 KB |
testcase_22 | AC | 408 ms
267,368 KB |
testcase_23 | AC | 474 ms
267,008 KB |
testcase_24 | AC | 526 ms
266,696 KB |
testcase_25 | AC | 448 ms
267,348 KB |
testcase_26 | AC | 446 ms
266,988 KB |
testcase_27 | AC | 459 ms
266,596 KB |
testcase_28 | AC | 426 ms
267,440 KB |
testcase_29 | AC | 456 ms
266,952 KB |
testcase_30 | AC | 458 ms
266,576 KB |
testcase_31 | AC | 449 ms
266,392 KB |
testcase_32 | AC | 468 ms
266,556 KB |
testcase_33 | AC | 426 ms
265,704 KB |
testcase_34 | AC | 456 ms
266,680 KB |
testcase_35 | AC | 449 ms
266,976 KB |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.util.ArrayList; import java.util.Arrays; import java.util.NoSuchElementException; class DJSet { int n; int[] upper; public DJSet(int n_) { n=n_; upper=new int[n]; Arrays.fill(upper, -1); } int root(int x) { return upper[x]<0?x:(upper[x]=root(upper[x])); } boolean equiv(int x,int y) { return root(x)==root(y); } void setUnion(int x,int y) { x=root(x); y=root(y); if (x==y) return; if (upper[x]<upper[y]) { x^=y;y^=x;x^=y; } upper[y]+=upper[x]; upper[x]=y; } } public class Main { public static void main(String[] args) { new Main().run(); } long pow(long a,long n) { long ret=1; for (;n>0;n>>=1,a=a*a%MOD) if (n%2==1) ret=ret*a%MOD; return ret; } void dfs(int cur,int par,ArrayList<Integer>[] g,long C) { for (int curc=1;curc<dp[cur].length;++curc) { dp[cur][curc]=1; } for (int dst:g[cur]) { if (dst==par) continue; dfs(dst,cur,g,C); for (int curc=1;curc<dp[cur].length;++curc) { long sum=0; for (int d=-3;d<=3;d+=6) { int nextc=curc+d; if (nextc<1||nextc>C||nextc>=dp[dst].length) continue; sum+=dp[dst][nextc]; sum%=MOD; } dp[cur][curc]*=sum; dp[cur][curc]%=MOD; } } } final long MOD=(long)1e9+7; int MAXN=3000; long[][] dp=new long[MAXN][3*MAXN+1]; void run() { FastScanner sc=new FastScanner(); int N=sc.nextInt(); DJSet ds=new DJSet(N); assert(2<=N&&N<=1000); long C=sc.nextInt(); assert(4<=C&&C<=1e9); int[] a=new int[N-1]; int[] b=new int[N-1]; ArrayList<Integer>[] g=new ArrayList[N]; for (int i=0;i<N;++i) g[i]=new ArrayList<>(); for (int i=0;i<N-1;++i) { a[i]=sc.nextInt()-1; b[i]=sc.nextInt()-1; g[a[i]].add(b[i]); g[b[i]].add(a[i]); assert(0<=a[i]&&a[i]<=N-1); assert(0<=b[i]&&b[i]<=N-1); assert(!ds.equiv(a[i], b[i])); ds.setUnion(a[i], b[i]); } if (C<=6000) { dfs(0,-1,g,C); long ans=0; for (int c=1;c<=C;++c) { ans=(ans+dp[0][c])%MOD; } System.out.println(ans); } else { dfs(0,-1,g,C); long s=0; for (int c=1;c<=3000;++c) { s=(s+dp[0][c])%MOD; } long ans=2*s+(C-6000)%MOD*pow(2,N-1)%MOD; ans=(ans%MOD+MOD)%MOD; System.out.println(ans); } } void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));} class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; }else{ ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;} private boolean isPrintableChar(int c) { return 33 <= c && c <= 126;} private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;} public boolean hasNext() { skipUnprintable(); return hasNextByte();} public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while(isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while(true){ if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; }else if(b == -1 || !isPrintableChar(b)){ return minus ? -n : n; }else{ throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { return (int)nextLong(); } } }