TopCoder SRM 720 Div1 Easy: SumProduct

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

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

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

このような それぞれについて、 の総和を求めよ。

解説

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

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

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

番目の数字までを使い、まだ数字が入っていない桁が 桁あるような数字の入れ方の場合の数 とします。 番目の数字を 個使う場合、 個あった空き場所から 個を選択して入れることになるため、この DP は と更新できます。 ( は、現在使える数字 の個数です)

答えとなるのは、

です。

ソースコード

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

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