SRM 655 div1 med:Nine

解説を読んで解いたんですが,さっき汚いコードと言ったコードは上手く書けば普通のコードになるっぽいですね。

問題:TopCoder Statistics - Problem Statement

解法:基本的にはさっきの(SRM 655 div2 hard:NineEasy - mayoko’s diary)に似ている。先程は各桁についてその桁を0〜9のどれにするかで状態を遷移させていたが,今度はちょっと別の見方をする。

よく考えると,d[i]の値が同じやつは,一緒に考えても良いことがわかる。例えばd={1,1,2}のとき,先ほどと同じように1桁目を見て9で割ったあまりがどのように遷移するか…とやっても良いが,d[i]=1のもの(2つある)を全部まとめて「2つの数字の和を9で割ったあまりが0〜8になるのはそれぞれ何通りあるか？」を考えて,それを計算した後にそれを上手く利用して場合の数を計算すると早そう。実際,この求め方で解くと,状態が32通りしかないので,先ほどとほとんど変わらない計算量で解ける。説明が下手すぎですみません…

以下ソースコード

const ll MOD = 1e9+7;
ll dp[40][9*9*9*9*9];
ll dp2[5010][9];
int dtime[40];
int pow9[6];

ll g(int t, int cur) {
    if (t == 0) {
        if (cur == 0) return 1;
        else return 0;
    }
    ll& ret = dp2[t][cur];
    if (ret == -1) {
        ret = 0;
        for (int i = 0; i <= 9; i++) {
            ret += g(t-1, (cur+9-i)%9);
        }
        ret %= MOD;
    }
    return ret;
}

ll f(int cur, int p) {
    if (cur == 32) {
        if (p == 0) return 1;
        else return 0;
    }
    ll& ret = dp[cur][p];
    if (ret == -1) {
        ret = 0;
        for (int i = 0; i < 9; i++) {
            int np = 0;
            for (int j = 4; j >= 0; j--) {
                int o = (p/pow9[j])%9;
                if ((cur>>j)&1) {
                    o = (o+i)%9;
                }
                np = 9*np+o;
            }
            ret += (f(cur+1, np) * g(dtime[cur], i)) % MOD;
        }
        ret %= MOD;
    }
    return ret;
}

class Nine {
public:
    int count(int N, vector <int> d) {
        // 初期化
        memset(dp, -1ll, sizeof(dp));
        memset(dp2, -1ll, sizeof(dp2));
        memset(dtime, 0, sizeof(dtime));
        for (int el : d) {
            dtime[el]++;
        }
        pow9[0] = 1;
        for (int i = 0; i < 5; i++) pow9[i+1] = pow9[i]*9;
        return f(0, 0);
    }
};