Submission #1046664
Source Code Expand
using System; using System.Text; using System.Collections.Generic; class Solve{ public Solve(){} StringBuilder sb; public static int Main(){ new Solve().Run(); return 0; } void Run(){ sb = new StringBuilder(); Calc(); Console.Write(sb.ToString()); } void Calc(){ string[] str = Console.ReadLine().Split(' '); int N = int.Parse(str[0]); int K = int.Parse(str[1]); if(K == 1){ sb.Append("1\n"); return; } Fact F = new Fact(N*K); long[,] dp = new long[N+1,N+1]; for(int i=0;i<N+1;i++){ dp[i,0] = 1; for(int j=1;j<=i;j++){ int L = N*K - i - j*(K-1) + K-1; dp[i,j] = ((dp[i,j-1]*F.GetConv(L-1,K-2)%Define.mod)+dp[i-1,j])%Define.mod; } } sb.Append((dp[N,N]*F.GetFact(N)%Define.mod)+"\n"); } } class Fact{ public long[] f; public long[] rf; public Fact(int N){ f = new long[N+1]; rf = new long[N+1]; for(int i=0;i<N+1;i++){ if(i == 0){ f[i] = 1; } else{ f[i] = (f[i-1]*i)%Define.mod; } } for(int i=N;i>=0;i--){ if(i == N){ rf[i] = pow(f[N],Define.mod-2); } else{ rf[i] = rf[i+1]*(i+1)%Define.mod; } } } public long pow(long N,long K){ if(K == 0){ return 1; } else if(K % 2 == 0){ long t = pow(N,K/2); return t*t%Define.mod; } else{ return N*pow(N,K-1)%Define.mod; } } public long GetFact(int N){ return f[N]; } public long GetConv(int N,int R){ return ((f[N]*rf[R])%Define.mod*rf[N-R])%Define.mod; } } public static class Define{ public const long mod = 1000000007; }
Submission Info
Submission Time | |
---|---|
Task | F - Leftmost Ball |
User | leign |
Language | C# (Mono 4.6.2.0) |
Score | 1600 |
Code Size | 2048 Byte |
Status | AC |
Exec Time | 478 ms |
Memory | 87760 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1600 / 1600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | AC | 21 ms | 2648 KB |
0_01.txt | AC | 20 ms | 2648 KB |
0_02.txt | AC | 21 ms | 2648 KB |
0_03.txt | AC | 478 ms | 87760 KB |
1_00.txt | AC | 20 ms | 2648 KB |
1_01.txt | AC | 21 ms | 2648 KB |
1_02.txt | AC | 20 ms | 2648 KB |
1_03.txt | AC | 477 ms | 87760 KB |
1_04.txt | AC | 454 ms | 82768 KB |
1_05.txt | AC | 469 ms | 85200 KB |
1_06.txt | AC | 466 ms | 85968 KB |
1_07.txt | AC | 441 ms | 81232 KB |
1_08.txt | AC | 424 ms | 81744 KB |
1_09.txt | AC | 451 ms | 83916 KB |
1_10.txt | AC | 443 ms | 81872 KB |
1_11.txt | AC | 466 ms | 85968 KB |
1_12.txt | AC | 88 ms | 20184 KB |
1_13.txt | AC | 391 ms | 73936 KB |
1_14.txt | AC | 27 ms | 4568 KB |
1_15.txt | AC | 117 ms | 24280 KB |
1_16.txt | AC | 201 ms | 40152 KB |
1_17.txt | AC | 348 ms | 60232 KB |
1_18.txt | AC | 32 ms | 5464 KB |
1_19.txt | AC | 452 ms | 86224 KB |