mayoko’s diary

プロコンとかいろいろ。

SRM 663 div1 med:ChangingChange

戻すDP,覚えました(あんまり理解していない)

解法

こどふぉの解説を参考にしました。
SRM 663 Brief Editorial - Codeforces

ways = {1, 3, 6, 2}となっているときに,それに対応する多項式を考えて1 + 3x + 6x^2 + 2x^3とします。

このように考えると,「valueが1のコインを追加した際の場合の数」というのは,「x+1を元の多項式に掛け算した時の各多項式係数」と対応します。

「valueが3のコインを追加した際の場合の数」というのは,「x^3+1を元の多項式に掛け算した時の各多項式係数」と対応します。そんな感じでvalueが1以外の時もx+1xの次数が変わるだけなのでこれ以降はvalueが1のときのみを考えます。

さっきの論法を逆に考えてみます。「valueが1のコインを取り除く」ことは,多項式からx+1を割ることと同じと考えられます。で,ちょっとここはよくわからないのですが,これは1-x+x^2-x^3+...を掛け算することと同じになるらしいです(とりあえず\frac{1}{(x+1)}x<1で上記の値に収束するのでそれで納得してしまいました)。多分群とかの知識使えばわかるんじゃないでしょうか。教えて欲しいです。

これにより,毎回のクエリを答えるためには,
1-x+x^2-x^3+...のnumRemoved[i]乗を計算し,
・それをwaysを多項式にしたやつに掛け算して,
・そのx^Dの係数を見れば良い
ということがわかりました。

まず最初のn乗するところから考えます。少し考えればわかりますが,1-x+x^2-x^3+...のn乗は1+x+x^2+x^3+...のn乗を計算して,xの奇数乗のところだけマイナスをつければ求まるということがわかります(マジメにやるなら帰納法ですが,\frac{1}{1-x} = 1+x+x^2+x^3+...のxを-xにしたと思えばわかりやすいんじゃないでしょうか)。

じゃあ今度は1+x+x^2+x^3+...のn乗をどう求めるかということになるんですが,x^cの係数は,「(n-1)×cの格子点を左端から右端まで進む場合の数」と同じになるので{}_{n-c-1}C_cです。

よって,x^Dの係数を求めると,
f:id:mayokoex:20150726142248p:plain
となります。

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