No.42 貯金箱の溜息 - shifth’s blog

勉強になった。
はじめ f(x,m) を多項式補完しないで f(x,m*C[x]+p) を多項式補完してる理由がすぐにわからなかった。f(x,m) だと次数が x とは限らないのか。
f(x,m*C[x]+p) は p に依存する。そのため補完に必要なサンプル点も p によって異なるので補完に必要なサンプル点数は 6 点だがサンプルとして確保するのは C[x]*(K+1)+1 点.

class SighOfSavingsBox {
public:
    void solve(void) {
            // M <= 10^18 なので M に対する DP ではダメ。どう高速化するか？
            //
            // f(x,m) := C[x] 以下の coin を使って m 円をちょうど払う方法の数
            //
            // とすると,
            //
            // f(x,m) = f(x-1,m) + f(x-1,m-C[x]) + f(x-1,m-2*C[x]) + ... + f(x-1,m-k*C[x]) (k*C[x] <= m) ...(*)
            // であり
            //
            // f(x,m-C[x]) = f(x-1,m-C[x]) + ... + f(x-1,m-k*C[x]) より
            // f(x,m) = f(x-1,m) + f(x,m-C[x]) と書ける
            //
            // このままだと m が大きすぎて計算できない。
            //
            // f(0,m) = 1 (0 次の多項式)であり p を C[x] 未満の任意の整数とすると
            //
            // f(x,m*C[x]+p)     - f(x,(m-1)*C[x]+p) = f(x-1,m*C[x]+p)
            // f(x,(m-1)*C[x]+p) - f(x,(m-2)*C[x]+p) = f(x-1,(m-1)*C[x]+p)
            //    :
            // f(x,C[x]+p)       - f(x,p)          = f(x-1,C[x]+p)
            //
            // なので
            //
            // f(x,m*C[x]+p) = f(x,p) + f(x-1,m*C[x]+p) + ... + f(x-1,C[x]+p)
            //                          <---------------- m ---------------->
            //
            // g(x) を d 次多項式とすると
            // g(x-k) = x^d + G(x-k) と書けるので
            //
            // x                 x
            // ∑ g(y)  = x*x^d + ∑ G(x-k)  となり d+1 次式となる。
            // y=1               k=1
            //
            // よって f(x,m*C[x]+p) は再帰的に m についての x 次式となる
            //
            // ( f(x,m) が x 次式になるわけではないことに注意!!!
            //   なぜなら (*) における k は k=m/C[x] であってこの値はかなり大きい )
            //
            // この x 次多項式の係数ををラグランジェ補完によって決定してやればよい。
            //
            // この多項式 f(x,m*C[x]+p) は p に依存する。
            //
            const vector<int> C = {1,5,10,50,100,500};

            // 多項式を補完するためにサンプル点を準備
            int K = C.size();
            int x = K-1;
            int nSamples = C[x]*(K+1) + 1;
            vector<vector<ModInt>> dp(K+1, vector<ModInt>(nSamples));

            // 初期化
            // C[0]=1 で表現できるのは 1 通り
            fill(RANGE(dp[0]), 1);

            // O(nSamples*K)
            FOR(x,1,K)
            REP(m,nSamples)
            {
                dp[x][m] = dp[x-1][m];
                if (m >= C[x])
                    dp[x][m] += dp[x][m-C[x]];
            }


            int T;
            cin>>T;
            REP(_,T)
            {
                ll M;
                cin>>M;

                //
                // sample を使って f(x,m*C[x]+p) をラグランジェ補完して
                //  m = M/C[x]
                //  p = M%C[x]
                // を代入する
                ModInt res = 0;
                ll m = M/C[x];
                ll p = M%C[x];
                // O(K^2*log(K))
                REP(i, K)
                {
                    ModInt c = 1;
                    REP(j, K)
                    {
                        if (i == j)
                            continue;
                        c *= (m-j);
                        c *= inverse(i-j);
                    }
                    res += dp[x][i*C[x]+p]*c;
                }
                cout<<res<<endl;
            }
    }
};