TopCoder SRM 586: StringWeightDiv2

L が 26 以下の場合は、"abc","cz" のような同じ文字が２つ以上含まれない文字列が最小の重さ (= 0) になる。このときの総数は、 順列P(26, L) となる。

L が 27 以上の場合は、"a..ab..bc..c..yz..z" のような同じ文字が一箇所にまとまっていて、かつ全ての文字が含まれている文字列が最小の重さ (= L-26) になる。このときの総数は、重複組合せを使うとC((L-26) - 1, 26 - 1) * 26! となる。またこの式は 26 * P(L + 25, 25) に簡単化できる。

public class StringWeightDiv2 {
    const int mod = 1000000009;
    public int countMinimums(int L) {
        if (L <= 26) {
            long ans = 1;
            for (int i = 0; i < L; i++) {
                ans = (ans * (26 - i)) % mod;
            }
            return (int)ans;
        } else {
            L -= 26;

            long[,] choose = new long[1001, 1001];
            long[] factorial = new long[1002];
            factorial[0] = 1;
            for (int s = 0; s < 1001; s++) {
                factorial[s + 1] = factorial[s] * (s + 1) % mod;
                for (int t = 0; t < 1001; t++) {
                    if (t == 0 || t == s)
                        choose[s, t] = 1;
                    else if (s >= t)
                        choose[s, t] = (choose[s - 1, t] + choose[s - 1, t - 1]) % mod;
                }
            }

            return (int)((factorial[26] * choose[L + 25, 25]) % mod);
        }
}

111122233333 のような文字列の総数を [現在の長さ][文字の種類] で動的計画法しても解ける。

public class StringWeightDiv2 {
    const int mod = 1000000009;
    public int countMinimums(int L) {
        var dp = new long[1001,30];
        dp[0, 0] = 1;
        for (int i = 1; i <= L; i++) {
            for (int k = 1; k <= 26; k++) {
                dp[i, k] += dp[i - 1, k] + dp[i - 1, k - 1] * (26 - k + 1);
                dp[i, k] %= mod;
            }
        }
        int kind = Math.Min(L, 26);
        return (int)dp[L,kind];
    }
}