#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long
const int N = 351;
int n, dp[N][N][2], C[N][N], mod = 1e9 + 7;
int solve(int idx, int s, bool b){
if(idx == n + 1) return s == 0 && b;
int &ret = dp[idx][s][b];
if(ret != -1) return ret;
ret = 0;
for(int i = 0 ; i <= s ; i++){
ret = (ret + 1LL * C[s][i] * solve(idx + 1, s - i, b | (i == idx))) % mod;
}
return ret;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(dp, -1, sizeof dp);
C[0][0] = 1;
for(int i = 1 ; i < N ; i++){
C[i][0] = 1;
for(int j = 1 ; j < N ; j++){
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
if(C[i][j] >= mod) C[i][j] -= mod;
}
}
cin >> n;
cout << solve(1, n, 0) << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1656 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1656 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1788 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1788 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 9 |
Correct |
7 ms |
1784 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 11 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 12 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1788 KB |
Output is correct |
| 14 |
Correct |
6 ms |
1788 KB |
Output is correct |
| 15 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 16 |
Correct |
6 ms |
1784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1656 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1788 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1788 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 9 |
Correct |
7 ms |
1784 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 11 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 12 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1788 KB |
Output is correct |
| 14 |
Correct |
6 ms |
1788 KB |
Output is correct |
| 15 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 16 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 17 |
Correct |
305 ms |
1784 KB |
Output is correct |
| 18 |
Correct |
8 ms |
1784 KB |
Output is correct |
| 19 |
Correct |
70 ms |
1784 KB |
Output is correct |
| 20 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 21 |
Correct |
403 ms |
1912 KB |
Output is correct |
| 22 |
Correct |
50 ms |
1912 KB |
Output is correct |
| 23 |
Correct |
9 ms |
1784 KB |
Output is correct |
| 24 |
Correct |
88 ms |
1784 KB |
Output is correct |
| 25 |
Correct |
61 ms |
1784 KB |
Output is correct |
| 26 |
Correct |
118 ms |
1716 KB |
Output is correct |
| 27 |
Correct |
583 ms |
1912 KB |
Output is correct |
| 28 |
Correct |
573 ms |
1784 KB |
Output is correct |
| 29 |
Correct |
580 ms |
1912 KB |
Output is correct |
| 30 |
Correct |
596 ms |
1916 KB |
Output is correct |
| 31 |
Correct |
602 ms |
1912 KB |
Output is correct |
| 32 |
Correct |
600 ms |
1912 KB |
Output is correct |
| 33 |
Correct |
610 ms |
1784 KB |
Output is correct |
| 34 |
Correct |
617 ms |
1912 KB |
Output is correct |
| 35 |
Correct |
611 ms |
1784 KB |
Output is correct |
| 36 |
Correct |
628 ms |
1912 KB |
Output is correct |
| 37 |
Correct |
648 ms |
1784 KB |
Output is correct |
