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); } };