| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 529045 |
2022-02-22T03:19:36 Z |
8e7 |
Tents (JOI18_tents) |
C++17 |
|
2000 ms |
93180 KB |
//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b ){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 3005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
void madd(int &x, int v) {
x += v - mod; x += mod & (x>>31);
}
ll comb[maxn][maxn], fac[maxn], cat[maxn][maxn], po[maxn];
ll c(int n, int m) {
if (m > n || m < 0) return 0;
return comb[n][m];
}
int main() {
io
po[0] = 1;
for (int i = 1;i < maxn;i++) po[i] = po[i-1] * 4 % mod;
fac[0] = 1;
for (int i = 1;i < maxn;i++) fac[i] = fac[i-1] * i % mod;
comb[0][0] = 1;
for (int i = 1;i < maxn;i++) {
for (int j = 0;j <= i;j++) {
comb[i][j] = (comb[i-1][j] + (j ? comb[i-1][j-1] : 0)) % mod;
}
}
cat[0][0] = 1;
for (int i = 1;i < maxn-1;i++) {
for (int j = 0;j <= i;j++) {
if (j) cat[i][j] = (cat[i][j] + cat[i-1][j-1])%mod;
cat[i][j] = (cat[i][j] + cat[i-1][j+1] * (j+1)%mod)%mod;
}
}
int n, m;
cin >> n >> m;
ll ans = 0;
for (int i = 0;i < maxn;i++) {
for (int j = 0;j < maxn;j++) {
if (2*i + j > n || i + 2 * j > m) continue;
ll val = c(n, 2*i + j) * c(m, i + 2*j) % mod *
c(2*i + j, j)%mod * c(i + 2*j, i)%mod *
cat[2*i][0]%mod * cat[2*j][0]%mod * fac[i]%mod * fac[j]%mod;
ll s = 0;
int sx = n - (2*i+j), sy = m - (i+2*j);
for (int k = 0;k <= min(sx, sy);k++) {
s = (s + c(sx, k) * c(sy, k)%mod * fac[k]%mod * po[k]%mod)%mod;
//debug(i, j, sx, sy, k, c(sx, k) * c(sy, k)%mod * fac[k]%mod * po[k]%mod);
}
//debug(i, j, val, s);
debug(i, j, val*s);
ans = (ans + val * s)%mod;
//debug(ans);
}
}
cout << (ans+mod-1)%mod << endl;
}
Compilation message
tents.cpp: In function 'int main()':
tents.cpp:12:20: warning: statement has no effect [-Wunused-value]
12 | #define debug(...) 0
| ^
tents.cpp:66:4: note: in expansion of macro 'debug'
66 | debug(i, j, val*s);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
93084 KB |
Output is correct |
| 2 |
Correct |
91 ms |
93000 KB |
Output is correct |
| 3 |
Correct |
94 ms |
93048 KB |
Output is correct |
| 4 |
Correct |
88 ms |
93092 KB |
Output is correct |
| 5 |
Correct |
92 ms |
93020 KB |
Output is correct |
| 6 |
Correct |
93 ms |
93036 KB |
Output is correct |
| 7 |
Correct |
90 ms |
93040 KB |
Output is correct |
| 8 |
Correct |
105 ms |
93136 KB |
Output is correct |
| 9 |
Correct |
104 ms |
93072 KB |
Output is correct |
| 10 |
Correct |
99 ms |
93092 KB |
Output is correct |
| 11 |
Correct |
91 ms |
93168 KB |
Output is correct |
| 12 |
Correct |
102 ms |
93056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
90 ms |
93084 KB |
Output is correct |
| 2 |
Correct |
91 ms |
93000 KB |
Output is correct |
| 3 |
Correct |
94 ms |
93048 KB |
Output is correct |
| 4 |
Correct |
88 ms |
93092 KB |
Output is correct |
| 5 |
Correct |
92 ms |
93020 KB |
Output is correct |
| 6 |
Correct |
93 ms |
93036 KB |
Output is correct |
| 7 |
Correct |
90 ms |
93040 KB |
Output is correct |
| 8 |
Correct |
105 ms |
93136 KB |
Output is correct |
| 9 |
Correct |
104 ms |
93072 KB |
Output is correct |
| 10 |
Correct |
99 ms |
93092 KB |
Output is correct |
| 11 |
Correct |
91 ms |
93168 KB |
Output is correct |
| 12 |
Correct |
102 ms |
93056 KB |
Output is correct |
| 13 |
Correct |
91 ms |
93180 KB |
Output is correct |
| 14 |
Correct |
94 ms |
92996 KB |
Output is correct |
| 15 |
Execution timed out |
2090 ms |
93012 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
