Submission #3403828

---

Source Code Expand

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

template<typename T> inline bool chkmin(T &a, T b) {return b < a ? a = b, 1 : 0;}
template<typename T> inline bool chkmax(T &a, T b) {return b > a ? a = b, 1 : 0;}

inline int read() {
    int x(0), sgn(1); char ch(getchar());
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
    for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
    return x * sgn;
}

void File() {
#ifdef zjp_shadow
	freopen ("E.in", "r", stdin);
	freopen ("E.out", "w", stdout);
#endif
}

const int N = 41, Mod = 1e9 + 7, All = (1 << 17) - 1;

int dp[N][All + 1];
bitset<All + 1> ban;

inline int Up(int val, int pos) {
	return val | (1 << (pos - 1));
}

int main() {

	File();

	int n = read(), X = read(), Y = read(), Z = read(), tmp = Up(Up(Up(0, Z), Y + Z), X + Y + Z);

	For (i, 0, All)
		ban[i] = (i | tmp) == i;

	dp[0][0] = 1;
	For (i, 0, n - 1) For (j, 0, All) 
		if (!ban[j] && dp[i][j])
			For (dig, 1, 10)
				(dp[i + 1][All & Up(j << dig, dig)] += dp[i][j]) %= Mod;

	int ans = 0;
	For (i, 1, All) if (!ban[i])
		(ans += dp[n][i]) %= Mod;

	int fac = 1;
	For (i, 1, n)
		fac = fac * 10ll % Mod;

	printf ("%d\n", (fac - ans + Mod) % Mod);
	
#ifdef zjp_shadow
	cerr << (double)clock () / CLOCKS_PER_SEC << endl;
#endif

    return 0;

}

Submission Info

Judge Result