#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
const ll MX = 351;
ll n;
ll dp[MX][MX][2], nr_dp[MX][MX];
ll nCr(ll N, ll R) {
if (R == 1) return N;
if (N == R || R == 0) return 1;
ll &res = nr_dp[N][R];
if (res != -1) return res;
res = nCr(N-1, R) + nCr(N-1, R-1);
res %= mod;
return res;
}
ll Calc(ll pos, ll rem, bool happy) {
if (pos > n) {
return (happy && rem == 0);
}
ll &res = dp[pos][rem][happy];
if (res != -1) return res;
res = 0;
for (ll i = 0; i <= rem; ++i) {
res += nCr(rem, i) * Calc(pos+1, rem-i, happy | (pos==i));
res %= mod;
}
return res;
}
int main() {
memset(dp, -1, sizeof dp);
memset(nr_dp, -1, sizeof nr_dp);
cin >> n;
cout << Calc(1, n, 0) << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
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 |
2 ms |
3116 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3188 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
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 |
2 ms |
3116 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3188 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 |
3184 KB |
Output is correct |
| 9 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 11 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 12 |
Correct |
2 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 |
3188 KB |
Output is correct |
| 16 |
Correct |
2 ms |
3148 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
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 |
2 ms |
3116 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3188 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 |
3184 KB |
Output is correct |
| 9 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 10 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 11 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 12 |
Correct |
2 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 |
3188 KB |
Output is correct |
| 16 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 17 |
Correct |
271 ms |
3196 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3148 KB |
Output is correct |
| 19 |
Correct |
55 ms |
3192 KB |
Output is correct |
| 20 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 21 |
Correct |
332 ms |
3204 KB |
Output is correct |
| 22 |
Correct |
38 ms |
3184 KB |
Output is correct |
| 23 |
Correct |
5 ms |
3148 KB |
Output is correct |
| 24 |
Correct |
71 ms |
3184 KB |
Output is correct |
| 25 |
Correct |
53 ms |
3148 KB |
Output is correct |
| 26 |
Correct |
96 ms |
3192 KB |
Output is correct |
| 27 |
Correct |
475 ms |
3204 KB |
Output is correct |
| 28 |
Correct |
472 ms |
3204 KB |
Output is correct |
| 29 |
Correct |
475 ms |
3148 KB |
Output is correct |
| 30 |
Correct |
479 ms |
3208 KB |
Output is correct |
| 31 |
Correct |
493 ms |
3208 KB |
Output is correct |
| 32 |
Correct |
487 ms |
3208 KB |
Output is correct |
| 33 |
Correct |
494 ms |
3308 KB |
Output is correct |
| 34 |
Correct |
505 ms |
3204 KB |
Output is correct |
| 35 |
Correct |
507 ms |
3148 KB |
Output is correct |
| 36 |
Correct |
507 ms |
3208 KB |
Output is correct |
| 37 |
Correct |
508 ms |
3204 KB |
Output is correct |
