Submission #3770463

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007ll

int N, X, Y, Z;
int dp[50][1 << 17];
int p;

int pou(int a, int b)
{
    int tmp = 1;
    for(int i = 0; i < b; i++){
        tmp = a * tmp % mod;
    }
    return tmp % mod;
}

int dfs(int pos, int bit)
{
    if(~dp[pos][bit]){
        return dp[pos][bit];
    }
    if((bit >> X + Y + Z - 1ll) & 1ll){
        if((bit >> Y + Z - 1ll) & 1ll){
            if((bit >> Z - 1ll) & 1ll){
                return dp[pos][bit] = 0ll;
            }
        }
    }
    if(pos == N){
        return dp[pos][bit] = 1ll;
    }
    //if(bit & (1ll << (p - 1ll))){
    //    bit ^= (1ll << (p - 1ll));
    //}
    int res = 0ll;
    for(int i = 1ll; i <= 10ll; i++){
        res = (res + dfs(pos + 1ll, ((bit << i) | (1ll << i - 1ll)) & ((1 << p) - 1))) % mod;
    }
    return dp[pos][bit] = res;
}

signed main()
{
    cin >> N >> X >> Y >> Z;
    p = X + Y + Z;
    memset(dp, -1ll, sizeof(dp));
    cout << (pou(10ll, N) - dfs(0ll, 0ll) + mod) % mod << endl;


    return 0;
}

Submission Info

Judge Result