SRM 663 div1 med:ChangingChange
戻すDP,覚えました(あんまり理解していない)
解法
こどふぉの解説を参考にしました。
SRM 663 Brief Editorial - Codeforces
ways = {1, 3, 6, 2}となっているときに,それに対応する多項式を考えてとします。
このように考えると,「valueが1のコインを追加した際の場合の数」というのは,「を元の多項式に掛け算した時の各多項式係数」と対応します。
「valueが3のコインを追加した際の場合の数」というのは,「を元の多項式に掛け算した時の各多項式係数」と対応します。そんな感じでvalueが1以外の時ものの次数が変わるだけなのでこれ以降はvalueが1のときのみを考えます。
さっきの論法を逆に考えてみます。「valueが1のコインを取り除く」ことは,多項式からを割ることと同じと考えられます。で,ちょっとここはよくわからないのですが,これはを掛け算することと同じになるらしいです(とりあえずはで上記の値に収束するのでそれで納得してしまいました)。多分群とかの知識使えばわかるんじゃないでしょうか。教えて欲しいです。
これにより,毎回のクエリを答えるためには,
・のnumRemoved[i]乗を計算し,
・それをwaysを多項式にしたやつに掛け算して,
・そのの係数を見れば良い
ということがわかりました。
まず最初のn乗するところから考えます。少し考えればわかりますが,のn乗はのn乗を計算して,xの奇数乗のところだけマイナスをつければ求まるということがわかります(マジメにやるなら帰納法ですが,のxを-xにしたと思えばわかりやすいんじゃないでしょうか)。
じゃあ今度はのn乗をどう求めるかということになるんですが,の係数は,「(n-1)×cの格子点を左端から右端まで進む場合の数」と同じになるのでです。
よって,の係数を求めると,
となります。
const int MOD = 1e9+7; // 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; } const int MAX = 1003000; ll fact[MAX]; ll rfact[MAX]; // mod_inverse ll mod_inverse(ll a, ll m) { ll x, y; extgcd(a, m, x, y); return (m+x%m) % m; } ll nCr(int n, int r) { ll ret = fact[n]; (ret *= rfact[r]) %= MOD; (ret *= rfact[n-r]) %= MOD; return ret; } class ChangingChange { public: vector <int> countWays(vector <int> ways, vector <int> valueRemoved, vector <int> numRemoved) { int D = ways.size() - 1; int Q = valueRemoved.size(); vector<int> ans(Q, 0); fact[0] = rfact[0] = 1; for (int i = 1; i < MAX; i++) { fact[i] = (fact[i-1]*i) % MOD; rfact[i] = mod_inverse(fact[i], MOD); } for (int t = 0; t < Q; t++) { int v = valueRemoved[t]; int n = numRemoved[t]; for (int p = 0; p * v <= D; p++) { ll tmp = 1; if (p%2) tmp = -1; tmp *= (ways[D-p*v] * nCr(n+p-1, p)) % MOD; tmp %= MOD; ans[t] = (ans[t] + tmp) % MOD; if (ans[t] < 0) ans[t] += MOD; } } return ans; } };