hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

TopCoder SRM 720 Div1 Easy: SumProduct

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

digit1 桁の数  A と、digit2 桁の数  B を、以下の条件のもとで作ることを考える。

  • leading zero を許す
  •  A, B の各桁において、登場する  i の個数の合計は最大で  a_i

このような  A, B それぞれについて、  A \times B の総和を求めよ。

解説

leading zero が許容されているため、どの数字をどこに並べても良いです。

桁ごとに分けて処理します。具体的には、  A i 桁目を  x に、  B j 桁目を  y にすることを考えます。この桁だけ見ると総和は当然  10^{i+j} xy だけ増えることになりますが、実際にはこれ以外の桁にも数字を入れる必要があるので、先ほどの値に「注目している桁以外に数字を入れるときの場合の数」を掛けたぶんだけ増えることがわかります。

注目している桁以外に数字を入れるときの場合の数は、 DP で求められます。

 \mathrm{dp} \left[ i \right] \left[ s \right] :=  i 番目の数字までを使い、まだ数字が入っていない桁が  s 桁あるような数字の入れ方の場合の数 とします。  i 番目の数字を  k 個使う場合、 s 個あった空き場所から  k 個を選択して入れることになるため、この DP は  \mathrm{dp} \left[ i \right] \left[ s \right] = \sum_{k=0}^{a_{i}} \mathrm{dp} \left[ i-1 \right] \left[ s+k \right] \times {}_{s+k} C_{k} と更新できます。 ( a_i は、現在使える数字  i の個数です)

答えとなるのは、

 \sum_{i=0}^{9} \sum_{j=0}^{9} \mathrm{dp}_{x=i, y=j} \left[ 10 \right] \left[ 0 \right] \times  ij  \sum_{d=0}^{\mathrm{digit1 - 1}} 10^{d} \sum_{d=0}^{\mathrm{digit2-1}} 10^{d} です。

ソースコード

class SumProduct {
    public:
    ll comb[210][210], dp[15][1010];
    ll mod_pow(ll n, ll k) {
        ll ret = 1, pw = n%MOD;
        while(k) {
            if(k & 1) (ret *= pw) %= MOD;
            (pw *= pw) %= MOD;
            k >>= 1;
        }
        return ret;
    }

    ll calc(int d) {
        ll a = (mod_pow(10, d) - 1 + MOD) % MOD;
        return (a * mod_pow(9, MOD-2)) % MOD;
    }

    int findSum(vector<int> amount, int blank1, int blank2) {
        for(int i=0; i<210; i++) {
            comb[i][0] = 1;
            for(int j=1; j<=i; j++) {
                comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
            }
        }

        int sum = 0, ans = 0;
        for(auto x : amount) sum += x;
        ll mul_a = calc(blank1), mul_b = calc(blank2);

        for(int x=0; x<10; x++) {
            for(int y=0; y<10; y++) {
                if(!amount[x] || !amount[y]) continue;
                vector<int> rest_num = amount;
                rest_num[x]--; rest_num[y]--;

                memset(dp, 0, sizeof(dp));
                int rest = blank1 + blank2 - 2;
                dp[0][rest] = 1;
                for(int num=0; num<10; num++) {
                    // 空き場所が s 個あるところに num を k 個置こう
                    for(int s=0; s<=rest; s++) {
                        for(int k=0; k<=min(s, rest_num[num]); k++) {
                            (dp[num+1][s-k] += dp[num][s] * comb[s][k]) %= MOD;
                        }
                    }
                }

                ll ad = (mul_a * mul_b) % MOD;
                (ad *= dp[10][0]) %= MOD;
                (ad *= x * y) %= MOD;
                (ans += ad) %= MOD;
            }
        }
        return ans;
    }
};

桁を抜き出す系、前にも見たことあるのに思いつかなくて悔しい・・・