| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 610122 |
2022-07-28T05:02:48 Z |
czhang2718 |
Tents (JOI18_tents) |
C++17 |
|
89 ms |
70728 KB |
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
const int N=3001, mod=1e9+7;
int n, m;
// int C[N][N];
// int f[N][N];
int dp[N][N];
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
// a left, b right
// nCa * mCb * (m chooose 2a) * (2a)!/2^a * (n choose 2b) * (2b)!/2^b * f(n-a-2*b,m-2*a-b)
// f(a,b) = f(a-1,b) + b*f(a-1,b-1)
// for(int i=0; i<N; i++) C[i][0]=1;
// for(int i=1; i<N; i++){
// for(int j=1; j<=i; j++) C[i][j]=C[i-1][j]+C[i-1][j-1];
// }
for(int i=0; i<=max(n,m); i++) dp[i][0]=dp[0][i]=1;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
dp[i][j]=(i>=2?i*(i-1)/2*dp[i-2][j-1]:0)+i*4*dp[i-1][j-1]+dp[i][j-1]+(j>=2?(j-1)*i*dp[i-1][j-2]:0);
dp[i][j]%=mod;
}
}
cout << (dp[n][m]+mod-1)%mod;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
724 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1748 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
1108 KB |
Output is correct |
| 5 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
1364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
724 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1748 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2132 KB |
Output is correct |
| 13 |
Correct |
3 ms |
7764 KB |
Output is correct |
| 14 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 15 |
Correct |
61 ms |
55132 KB |
Output is correct |
| 16 |
Correct |
8 ms |
9380 KB |
Output is correct |
| 17 |
Correct |
18 ms |
17280 KB |
Output is correct |
| 18 |
Correct |
23 ms |
17764 KB |
Output is correct |
| 19 |
Correct |
67 ms |
62924 KB |
Output is correct |
| 20 |
Correct |
53 ms |
51008 KB |
Output is correct |
| 21 |
Correct |
36 ms |
35400 KB |
Output is correct |
| 22 |
Correct |
36 ms |
35396 KB |
Output is correct |
| 23 |
Correct |
23 ms |
27080 KB |
Output is correct |
| 24 |
Correct |
86 ms |
70728 KB |
Output is correct |
| 25 |
Correct |
67 ms |
61112 KB |
Output is correct |
| 26 |
Correct |
86 ms |
66512 KB |
Output is correct |
| 27 |
Correct |
89 ms |
69068 KB |
Output is correct |
