SRM 655 div2 hard:NineEasy

汚いコード。

問題:TopCoder Statistics - Problem Statement

解法:dp[keta][x1][x2][x3][x4][x5]=(keta目で1つ目の質問に対する答え(つまり9で割ったあまり)がx1で,2つ目の質問に対する答えがx2で…　であるような場合の数)とする。
すると,非常に汚い漸化式ができるのでそれを実行する。
状態量はD*(9^N)で,各状態に対して10*Nの計算量がかかるのでO(6*10^7)ぐらいで,結構危ないがなんとか間に合った。
以下ソースコード

const ll MOD = 1e9+7;

ll dp[22][9][9][9][9][9];

class NineEasy {
public:
    int count(int N, vector <int> d) {
        int keta = d.size();
        memset(dp, 0, sizeof(dp));
        dp[0][0][0][0][0][0] = 1;
        for (int i = 0; i < keta; i++) {
            for (int x1 = 0; x1 < 9; x1++) for (int x2 = 0; x2 < 9; x2++) for (int x3 = 0; x3 < 9; x3++) for (int x4 = 0; x4 < 9; x4++) for (int x5 = 0; x5 < 9; x5++) {
                if (dp[i][x1][x2][x3][x4][x5] == 0) continue;
                for (int j = 0; j < 10; j++) {
                    // i桁目はjにする
                    int n1=x1, n2=x2, n3=x3, n4=x4, n5=x5;
                    for (int k = 0; k < N; k++) {
                        if ((d[i]>>k)&1) {
                            if (k==0) n1 = (n1+j)%9;
                            if (k==1) n2 = (n2+j)%9;
                            if (k==2) n3 = (n3+j)%9;
                            if (k==3) n4 = (n4+j)%9;
                            if (k==4) n5 = (n5+j)%9;
                        }
                    }
                    dp[i+1][n1][n2][n3][n4][n5] += dp[i][x1][x2][x3][x4][x5];
                    dp[i+1][n1][n2][n3][n4][n5] %= MOD;
                }
            }
        }
        return dp[keta][0][0][0][0][0];
    }
};