Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
SRM #673 Div.2 Hard
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
using namespace std;
class BearPermutations2 {
public:
ll mod;
ll comb[101][101];
ll f[101];
ll dp[101];
void calc_comb(){
rep(i, 101){
comb[i][0] = 1;
comb[i][i] = 1;
}
repd(i, 2, 101){
repd(j, 1, i){
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
comb[i][j] %= mod;
}
}
}
void calc_f(){
f[0] = 0;
f[1] = 1;
repd(i, 2, 101){
f[i] = f[i - 1] * i;
f[i] %= mod;
}
}
void init_dp(){
dp[0] = 0;
dp[1] = 0;
dp[2] = 0;
}
ll powMod(ll a, ll b, ll m){
ll ret = 1;
while (b > 0) {
if (b & 1) {
ret = ret * a % m;
}
a = a * a % m;
b >>= 1;
}
return ret;
}
ll invMod(ll a, ll m){
return powMod(a, m - 2, m);
}
int getSum(int N, int MOD) {
mod = MOD;
calc_comb();
calc_f();
repd(i, 3, N + 1){
dp[i] = 0;
rep(j, i){
if (j == 0 || j == i - 1) {
dp[i] += dp[i - 1];
dp[i] %= mod;
}
else{
ll tmp = f[j] * f[i - 1 - j];
tmp %= mod;
tmp *= i + 1;
tmp %= mod;
tmp *= invMod(2, mod);
tmp %= mod;
tmp += f[j] * dp[i - 1 - j] + f[i - 1 - j] * dp[j];
tmp %= mod;
tmp *= comb[i - 1][j];
tmp %= mod;
dp[i] += tmp;
dp[i] %= mod;
// cout << i << ", " << j << ": " << tmp << endl;
}
}
}
dp[N] += mod;
dp[N] %= mod;
return (int)dp[N];
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment