E - 和風いろはちゃん / Iroha and Haiku

E - 和風いろはちゃん / Iroha and Haiku

余事象を考えるとわかりやすい
桁毎に全探索するメモ化で解く
ある桁iで使える数vは、iを右端としたときに575とならないようなvだが
これは右端から数の累積和を取ってbitに持たせれば575になるか判定できる
18以上の累積和をもつ必要はないためbitでもてる

int mem[44][1 << 19];
int ng;

mint rec(int i, int m) {
    if (i == n)return 1;
    int &res = mem[i][m];
    if (res >= 0)return res;
    res = 0;
    rep(v, 1, 11) {
        int tm = (m << v) + bit(v);
        tm &= bit(18) - 1;
        if ((tm & ng) != ng)res += rec(i + 1, tm);
    }
    return res;
}
signed main() {
    cin >> n >> x >> y >> z;
    setMod();
    fill(mem, -1);
    ng |= bit(z);
    ng |= bit(z + y);
    ng |= bit(z + y + x);
    cout << mpow(10, n) - rec(0, -0) << endl;
    return 0;
}