| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 763932 |
2023-06-23T03:31:04 Z |
minhcool |
Tents (JOI18_tents) |
C++17 |
|
623 ms |
143084 KB |
#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
#ifdef local
int fac[N], invfac[N];
int binpw(int base, int pw){
int ans = 1;
while(pw){
if(pw & 1) ans = (ans * base) % mod;
base = (base * base) % mod;
pw >>= 1;
}
return ans;
}
void prep(){
fac[0] = invfac[0] = 1;
for(int i = 1; i <= 100000; i++){
fac[i] = (fac[i - 1] * i) % mod;
invfac[i] = binpw(fac[i], mod - 2) % mod;
}
}
int precal[3005][3005];// what to do when we have i free rows and j free columns. actually we just either confirm (+1) or choose and (i - 1, j - 1)
int pref[3005][3005];
void process(){
int h, w;
cin >> h >> w;
//int ans = 0;
for(int i = 0; i <= h; i++){
for(int j = 0; j <= w; j++){
precal[i][j] = 1;
if(i > 0 && j > 0) precal[i][j] += pref[i - 1][j - 1] * 4 * j;
precal[i][j] %= mod;
//if(i > 0 && j > 0) pref[i][j] = (pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + precal[i][j] + 2 * mod) % mod;
if(i > 0) pref[i][j] = (pref[i - 1][j] + precal[i][j]) % mod;
else pref[i][j] = precal[i][j];
//else if(j > 0) pref[i][j] = (pref[i][j - 1] + precal[i][j]) % mod;
// cout << i << " " << j << " " << precal[i][j] << " " << pref[i][j] << "\n";
}
}
int ans = 0;
for(int cr = 0; cr <= h/2; cr++){
for(int cl = 0; cl <= w/2; cl++){
if((cr * 2 + cl) > h) continue;
if((cr + cl * 2) > w) continue;
// when we use 2 * cr rows, we also use cr columns that is not in the cl * 2 columns and vice versa
int tol = 0;
int temp = binpw(2, cr); temp = binpw(temp, mod - 2);
temp = (temp * fac[h]) % mod;
temp = (temp * invfac[h - 2 * cr]) % mod;
temp = (temp * fac[w]) % mod;
temp = (temp * invfac[w - cr]) % mod;
int temp2 = binpw(2, cl); temp2 = binpw(temp2, mod - 2);
// cout << temp2 << "\n";
temp2 = (temp2 * fac[w - cr]) % mod;
temp2 = (temp2 * invfac[w - cr - 2 * cl]) % mod;
// cout << temp2 << "\n";
temp2 = (temp2 * fac[h - 2 * cr]) % mod;
temp2 = (temp2 * invfac[h - 2 * cr - cl]) % mod;
// cout << temp << " " << temp2 << "\n";
tol = (temp * temp2) % mod;
tol = (tol * invfac[cl]) % mod;
tol = (tol * invfac[cr]) % mod;
//cout << tol << "\n";
//cout << (h - (cr * 2 + cl)) << " " << (w - (cr + cl))
tol = (tol * precal[h - (cr * 2 + cl)][w - (cr + cl * 2)]) % mod;
if(!(cl + cr)) tol = (tol + mod - 1) % mod;
/*
int temp3 = min(h - (cr * 2 + cl), w - (cr + cl * 2)), sum = 0;
for(int single = 0; single <= temp3; single++){
int ini = binpw(4, single);
ini = (ini * fac[h - (cr * 2 + cl)]) % mod;
ini = (ini * invfac[h - (cr * 2 + cl) - single]) % mod;
ini = (ini * fac[w - (cr + cl * 2)]) % mod;
ini = (ini * invfac[w - (cr + cl * 2) - single]) % mod;
ini = (ini * invfac[single]) % mod;
sum = (sum + ini) % mod;
}*/
//if(!(cl | cr)) sum = (sum + mod - 1) % mod;
//tol = (tol * sum) % mod;
//tol = (tol * )
// cout << cr << " " << cl << " " << tol << "\n";
ans = (ans + tol) % mod;
}
}
cout << ans << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
prep();
process();
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1892 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1904 KB |
Output is correct |
| 3 |
Correct |
13 ms |
2260 KB |
Output is correct |
| 4 |
Correct |
13 ms |
3540 KB |
Output is correct |
| 5 |
Correct |
14 ms |
2632 KB |
Output is correct |
| 6 |
Correct |
14 ms |
3972 KB |
Output is correct |
| 7 |
Correct |
13 ms |
2900 KB |
Output is correct |
| 8 |
Correct |
13 ms |
4196 KB |
Output is correct |
| 9 |
Correct |
13 ms |
2832 KB |
Output is correct |
| 10 |
Correct |
15 ms |
4880 KB |
Output is correct |
| 11 |
Correct |
13 ms |
2012 KB |
Output is correct |
| 12 |
Correct |
18 ms |
5716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
1892 KB |
Output is correct |
| 2 |
Correct |
13 ms |
1904 KB |
Output is correct |
| 3 |
Correct |
13 ms |
2260 KB |
Output is correct |
| 4 |
Correct |
13 ms |
3540 KB |
Output is correct |
| 5 |
Correct |
14 ms |
2632 KB |
Output is correct |
| 6 |
Correct |
14 ms |
3972 KB |
Output is correct |
| 7 |
Correct |
13 ms |
2900 KB |
Output is correct |
| 8 |
Correct |
13 ms |
4196 KB |
Output is correct |
| 9 |
Correct |
13 ms |
2832 KB |
Output is correct |
| 10 |
Correct |
15 ms |
4880 KB |
Output is correct |
| 11 |
Correct |
13 ms |
2012 KB |
Output is correct |
| 12 |
Correct |
18 ms |
5716 KB |
Output is correct |
| 13 |
Correct |
12 ms |
1952 KB |
Output is correct |
| 14 |
Correct |
20 ms |
20556 KB |
Output is correct |
| 15 |
Correct |
374 ms |
111680 KB |
Output is correct |
| 16 |
Correct |
20 ms |
9292 KB |
Output is correct |
| 17 |
Correct |
66 ms |
26892 KB |
Output is correct |
| 18 |
Correct |
119 ms |
35488 KB |
Output is correct |
| 19 |
Correct |
541 ms |
127296 KB |
Output is correct |
| 20 |
Correct |
364 ms |
103108 KB |
Output is correct |
| 21 |
Correct |
249 ms |
68916 KB |
Output is correct |
| 22 |
Correct |
234 ms |
72228 KB |
Output is correct |
| 23 |
Correct |
71 ms |
55420 KB |
Output is correct |
| 24 |
Correct |
623 ms |
143084 KB |
Output is correct |
| 25 |
Correct |
465 ms |
123800 KB |
Output is correct |
| 26 |
Correct |
542 ms |
134572 KB |
Output is correct |
| 27 |
Correct |
595 ms |
139328 KB |
Output is correct |
