| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 132328 |
2019-07-18T17:29:05 Z |
duality |
Tents (JOI18_tents) |
C++11 |
|
218 ms |
70904 KB |
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
#define MOD 1000000007
LLI inv(LLI n) {
int e = MOD-2;
LLI r = 1;
while (e > 0) {
if (e & 1) r *= n,r %= MOD;
e >>= 1;
n *= n,n %= MOD;
}
return r;
}
LLI fact[3001],invf[3001],invpow2[6001];
LLI dp[3001][3001];
LLI choose(LLI n,LLI k) {
return (fact[n]*((invf[k]*invf[n-k]) % MOD)) % MOD;
}
int main() {
int H,W;
cin >> H >> W;
int i,j;
LLI ans = 0;
fact[0] = invf[0] = 1;
for (i = 1; i <= max(H,W); i++) fact[i] = (fact[i-1]*i) % MOD,invf[i] = inv(fact[i]);
invpow2[0] = 1;
for (i = 1; i <= H+W; i++) invpow2[i] = (invpow2[i-1]*inv(2)) % MOD;
for (i = 0; i <= W; i++) dp[0][i] = 1;
for (i = 1; i <= H; i++) {
dp[i][0] = 1;
for (j = 1; j <= W; j++) dp[i][j] = (dp[i-1][j]+4*j*dp[i-1][j-1]) % MOD;
}
for (i = 0; i <= H; i++) {
for (j = 0; j <= W; j++) {
if ((i+2*j <= H) && (j+2*i <= W)) {
LLI x = (((choose(H,i)*choose(W,2*i)) % MOD)*fact[2*i]) % MOD;
LLI y = (((choose(W-2*i,j)*choose(H-i,2*j)) % MOD)*fact[2*j]) % MOD;
ans += ((x*y) % MOD)*((dp[H-i-2*j][W-j-2*i]*invpow2[i+j]) % MOD);
ans %= MOD;
}
}
}
cout << (ans+MOD-1) % MOD << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 5 |
Correct |
2 ms |
760 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1400 KB |
Output is correct |
| 7 |
Correct |
3 ms |
888 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1400 KB |
Output is correct |
| 9 |
Correct |
2 ms |
888 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1784 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1144 KB |
Output is correct |
| 5 |
Correct |
2 ms |
760 KB |
Output is correct |
| 6 |
Correct |
3 ms |
1400 KB |
Output is correct |
| 7 |
Correct |
3 ms |
888 KB |
Output is correct |
| 8 |
Correct |
3 ms |
1400 KB |
Output is correct |
| 9 |
Correct |
2 ms |
888 KB |
Output is correct |
| 10 |
Correct |
4 ms |
1784 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2288 KB |
Output is correct |
| 13 |
Correct |
3 ms |
376 KB |
Output is correct |
| 14 |
Correct |
9 ms |
9720 KB |
Output is correct |
| 15 |
Correct |
139 ms |
55340 KB |
Output is correct |
| 16 |
Correct |
7 ms |
4088 KB |
Output is correct |
| 17 |
Correct |
24 ms |
13048 KB |
Output is correct |
| 18 |
Correct |
38 ms |
17144 KB |
Output is correct |
| 19 |
Correct |
161 ms |
63152 KB |
Output is correct |
| 20 |
Correct |
130 ms |
51148 KB |
Output is correct |
| 21 |
Correct |
80 ms |
33912 KB |
Output is correct |
| 22 |
Correct |
84 ms |
35576 KB |
Output is correct |
| 23 |
Correct |
33 ms |
27128 KB |
Output is correct |
| 24 |
Correct |
218 ms |
70904 KB |
Output is correct |
| 25 |
Correct |
163 ms |
61304 KB |
Output is correct |
| 26 |
Correct |
190 ms |
66776 KB |
Output is correct |
| 27 |
Correct |
212 ms |
69076 KB |
Output is correct |
