ARC058 E - 和風いろはちゃん

問題文

http://arc058.contest.atcoder.jp/tasks/arc058_c

解法

X, Y, Z が小さいので bitDP でやります．
dp[i][S] := i 番目まで見たときに，直前の和が X + Y + Z 以下になるところまでの状態が S であるような場合の数
とします．
たとえば，X = 5, Y = 7, Z = 5 のときに，"575" という状態を "10000 1000000 10000" という (X + Y + Z) ビットからなる列として表します．
XYZ であるか，という状態は，よく考えると下から Z ビット目，(Z + Y) ビット目，(X + Y + Z) ビット目が 1 になっているか，という問と同じなので，そういうマスクを作っておけば判定は簡単です．
過去に XYZ を含んだ数列は次からは任意の数を取って良いので，その数列を特別な場所に保存しておくと単に 10 倍するだけで済みます．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr int mod = 1e9 + 7;

int main() {
    int N, X, Y, Z;
    cin >> N >> X >> Y >> Z;
    int const M = 1 << (X + Y + Z);
    vector<vector<ll>> dp(N + 1, vector<ll>(M + 1));
    int const mask = (1 << (Z - 1)) | (1 << (Z + Y - 1)) | (1 << (Z + Y + X - 1));
    dp[0][0] = 1;

    for(int i = 0; i < N; ++i) {
        for(int S = 0; S < M; ++S) {
            if(dp[i][S] == 0) {
                continue;
            }
            for(int j = 1; j <= 10; ++j) {
                int nS = ((S << j) | (1 << (j - 1))) & (M - 1);
                if((nS & mask) == mask) {
                    (dp[i + 1][M] += dp[i][S]) %= mod;
                } else {
                    (dp[i + 1][nS] += dp[i][S]) %= mod;
                }
            }
        }
        (dp[i + 1][M] += dp[i][M] * 10) %= mod;
    }
    cout << dp[N].back() << endl;
}

感想

bitDP だとわかれば簡単（ほんまか？）