Submission #2237266
Source Code Expand
import java.util.*; import java.io.*; class Main { static long [][] c = new long [2002][2002]; static long [] fac = new long [2002]; static final int mod = 924844033; static long [][] dp = new long [2][6002]; public static void main (String[] args) { Reader in = new Reader(); int n = in.nextInt(); int k = in.nextInt(); fac[0] = 1; for(int i = 1; i <= n; i++) { fac[i] = fac[i - 1] * i; fac[i] %= mod; } for(int i = 0; i <= n; i++) { c[i][0] = 1; for(int j = 1; j <= i; j++) { c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; c[i][j] %= mod; } } ArrayList <Integer> chain = new ArrayList <> (); for(int i = 1; i <= k; i++) { int sz = 0; int cur = i; while(cur <= n) { ++sz; cur += k; } chain.add(sz); chain.add(sz); } dp[0][0] = 1; int row = 0; for(int i = 1; i <= chain.size(); i++) { int sz = chain.get(i - 1); row ^= 1; for(int j = 0; j <= n; j++) { dp[row][j] = 0; for(int x = 0; x <= Math.min(j, sz); x++) { dp[row][j] += dp[row ^ 1][j - x] * c[sz - x][x]; dp[row][j] %= mod; } } } long ans = 0; for(int i = 0; i <= n; i++) { if(i % 2 == 1) { ans -= fac[n - i] * dp[row][i]; } else { ans += fac[n - i] * dp[row][i]; } ans %= mod; } if(ans < 0) ans += mod; System.out.println(ans); } static class Reader { private BufferedReader a; private StringTokenizer b; Reader() { a = new BufferedReader (new InputStreamReader (System.in)); } public String next () { while(b == null || !b.hasMoreTokens()) { try { b = new StringTokenizer (a.readLine()); } catch (IOException e) { e.printStackTrace(); } } return b.nextToken(); } public int nextInt () { return Integer.parseInt(next()); } public long nextLong () { return Long.parseLong(next()); } public double nextDouble () { return Double.parseDouble(next()); } public String nextLine () { try { return a.readLine(); } catch (IOException e) { e.printStackTrace (); } return "##"; } } }
Submission Info
Submission Time | |
---|---|
Task | D - ~K Perm Counting |
User | tasmeemreza |
Language | Java7 (OpenJDK 1.7.0) |
Score | 900 |
Code Size | 2191 Byte |
Status | AC |
Exec Time | 240 ms |
Memory | 88804 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 900 / 900 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2, example3, example4 |
All | example0, example1, example2, example3, example4, handmade0, handmade1, handmade2, handmade3, handmade4, handmade5, handmade6, maxrand0, maxrand1, maxrand2, maxrand3, maxrand4, rand0, rand1, rand2, rand3, rand4, small0, small1, small2, supersmall0, supersmall1, supersmall2 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
example0 | AC | 104 ms | 81492 KB |
example1 | AC | 106 ms | 85332 KB |
example2 | AC | 106 ms | 83156 KB |
example3 | AC | 106 ms | 85332 KB |
example4 | AC | 142 ms | 84856 KB |
handmade0 | AC | 105 ms | 81364 KB |
handmade1 | AC | 173 ms | 82784 KB |
handmade2 | AC | 240 ms | 86524 KB |
handmade3 | AC | 171 ms | 82876 KB |
handmade4 | AC | 226 ms | 82812 KB |
handmade5 | AC | 183 ms | 82800 KB |
handmade6 | AC | 185 ms | 82768 KB |
maxrand0 | AC | 220 ms | 84860 KB |
maxrand1 | AC | 196 ms | 82808 KB |
maxrand2 | AC | 196 ms | 82808 KB |
maxrand3 | AC | 180 ms | 84464 KB |
maxrand4 | AC | 229 ms | 84372 KB |
rand0 | AC | 199 ms | 88804 KB |
rand1 | AC | 147 ms | 86908 KB |
rand2 | AC | 154 ms | 82812 KB |
rand3 | AC | 123 ms | 82004 KB |
rand4 | AC | 215 ms | 82940 KB |
small0 | AC | 139 ms | 84752 KB |
small1 | AC | 140 ms | 85384 KB |
small2 | AC | 174 ms | 83932 KB |
supersmall0 | AC | 105 ms | 83284 KB |
supersmall1 | AC | 106 ms | 79572 KB |
supersmall2 | AC | 106 ms | 81364 KB |