# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
319570 | BeanZ | Zapina (COCI20_zapina) | C++14 | 199 ms | 3428 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
//#define task "A"
#define ll long long
#define endl '\n'
const int N = 355;
const int mod = 1e9 + 7;
const int lg = 18;
ll dp[N][N][2];
ll fact[N], f[N][N];
ll binpow(ll u, ll p){
if (p == 0) return 1;
if (p == 1) return u;
ll t = binpow(u, p / 2);
if (p & 1) return t * t % mod * u % mod;
return t * t % mod;
}
ll nCk(ll n, ll k){
return fact[n] * binpow(fact[n - k], mod - 2) % mod * binpow(fact[k], mod - 2) % mod;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen(".inp", "r")){
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
ll n;
cin >> n;
fact[0] = 1;
for (int i = 1; i <= n; i++){
fact[i] = fact[i - 1] * i % mod;
}
for (int i = 0; i <= n; i++){
for (int j = 0; j <= i; j++){
f[i][j] = nCk(i, j);
}
}
dp[0][0][0] = 1;
for (int i = 1; i <= n; i++){
for (int j = 0; j <= n; j++){
for (int k = 0; k <= j; k++){
if (k == i){
dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j - k][0] * f[n - (j - k)][k]) % mod;
dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j - k][1] * f[n - (j - k)][k]) % mod;
} else {
dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j - k][0] * f[n - (j - k)][k]) % mod;
dp[i][j][1] = (dp[i][j][1] + dp[i - 1][j - k][1] * f[n - (j - k)][k]) % mod;
}
}
}
}
cout << dp[n][n][1];
}
/*
*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |