Submission #1219936
Source Code Expand
#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <vector> #include <queue> #include <set> #include <map> #include <cmath> using namespace std; #define int long long typedef pair<int, int> P; #define rep(i, n) for (int i=0; i<(n); i++) #define all(c) (c).begin(), (c).end() #define uniq(c) c.erase(unique(all(c)), (c).end()) #define _1 first #define _2 second #define pb push_back #define INF 1145141919 #define MOD 1000000007 int N, A, B, C, D; int dp[1001][1001]; int fact[1001]; int factinv[1001]; int comb[1001][1001]; int modpow(int x, int k) { int a = 1; while (k > 0) { if (k & 1) a = (1LL*a*x) % MOD; x = (1LL*x*x) % MOD; k >>= 1; } return a; } int inv(int x) { return modpow(x, MOD-2); } int nCr(int n, int k) { if (n < 0 || k < 0 || n < k) return 0; return (1LL * fact[n] * inv((1LL*fact[k]*fact[n-k]) % MOD)) % MOD; } int f(int x, int n) { if (dp[x][n] != -1) return dp[x][n]; if (n == 0) return dp[x][n] = 1; if (x < A) return dp[x][n] = 0; long long s = 0; s += f(x-1, n); long long y = 1, yn = n; for (int k=C; k<=D; k++) { if (n-k*x < 0) break; y = (1LL * y * comb[yn][x]) % MOD; yn -= x; long long b = (1LL * y * factinv[k]) % MOD; s = (s + 1LL * b * f(x-1, n-k*x)) % MOD; } return dp[x][n] = s; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> N >> A >> B >> C >> D; fact[0] = 1; factinv[0] = 1; for (int i=1; i<=N; i++) { fact[i] = (1LL*i*fact[i-1]) % MOD; factinv[i] = inv(fact[i]); } for (int i=0; i<=1000; i++) { for (int j=0; j<=1000; j++) { dp[i][j] = -1; comb[i][j] = nCr(i, j); } } cout << f(B, N) << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Grouping |
User | funcsr |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1800 Byte |
Status | WA |
Exec Time | 122 ms |
Memory | 16000 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 84 ms | 15872 KB |
sample_02.txt | AC | 84 ms | 15872 KB |
sample_03.txt | AC | 122 ms | 16000 KB |
sample_04.txt | AC | 84 ms | 15872 KB |
subtask_1_many_01.txt | AC | 108 ms | 15872 KB |
subtask_1_many_02.txt | WA | 99 ms | 16000 KB |
subtask_1_many_03.txt | WA | 106 ms | 16000 KB |
subtask_1_many_04.txt | WA | 103 ms | 16000 KB |
subtask_1_max_01.txt | AC | 84 ms | 16000 KB |
subtask_1_max_02.txt | AC | 84 ms | 15872 KB |
subtask_1_min_01.txt | AC | 84 ms | 15872 KB |
subtask_1_randa_01.txt | AC | 84 ms | 16000 KB |
subtask_1_randa_02.txt | AC | 84 ms | 15872 KB |
subtask_1_randb_01.txt | AC | 84 ms | 16000 KB |
subtask_1_randb_02.txt | AC | 84 ms | 16000 KB |