SRM 656 div1 med:PermutationCounts

これも良い問題だよなぁ。こういうの解けるようになりたい。

問題:TopCoder Statistics - Problem Statement

解法:めぐるさんの説明(因幡めぐる@競技プログラミング(@meguru_comp)/2015年04月17日 - Twilog)が非常にわかりやすいのでそれを参考にしました。
以下ソースコード

const ll MOD = 1e9+7;
const ll MAXN = 1000100;
ll fact[MAXN];
ll factinv[MAXN];

// extgcd
ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    return (m+x%m) % m;
}

void init() {
    fact[0] = 1;
    factinv[0] = 1;
    for (ll i = 1; i < MAXN; i++) {
        fact[i] = (i*fact[i-1]) % MOD;
        factinv[i] = mod_inverse(fact[i], MOD);
    }
}

ll nCr(int n, int r) {
    return (fact[n]*factinv[r]%MOD)*factinv[n-r]%MOD;
}

ll dp[3000][2];
vector<int> sum;
int M;

ll dfs(int cur, int p) {
    if (cur == M) return (p == 0) ? 1 : -1;
    ll& ret = dp[cur][p];
    if (ret >= 0) return ret;
    ret = 0;
    // どこまですすめるか
    for (int i = cur; i < M; i++) {
        int n = sum[i+1];
        int r = sum[cur];
        int q = ((i-cur)&1);
        ret += MOD+(nCr(n, r) * dfs(i+1, p^q))%MOD;
        ret %= MOD;
    }
    return ret;
}

class PermutationCounts {
public:
    int countPermutations(int N, vector <int> pos) {
        init();
        sort(pos.begin(), pos.end());
        vector<int> nums;
        int cur = 0;
        for (int el : pos) {
            nums.push_back(el-cur);
            cur = el;
        }
        nums.push_back(N-cur);
        memset(dp, -1, sizeof(dp));
        M = nums.size();
        sum.resize(M+1);
        sum[0] = 0;
        for (int i = 1; i <= M; i++) {
            sum[i] = sum[i-1]+nums[i-1];
        }
        for (auto el : sum) cout << el << "  ";
        cout << endl;
        return dfs(0, 0);
    }
};