結果
問題 | No.612 Move on grid |
ユーザー | 夕叢霧香(ゆうむらきりか) |
提出日時 | 2017-12-12 10:40:31 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,390 ms / 2,500 ms |
コード長 | 4,226 bytes |
コンパイル時間 | 2,253 ms |
コンパイル使用メモリ | 74,828 KB |
実行使用メモリ | 58,612 KB |
最終ジャッジ日時 | 2023-08-20 22:17:09 |
合計ジャッジ時間 | 15,926 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 53 ms
51,152 KB |
testcase_01 | AC | 53 ms
49,112 KB |
testcase_02 | AC | 52 ms
49,148 KB |
testcase_03 | AC | 105 ms
52,816 KB |
testcase_04 | AC | 1,356 ms
58,140 KB |
testcase_05 | AC | 1,390 ms
56,048 KB |
testcase_06 | AC | 1,368 ms
58,388 KB |
testcase_07 | AC | 1,357 ms
58,308 KB |
testcase_08 | AC | 1,115 ms
58,292 KB |
testcase_09 | AC | 137 ms
58,196 KB |
testcase_10 | AC | 350 ms
53,800 KB |
testcase_11 | AC | 116 ms
53,000 KB |
testcase_12 | AC | 576 ms
55,940 KB |
testcase_13 | AC | 146 ms
53,112 KB |
testcase_14 | AC | 884 ms
55,848 KB |
testcase_15 | AC | 106 ms
52,992 KB |
testcase_16 | AC | 803 ms
58,052 KB |
testcase_17 | AC | 216 ms
53,104 KB |
testcase_18 | AC | 720 ms
55,744 KB |
testcase_19 | AC | 505 ms
55,812 KB |
testcase_20 | AC | 1,088 ms
58,612 KB |
ソースコード
import java.io.*; import java.util.*; class Main { static final long MOD=1000000007; static final int N=2000; static long[] fact; static long[] invfact; static void initialize() { fact = new long[N]; invfact = new long[N]; fact[0] = invfact[0] = 1; for (int i = 1; i < N; ++i) { fact[i] = (i * fact[i - 1]) % MOD; invfact[i] = powerMod(fact[i], MOD - 2); } } static long powerMod(long x, long exponent) { long prod = 1; for (int i = 63; i >= 0; --i) { prod = (prod * prod) % MOD; if ((exponent & 1L << i) != 0) { prod = (prod * x) % MOD; } } return prod; } static long comb(int x, int y) { if (x < 0) { return 0; } if (y < 0 || y > x) { return 0; } long r= fact[x] * ((invfact[x - y] * invfact[y]) % MOD) % MOD; return r; } public static void main(String[] args) { MyScanner sc = new MyScanner(); out = new PrintWriter(new BufferedOutputStream(System.out)); int t=sc.nextInt(); int[] a=new int[3]; for(int i=0;i<3;++i)a[i]=sc.nextInt(); int d=sc.nextInt(); int e=sc.nextInt(); if(a[2]<0){ for(int i=0;i<3;++i)a[i]=-a[i]; int tmp=d; d=-e; e=-tmp; } initialize(); long[][]prec=new long[t+1][2*t+2]; for(int i=0;i<=t;++i){ for(int z=-t;z<=t;++z){ int az=Math.abs(z); if((az+i)%2!=0)continue; int j=(i-z)/2; prec[i][z+t+1]=j>=0&&j+z>=0?invfact[j]*invfact[j+z]%MOD:0; } for(int j=0;j<2*t+1;++j) prec[i][j+1]=(prec[i][j+1]+prec[i][j])%MOD; } long wa=0; for(int x=-t;x<=t;++x){ int ax=Math.abs(x); int tx=t-ax; for(int y=-tx;y<=tx;++y){ int ay=Math.abs(y); int ty=tx-ay; int zMin=-ty,zMax=ty; if(a[2]!=0){ zMin=Math.max(zMin,(d-a[0]*x-a[1]*y+100000*a[2]+a[2]-1)/a[2]-100000); zMax=Math.min(zMax,(e-a[0]*x-a[1]*y+100000*a[2])/a[2]-100000); }else if(d-a[0]*x-a[1]*y>0||e-a[0]*x-a[1]*y<0) continue; if(zMin>zMax)continue; //System.err.println("x = "+x+" y = "+y); //System.err.println("zMin = "+zMin+" zMax = "+zMax); //System.err.println(Arrays.toString(d2)); long tmp=0; for(int i=ax+ay;i<=t;i+=2){ long adden=prec[t-i][t+zMax+1]-prec[t-i][t+zMin]+MOD; adden%=MOD; long d2=comb(i,(i-ax-ay)/2)*comb(i,(i-ax+ay)/2)%MOD; d2=d2*invfact[i]%MOD; adden=adden*d2%MOD; tmp=(tmp+adden)%MOD; } wa=(wa+tmp)%MOD; } } out.println(wa*fact[t]%MOD); out.close(); } // http://codeforces.com/blog/entry/7018 //-----------PrintWriter for faster output--------------------------------- public static PrintWriter out; //-----------MyScanner class for faster input---------- public static class MyScanner { BufferedReader br; StringTokenizer st; public MyScanner() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine(){ String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } } }