SRM #673 Div.2 Hard

SRM673Div2Hard.cpp

#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];
        
    }
};