#include <bits/stdc++.h>
#define sz(c) int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
#define fore(c,...) for (auto __VA_ARGS__:(c))
using namespace std;
typedef long long ll;
int const MD=1000000007;
int madd(int x,int y) {
if (x+y<MD) return x+y; else return x+y-MD;
}
void minc(int &x,int y) {
x+=y;
if (x>=MD) x-=MD;
}
int mmul(int x,int y) {
return int(ll(x)*y % MD);
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
cout<<fixed<<setprecision(10);
int N;
cin>>N;
vector<vector<int>> comb(N+1,vector<int>(N+1));
rep(i,0,N+1) {
comb[i][0]=1;
rep(j,1,i+1) comb[i][j]=madd(comb[i-1][j],comb[i-1][j-1]);
}
vector<vector<array<int,2>>> cnt(N+1,vector<array<int,2>>(N+1));
cnt[0][N][0]=1;
rep(i,0,N) rep(j,0,N+1) rep(k,0,2) if (cnt[i][j][k]) {
rep(l,0,j+1) {
minc(cnt[i+1][j-l][k||(l==i+1)],mmul(cnt[i][j][k],comb[j][l]));
}
}
cout<<cnt[N][0][1]<<'\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
7 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
5 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
376 KB |
Output is correct |
| 11 |
Correct |
5 ms |
376 KB |
Output is correct |
| 12 |
Correct |
5 ms |
376 KB |
Output is correct |
| 13 |
Correct |
5 ms |
376 KB |
Output is correct |
| 14 |
Correct |
4 ms |
376 KB |
Output is correct |
| 15 |
Correct |
5 ms |
380 KB |
Output is correct |
| 16 |
Correct |
5 ms |
380 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
7 ms |
376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
376 KB |
Output is correct |
| 8 |
Correct |
5 ms |
376 KB |
Output is correct |
| 9 |
Correct |
5 ms |
376 KB |
Output is correct |
| 10 |
Correct |
5 ms |
376 KB |
Output is correct |
| 11 |
Correct |
5 ms |
376 KB |
Output is correct |
| 12 |
Correct |
5 ms |
376 KB |
Output is correct |
| 13 |
Correct |
5 ms |
376 KB |
Output is correct |
| 14 |
Correct |
4 ms |
376 KB |
Output is correct |
| 15 |
Correct |
5 ms |
380 KB |
Output is correct |
| 16 |
Correct |
5 ms |
380 KB |
Output is correct |
| 17 |
Correct |
136 ms |
1272 KB |
Output is correct |
| 18 |
Correct |
6 ms |
376 KB |
Output is correct |
| 19 |
Correct |
32 ms |
632 KB |
Output is correct |
| 20 |
Correct |
5 ms |
376 KB |
Output is correct |
| 21 |
Correct |
182 ms |
1484 KB |
Output is correct |
| 22 |
Correct |
24 ms |
632 KB |
Output is correct |
| 23 |
Correct |
7 ms |
376 KB |
Output is correct |
| 24 |
Correct |
42 ms |
760 KB |
Output is correct |
| 25 |
Correct |
30 ms |
632 KB |
Output is correct |
| 26 |
Correct |
54 ms |
760 KB |
Output is correct |
| 27 |
Correct |
250 ms |
1656 KB |
Output is correct |
| 28 |
Correct |
270 ms |
1660 KB |
Output is correct |
| 29 |
Correct |
257 ms |
1784 KB |
Output is correct |
| 30 |
Correct |
266 ms |
1784 KB |
Output is correct |
| 31 |
Correct |
262 ms |
1912 KB |
Output is correct |
| 32 |
Correct |
259 ms |
1784 KB |
Output is correct |
| 33 |
Correct |
262 ms |
1784 KB |
Output is correct |
| 34 |
Correct |
278 ms |
1788 KB |
Output is correct |
| 35 |
Correct |
269 ms |
1784 KB |
Output is correct |
| 36 |
Correct |
280 ms |
1784 KB |
Output is correct |
| 37 |
Correct |
272 ms |
1784 KB |
Output is correct |
