Submission #2239701
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<vector<lli>> mat;
typedef vector<unordered_map<lli,lli>> graph;
const lli mod = 1000000007;
lli n,a,b,c,d;
mat dp;
lli factorial(lli n){
static lli dp[100000];
if(dp[n]) return dp[n];
if(n == 0) return dp[n] = 1;
return dp[n] = (n*factorial(n-1))%mod;
}
lli pow(lli x,lli r,lli mod = 1000000007){
lli ret = 1;
for(;r != 0;r >>= 1){
if(r&1 != 0) ret *= x,ret %= mod;
x *= x,x %= mod;
}
return ret;
}
lli exeuclid(lli a,lli aa,lli x,lli xx,lli y,lli yy){
lli q;
if(a == 0) return aa > 0 ? xx : -xx;
q = aa / a;
return exeuclid(aa - q * a,a,xx - q * x,x,yy - q * y,y);
}
lli inverse(lli x){
return (exeuclid(mod,x,0,1,1,0) + mod) % mod;
}
int main(){
cin >> n >> a >> b >> c >> d;
dp = mat(n+1,vll(n+1));
dp[0][0] = 1;
for(lli i = 1;i <= n;i++){
for(lli j = 0;j <= n;j++){
dp[i][j] = dp[i-1][j];
if(i < a || i > b) continue;
for(lli k = c;k <= d;k++){
if(j-i*k < 0) break;
lli x = dp[i-1][j-i*k];
x = (x*factorial(j))%mod;
x = (x*inverse(factorial(k)))%mod;
x = (x*inverse(pow(factorial(i),k)))%mod;
x = (x*inverse(factorial(j-i*k)))%mod;
dp[i][j] += x;
}
dp[i][j] %= mod;
}
}
cout << dp[n][n] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Grouping |
User |
deoxy |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1462 Byte |
Status |
TLE |
Exec Time |
2104 ms |
Memory |
10112 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 |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
TLE |
2104 ms |
8064 KB |
sample_04.txt |
AC |
1 ms |
256 KB |
subtask_1_many_01.txt |
AC |
1953 ms |
8064 KB |
subtask_1_many_02.txt |
AC |
1705 ms |
10112 KB |
subtask_1_many_03.txt |
AC |
1958 ms |
8064 KB |
subtask_1_many_04.txt |
AC |
1966 ms |
8064 KB |
subtask_1_max_01.txt |
AC |
26 ms |
8192 KB |
subtask_1_max_02.txt |
AC |
19 ms |
8192 KB |
subtask_1_min_01.txt |
AC |
1 ms |
256 KB |
subtask_1_randa_01.txt |
AC |
3 ms |
2432 KB |
subtask_1_randa_02.txt |
AC |
1 ms |
256 KB |
subtask_1_randb_01.txt |
AC |
7 ms |
4992 KB |
subtask_1_randb_02.txt |
AC |
6 ms |
384 KB |