Atcoder ARC058E Iroha and Haiku

题目中的式子转化一下即存在一位 \(i\) 使得到 \(i\) 时的后缀和存在 \(X + Y + Z, Y + Z, Z\)，再发现 \(X + Y + Z\le 17\)，考虑状压。

设 \(f_{i, j}\) 为填了 \(i\) 个数当前后缀和中存在的数的状态为 \(j\)（只存 \(0\sim X + Y + Z\) 的数是否存在）的方案数。
考虑转移，则下一位可以填上 \(1\sim 10\) 的数，对应的后缀和就应左移对应位数同时 \(+1\) 代表存在后缀为 \(0\)，\(f_{i + 1, j\times 2^d + 1}\leftarrow f_{i + 1, j\times 2^d + 1} + f_{i, j}(1\le j\le 10)\)。

统计答案考虑若在第 \(i\) 个数满足条件就直接加上答案不继续往后转移，否则可能会算漏一部分。
当 \(j\) 对应的存在状态中已存在 \(X + Y + Z, Y + Z, Z\) 时，后面的 \(n - i\) 位就可以任意填了，对应的方案数就为 \(f_{i, j}\times 10^{n - i}\)，对所有满足条件的状态按照此式子求和即可。

时间复杂度 \(O(nW\times 2^{X + Y + Z})\)，\(W\) 为值域，此题为 \(10\)。

// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: E - Iroha and Haiku
// Contest: AtCoder - AtCoder Regular Contest 058
// URL: https://atcoder.jp/contests/arc058/tasks/arc058_c
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int N = 40 + 2, M = 18;
int f[N][1 << M];
int p10[N];
const int mod = 1e9 + 7;
int main() {
	p10[0] = 1;
	for (int i = 1; i <= 40; i++) {
		p10[i] = 1ll * p10[i - 1] * 10 % mod;
	}
	int n, X, Y, Z;
	scanf("%d%d%d%d", &n, &X, &Y, &Z);
	int lim = (1 << (X + Y + Z + 1)) - 1, orz = (1 << (X + Y + Z)) | (1 << (Y + Z)) | (1 << Z);
	int ans = 0;
	f[0][1] = 1;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= lim; j++) {
			if ((j & orz) == orz) {
				ans = (ans + 1ll * f[i][j] * p10[n - i] % mod) % mod;
				continue;
			}
			for (int s = 1; s <= 10; s++) {
				f[i + 1][(j << s | 1) & lim] = (f[i + 1][(j << s | 1) & lim] + f[i][j]) % mod;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}