// "Say:He is the Most Merciful,We have believed in him and upon him we have relied" [67:29]
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int ncr[351][351];
int dp[351][351][2];
int n;
void fillncr(int n){
ncr[0][0] = 1;
for(int i=1; i<=n; i++){
for(int j=0; j<=n; j++){
if(j > i)ncr[i][j] = 0;
else if(j == i || j == 0)ncr[i][j] = 1;
else ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j])%mod;
}
}
}
int f(int persons, int tasks, int is_valid){
if(persons == n){
return (is_valid | (tasks == persons));
}
if(tasks == 0){
return is_valid;
}
if(dp[persons][tasks][is_valid] != -1)return dp[persons][tasks][is_valid];
int ways = 0;
for(int i=0; i<=tasks; i++){
ways += f(persons+1, tasks-i, is_valid|(persons == i)) * ncr[tasks][i];
ways %= mod;
}
return dp[persons][tasks][is_valid] = ways % mod;
}
signed main(){
memset(dp, -1, sizeof dp);
fillncr(350);
cin >> n;
int val = f(1, n, 0);
cout << val << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 7 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 8 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 9 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 11 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 12 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 13 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 14 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 15 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 16 |
Correct |
2 ms |
3148 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 4 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 7 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 8 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 9 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 11 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 12 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 13 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 14 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 15 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 16 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 17 |
Correct |
160 ms |
3184 KB |
Output is correct |
| 18 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 19 |
Correct |
35 ms |
3148 KB |
Output is correct |
| 20 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 21 |
Correct |
215 ms |
3184 KB |
Output is correct |
| 22 |
Correct |
27 ms |
3188 KB |
Output is correct |
| 23 |
Correct |
4 ms |
3188 KB |
Output is correct |
| 24 |
Correct |
46 ms |
3192 KB |
Output is correct |
| 25 |
Correct |
31 ms |
3192 KB |
Output is correct |
| 26 |
Correct |
67 ms |
3192 KB |
Output is correct |
| 27 |
Correct |
295 ms |
3192 KB |
Output is correct |
| 28 |
Correct |
302 ms |
3184 KB |
Output is correct |
| 29 |
Correct |
311 ms |
3200 KB |
Output is correct |
| 30 |
Correct |
307 ms |
3188 KB |
Output is correct |
| 31 |
Correct |
311 ms |
3204 KB |
Output is correct |
| 32 |
Correct |
311 ms |
3188 KB |
Output is correct |
| 33 |
Correct |
313 ms |
3200 KB |
Output is correct |
| 34 |
Correct |
317 ms |
3268 KB |
Output is correct |
| 35 |
Correct |
324 ms |
3268 KB |
Output is correct |
| 36 |
Correct |
325 ms |
3268 KB |
Output is correct |
| 37 |
Correct |
330 ms |
3192 KB |
Output is correct |
