Submission #2210213
Source Code Expand
//package com.company; import java.io.*; import java.lang.reflect.Array; import java.math.BigInteger; import java.util.*; public class Main { static long TIME_START, TIME_END; public static void main(String[] args) throws IOException { MyScanner sc = new MyScanner(System.in); // MyScanner sc = new MyScanner(new FileInputStream("Test.in")); PrintWriter pw = new PrintWriter(System.out); // PrintWriter pw = new PrintWriter(new FileOutputStream("Test.out")); TIME_START = System.currentTimeMillis(); Task.solve(sc, pw); TIME_END = System.currentTimeMillis(); // pw.println("Time used: " + (TIME_END - TIME_START) + "."); pw.close(); } public static class Task { static final int MOD = 1000000007; static long[][] dp; static long[] fact; static long[] invfact; static int N, A, B, C, D; public static void solve(MyScanner sc, PrintWriter pw) throws IOException { N = sc.nextInt(); A = sc.nextInt(); B = sc.nextInt(); C = sc.nextInt(); D = sc.nextInt(); precompute(); dp = new long[2][N + 1]; dp[(A - 1) % 2][0] = 1; for (int i = A; i <= B; i++) { int cutI = i % 2; int prevI = (i - 1) % 2; for (int j = C; j <= D; j++) { int count = i * j; if (count > N) break; long subChoose = fact[count] * pow(invfact[i], j) % MOD * invfact[j] % MOD; for (int k = count; k <= N; k++) { long choose = fact[k] * invfact[count] % MOD * invfact[k - count] % MOD; long add = dp[prevI][k - count] * subChoose % MOD * choose % MOD; dp[cutI][k] += add; if (dp[cutI][k] >= MOD) dp[cutI][k] -= MOD; } } for (int j = 0; j <= N; j++) { dp[cutI][j] += dp[prevI][j]; if (dp[cutI][j] >= MOD) dp[cutI][j] -= MOD; } Arrays.fill(dp[prevI], 0); } pw.println(dp[B % 2][N]); } public static long pow(long a, int b) { if (b == 0) return 1; if ((b & 1) == 0) return pow(a * a % MOD, b >> 1); return (a * pow(a * a % MOD, b >> 1) % MOD); } public static void precompute(){ fact = new long[1001]; invfact = new long[1001]; fact[0] = 1; invfact[0] = (int)pow(1, MOD - 2); for (int i = 1; i < 1001; i++) { fact[i] = i * fact[i - 1]; fact[i] %= MOD; invfact[i] = (int) pow(fact[i], MOD - 2); } } } static class MyScanner { StringTokenizer st; BufferedReader br; public MyScanner(InputStream s){ br = new BufferedReader(new InputStreamReader(s));} public MyScanner(FileReader s) throws FileNotFoundException {br = new BufferedReader(s);} public String next() throws IOException { while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine()); return st.nextToken(); } public int nextInt() throws IOException {return Integer.parseInt(next());} public long nextLong() throws IOException {return Long.parseLong(next());} public String nextLine() throws IOException {return br.readLine();} public double nextDouble() throws IOException { return Double.parseDouble(next()); } public boolean ready() throws IOException {return br.ready();} } }
Submission Info
Submission Time | |
---|---|
Task | E - Grouping |
User | zihanw |
Language | Java8 (OpenJDK 1.8.0) |
Score | 600 |
Code Size | 3887 Byte |
Status | AC |
Exec Time | 222 ms |
Memory | 22864 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_many_01.txt, subtask_1_many_02.txt, subtask_1_many_03.txt, subtask_1_many_04.txt, subtask_1_max_01.txt, subtask_1_max_02.txt, subtask_1_min_01.txt, subtask_1_randa_01.txt, subtask_1_randa_02.txt, subtask_1_randb_01.txt, subtask_1_randb_02.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 72 ms | 19028 KB |
sample_02.txt | AC | 74 ms | 20948 KB |
sample_03.txt | AC | 222 ms | 19304 KB |
sample_04.txt | AC | 73 ms | 21460 KB |
subtask_1_many_01.txt | AC | 216 ms | 20944 KB |
subtask_1_many_02.txt | AC | 204 ms | 20688 KB |
subtask_1_many_03.txt | AC | 206 ms | 22864 KB |
subtask_1_many_04.txt | AC | 207 ms | 22224 KB |
subtask_1_max_01.txt | AC | 111 ms | 20532 KB |
subtask_1_max_02.txt | AC | 93 ms | 18516 KB |
subtask_1_min_01.txt | AC | 72 ms | 21460 KB |
subtask_1_randa_01.txt | AC | 100 ms | 20652 KB |
subtask_1_randa_02.txt | AC | 74 ms | 19028 KB |
subtask_1_randb_01.txt | AC | 93 ms | 19796 KB |
subtask_1_randb_02.txt | AC | 77 ms | 21076 KB |