This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios_base::sync_with_stdio(false);
cin.tie();
int n; ll mod;
cin >> n >> mod;
vector<vector<ll>> binom(n+1, vector<ll>(n+1));
for(int i = 0; i <= n; i++){
binom[i][0] = 1;
for(int j = 1; j <= i; j++){
binom[i][j] = (binom[i-1][j-1] + binom[i-1][j]) % mod;
}
}
vector<ll> fact(n+1);
fact[0] = 1;
for(int i = 1; i <= n; i++) fact[i] = (fact[i-1]*i) % mod;
vector<vector<ll>> dp(n+1, vector<ll>(n+1));
dp[n][n] = 1;
for(int a = n-1; a >= 0; a--){
for(int b = a; b >= 0; b--){
ll res = 0;
for(int k = a+1; k <= n; k++){
for(int l = a+1; l <= k; l++){
ll cnt = 0;
if(k == l){
for(int e = 1; e <= l-b; e++){
ll add = binom[l-b-1][e-1] * fact[e] % mod;
for(int up = 0; up < l-b-e; up++){
add = add * (2*(n-l)+up) % mod;
}
cnt = (cnt + add) % mod;
// cerr << "# " << binom[l-b][e-1] << " " << fact[e] << "\n";
}
}
else
for(int ek = 1; ek <= l-b; ek++){
for(int el = 1; ek+el <= l-b; el++){
ll add = binom[l-b-1][ek+el-1] * binom[ek+el-1][el] % mod;
add = add * fact[ek] % mod;
add = add * fact[el] % mod;
for(int up = 0; up < l-b-el-ek; up++){
add = add * (2*(n-l)-1+up) % mod;
}
cnt = (cnt + add) % mod;
}
}
res = (res + cnt * dp[k][l]) % mod;
// cerr << a << " " << b << " " << k << " " << l << " -> " << cnt << " " << cnt*dp[k][l] << "\n";
}
}
dp[a][b] = res;
}
}
ll total = 1;
for(int i = 0; i < n; i++) total = total * (2*i+1) % mod;
// cerr << dp[0][0] << "\n";
cout << (total - dp[0][0] + mod) % mod << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |