Instantly share code, notes, and snippets.

# ctylim/SRM673Div2Hard.cpp Created Nov 20, 2015

What would you like to do?
SRM #673 Div.2 Hard
 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #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]; } };