| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 364698 |
2021-02-09T17:38:55 Z |
Nima_Naderi |
Tents (JOI18_tents) |
C++14 |
|
284 ms |
71472 KB |
///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN = 3e3 + 10;
const ll Mod = 1e9 + 7;
ll power(ll a, ll b){
return (!b ? 1 : power(a * a % Mod, b / 2) * (b & 1LL ? a : 1) % Mod);
}
ll inv(ll x){
return power(x, Mod - 2);
}
inline void mkay(ll& x){
while(x >= Mod) x -= Mod;
}
ll n, m;
ll dp[MXN][MXN], F[MXN], I[MXN];
ll nCr(ll n, ll r){
if(r < 0 || r > n) return 0;
return F[n] * I[r] % Mod * I[n - r] % Mod;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
F[0] = I[0] = 1;
for(int i = 1; i < MXN; i ++) F[i] = F[i - 1] * i % Mod;
I[MXN - 1] = inv(F[MXN - 1]);
for(int i = MXN - 2; i; i --) I[i] = I[i + 1] * (i + 1) % Mod;
for(int i = 0; i < MXN; i ++) dp[i][0] = dp[0][i] = 1;
dp[1][1] = 4 + 1;
for(int j = 2; j < MXN; j ++){
dp[j][1] = dp[1][j] = (4 * j + nCr(j, 2) + 1) % Mod;
}
for(int i = 2; i < MXN; i ++){
for(int j = 2; j < MXN; j ++){
dp[i][j] = (dp[i - 1][j] + nCr(j, 2) * dp[i - 1][j - 2] % Mod);
dp[i][j] = (dp[i][j] + j * 4 * dp[i - 1][j - 1] % Mod);
dp[i][j] = (dp[i][j] + j * (i - 1) % Mod * dp[i - 2][j - 1] % Mod);
mkay(dp[i][j]);
}
}
cin >> n >> m;
cout << dp[n][m] - 1 << '\n';
return 0;
}
/*!
HE'S AN INSTIGATOR,
ENEMY ELIMINATOR,
AND WHEN HE KNOCKS YOU BETTER
YOU BETTER LET HIM IN.
*/
//! N.N
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
254 ms |
71276 KB |
Output is correct |
| 2 |
Correct |
250 ms |
71276 KB |
Output is correct |
| 3 |
Correct |
256 ms |
71320 KB |
Output is correct |
| 4 |
Correct |
264 ms |
71404 KB |
Output is correct |
| 5 |
Correct |
256 ms |
71276 KB |
Output is correct |
| 6 |
Correct |
263 ms |
71276 KB |
Output is correct |
| 7 |
Correct |
256 ms |
71296 KB |
Output is correct |
| 8 |
Correct |
252 ms |
71276 KB |
Output is correct |
| 9 |
Correct |
264 ms |
71404 KB |
Output is correct |
| 10 |
Correct |
251 ms |
71276 KB |
Output is correct |
| 11 |
Correct |
264 ms |
71276 KB |
Output is correct |
| 12 |
Correct |
255 ms |
71404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
254 ms |
71276 KB |
Output is correct |
| 2 |
Correct |
250 ms |
71276 KB |
Output is correct |
| 3 |
Correct |
256 ms |
71320 KB |
Output is correct |
| 4 |
Correct |
264 ms |
71404 KB |
Output is correct |
| 5 |
Correct |
256 ms |
71276 KB |
Output is correct |
| 6 |
Correct |
263 ms |
71276 KB |
Output is correct |
| 7 |
Correct |
256 ms |
71296 KB |
Output is correct |
| 8 |
Correct |
252 ms |
71276 KB |
Output is correct |
| 9 |
Correct |
264 ms |
71404 KB |
Output is correct |
| 10 |
Correct |
251 ms |
71276 KB |
Output is correct |
| 11 |
Correct |
264 ms |
71276 KB |
Output is correct |
| 12 |
Correct |
255 ms |
71404 KB |
Output is correct |
| 13 |
Correct |
253 ms |
71404 KB |
Output is correct |
| 14 |
Correct |
253 ms |
71276 KB |
Output is correct |
| 15 |
Correct |
252 ms |
71404 KB |
Output is correct |
| 16 |
Correct |
253 ms |
71472 KB |
Output is correct |
| 17 |
Correct |
251 ms |
71276 KB |
Output is correct |
| 18 |
Correct |
253 ms |
71404 KB |
Output is correct |
| 19 |
Correct |
254 ms |
71404 KB |
Output is correct |
| 20 |
Correct |
251 ms |
71404 KB |
Output is correct |
| 21 |
Correct |
254 ms |
71404 KB |
Output is correct |
| 22 |
Correct |
250 ms |
71276 KB |
Output is correct |
| 23 |
Correct |
256 ms |
71288 KB |
Output is correct |
| 24 |
Correct |
253 ms |
71276 KB |
Output is correct |
| 25 |
Correct |
254 ms |
71360 KB |
Output is correct |
| 26 |
Correct |
251 ms |
71276 KB |
Output is correct |
| 27 |
Correct |
284 ms |
71280 KB |
Output is correct |
