Submission #826400
Source Code Expand
import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.StringTokenizer; import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class Main { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); PrintWriter out = new PrintWriter(outputStream); TaskF solver = new TaskF(); solver.solve(1, in, out); out.close(); } static class TaskF { static final long MODULO = (long) (1e9 + 7); public void solve(int testNumber, InputReader in, PrintWriter out) { int n = in.nextInt(); int k = in.nextInt(); if (k == 1) { out.println(1); return; } long[] invs = new long[k + 1]; invs[1] = 1; for (int i = 2; i < invs.length; ++i) { invs[i] = (MODULO - (MODULO / i) * invs[((int) (MODULO % i))] % MODULO) % MODULO; } long invProd = 1; for (int i = 1; i <= k - 2; ++i) { invProd = invProd * invs[i] % MODULO; } long[] ways = new long[]{1}; long[] sufProds = new long[k - 1]; for (int i = 1; i < n; ++i) { long[] nways = new long[ways.length + 1]; long sum = 0; long prefProd = 1; int upto = Integer.MIN_VALUE; for (int newZ = nways.length; newZ >= 1; --newZ) { if (newZ > 1) { sum += ways[newZ - 2]; sum %= MODULO; } int need = (i + 1) * k - newZ - 1; if (upto < (need - (k - 2))) { upto = need; sufProds[0] = 1; for (int j = 1; j < sufProds.length; ++j) { sufProds[j] = sufProds[j - 1] * (upto - j + 1) % MODULO; } prefProd = 1; } else { prefProd *= need; prefProd %= MODULO; } nways[newZ - 1] = (nways[newZ - 1] + sum * prefProd % MODULO * sufProds[upto - (need - (k - 2))] % MODULO * invProd % MODULO) % MODULO; } ways = nways; } long res = 0; for (long x : ways) res += x; res %= MODULO; for (int i = 1; i <= n; ++i) { res = res * i % MODULO; } out.println(res); } } static class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } } }
Submission Info
Submission Time | |
---|---|
Task | F - Leftmost Ball |
User | Petr |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1600 |
Code Size | 3772 Byte |
Status | AC |
Exec Time | 331 ms |
Memory | 18032 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 | 152 ms | 8148 KB |
0_01.txt | AC | 155 ms | 8272 KB |
0_02.txt | AC | 151 ms | 8148 KB |
0_03.txt | AC | 315 ms | 17904 KB |
1_00.txt | AC | 149 ms | 8148 KB |
1_01.txt | AC | 155 ms | 8148 KB |
1_02.txt | AC | 152 ms | 8148 KB |
1_03.txt | AC | 323 ms | 18032 KB |
1_04.txt | AC | 327 ms | 18028 KB |
1_05.txt | AC | 331 ms | 18020 KB |
1_06.txt | AC | 315 ms | 17456 KB |
1_07.txt | AC | 320 ms | 17532 KB |
1_08.txt | AC | 319 ms | 17544 KB |
1_09.txt | AC | 303 ms | 17192 KB |
1_10.txt | AC | 315 ms | 17648 KB |
1_11.txt | AC | 311 ms | 17316 KB |
1_12.txt | AC | 222 ms | 10544 KB |
1_13.txt | AC | 303 ms | 17648 KB |
1_14.txt | AC | 175 ms | 8788 KB |
1_15.txt | AC | 247 ms | 12944 KB |
1_16.txt | AC | 264 ms | 15612 KB |
1_17.txt | AC | 285 ms | 17060 KB |
1_18.txt | AC | 181 ms | 9300 KB |
1_19.txt | AC | 323 ms | 17628 KB |