| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 431278 |
2021-06-17T10:41:08 Z |
keko37 |
Tents (JOI18_tents) |
C++14 |
|
205 ms |
63340 KB |
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
typedef long long llint;
const int MAXN = 3005;
int add (int a, int b) {a += b; if (a >= MOD) return a - MOD; return a;}
int sub (int a, int b) {a -= b; if (a < 0) return a + MOD; return a;}
int mul (int a, int b) {return (llint) a * b % MOD;}
int n, m;
int fact[MAXN], pot[MAXN];
int nck[MAXN][MAXN], dp[MAXN][MAXN];
void precompute () {
fact[0] = 1;
pot[0] = 1;
for (int i = 1; i < MAXN; i++) {
fact[i] = mul(fact[i - 1], i);
pot[i] = mul(pot[i - 1], (MOD + 1) / 2);
}
for (int i = 0; i < MAXN; i++) {
nck[i][0] = nck[i][i] = 1;
for (int j = 1; j < i; j++) {
nck[i][j] = add(nck[i - 1][j], nck[i - 1][j - 1]);
}
}
for (int i = 0; i < MAXN; i++) {
dp[i][0] = dp[0][i] = 1;
}
for (int i = 1; i < MAXN; i++) {
for (int j = 1; j < MAXN; j++) {
dp[i][j] = add(dp[i - 1][j], mul(4 * j, dp[i - 1][j - 1]));
}
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
precompute();
cin >> n >> m;
int sol = 0;
for (int a = 0; a <= n; a++) {
for (int b = 0; b <= m; b++) {
int x = n - a - 2 * b;
int y = m - b - 2 * a;
if (x < 0 || y < 0) continue;
int val = mul(mul(nck[n][a], nck[m][2 * a]), mul(nck[n - a][2 * b], nck[m - 2 * a][b]));
val = mul(val, mul(mul(fact[2 * a], pot[a]), mul(fact[2 * b], pot[b])));
val = mul(val, dp[x][y]);
sol = add(sol, val);
}
}
cout << sub(sol, 1);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
63320 KB |
Output is correct |
| 2 |
Correct |
73 ms |
63288 KB |
Output is correct |
| 3 |
Correct |
76 ms |
63236 KB |
Output is correct |
| 4 |
Correct |
65 ms |
63264 KB |
Output is correct |
| 5 |
Correct |
60 ms |
63272 KB |
Output is correct |
| 6 |
Correct |
76 ms |
63228 KB |
Output is correct |
| 7 |
Correct |
73 ms |
63332 KB |
Output is correct |
| 8 |
Correct |
63 ms |
63216 KB |
Output is correct |
| 9 |
Correct |
76 ms |
63228 KB |
Output is correct |
| 10 |
Correct |
73 ms |
63332 KB |
Output is correct |
| 11 |
Correct |
70 ms |
63276 KB |
Output is correct |
| 12 |
Correct |
64 ms |
63268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
63320 KB |
Output is correct |
| 2 |
Correct |
73 ms |
63288 KB |
Output is correct |
| 3 |
Correct |
76 ms |
63236 KB |
Output is correct |
| 4 |
Correct |
65 ms |
63264 KB |
Output is correct |
| 5 |
Correct |
60 ms |
63272 KB |
Output is correct |
| 6 |
Correct |
76 ms |
63228 KB |
Output is correct |
| 7 |
Correct |
73 ms |
63332 KB |
Output is correct |
| 8 |
Correct |
63 ms |
63216 KB |
Output is correct |
| 9 |
Correct |
76 ms |
63228 KB |
Output is correct |
| 10 |
Correct |
73 ms |
63332 KB |
Output is correct |
| 11 |
Correct |
70 ms |
63276 KB |
Output is correct |
| 12 |
Correct |
64 ms |
63268 KB |
Output is correct |
| 13 |
Correct |
62 ms |
63300 KB |
Output is correct |
| 14 |
Correct |
68 ms |
63272 KB |
Output is correct |
| 15 |
Correct |
151 ms |
63312 KB |
Output is correct |
| 16 |
Correct |
78 ms |
63332 KB |
Output is correct |
| 17 |
Correct |
72 ms |
63232 KB |
Output is correct |
| 18 |
Correct |
87 ms |
63320 KB |
Output is correct |
| 19 |
Correct |
152 ms |
63336 KB |
Output is correct |
| 20 |
Correct |
137 ms |
63336 KB |
Output is correct |
| 21 |
Correct |
103 ms |
63336 KB |
Output is correct |
| 22 |
Correct |
117 ms |
63260 KB |
Output is correct |
| 23 |
Correct |
90 ms |
63252 KB |
Output is correct |
| 24 |
Correct |
197 ms |
63272 KB |
Output is correct |
| 25 |
Correct |
147 ms |
63340 KB |
Output is correct |
| 26 |
Correct |
155 ms |
63336 KB |
Output is correct |
| 27 |
Correct |
205 ms |
63340 KB |
Output is correct |
