Submission #1519703
Source Code Expand
//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
ll dp[1010][1010], comb[1010][1010], fact[1010], ifact[1010];
//二分累乗法 xのe乗
ll binpow(ll x, ll e) {
ll a = 1, p = x;
while(e > 0) {
if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
else {a = (a*p) % MOD; e--;}
}
return a % MOD;
}
void pascalTriangle(int n) {
REP(i, n) {
comb[i][0] = 1;
comb[i][i] = 1;
FOR(j, 1, i) comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;
}
}
void initFact(int n) {
fact[0] = fact[1] = 1;
ifact[1] = 1;
FOR(i, 2, n) {
fact[i] = (fact[i-1] * i) % MOD;
ifact[i] = binpow(fact[i], MOD-2);
}
}
ll P(ll n, int r) {
return fact[n]*binpow(fact[n-r], MOD-2)%MOD;
}
signed main(void)
{
int n, a, b, c, d;
cin >> n >> a >> b >> c >> d;
fact[0] = 1;
for(int i = 1; i <= n; i++) {
fact[i] = (fact[i-1] * i) % MOD;
}
dp[a-1][0] = 1;
for(int i = a; i <= b; i++) {
for(int j = 0; j <= n; j++) dp[i][j] = dp[i-1][j];
for(int k = c; k <= d; k++) {
for(int j = i * k; j <= n; j++) {
dp[i][j] = (dp[i][j] + (dp[i-1][j-i*k] * P(j,i*k) % MOD) * binpow(binpow(fact[i],k) * fact[k] % MOD, MOD-2) % MOD) % MOD;
}
}
}
cout << dp[b][n] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Grouping |
User |
ferin_tech |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
2041 Byte |
Status |
AC |
Exec Time |
1091 ms |
Memory |
9984 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 |
2 ms |
2304 KB |
sample_02.txt |
AC |
2 ms |
2304 KB |
sample_03.txt |
AC |
1091 ms |
9984 KB |
sample_04.txt |
AC |
2 ms |
2304 KB |
subtask_1_many_01.txt |
AC |
799 ms |
4352 KB |
subtask_1_many_02.txt |
AC |
682 ms |
9472 KB |
subtask_1_many_03.txt |
AC |
799 ms |
4352 KB |
subtask_1_many_04.txt |
AC |
801 ms |
6400 KB |
subtask_1_max_01.txt |
AC |
12 ms |
3200 KB |
subtask_1_max_02.txt |
AC |
8 ms |
2304 KB |
subtask_1_min_01.txt |
AC |
2 ms |
2304 KB |
subtask_1_randa_01.txt |
AC |
2 ms |
4352 KB |
subtask_1_randa_02.txt |
AC |
2 ms |
4352 KB |
subtask_1_randb_01.txt |
AC |
3 ms |
4352 KB |
subtask_1_randb_02.txt |
AC |
4 ms |
2304 KB |