ARC 058 E Iroha and Haiku

• 长度为 \(n\le 40\) 的序列中，每个数属于 \(1...10\)，求出存在序列中存在连续的三段，数字和分别为 \(x\le 5,y\le 7,z\le 5\) 的序列个数。

考虑容斥，求出不存在连续的三段和分别为 \(x,y,z\) 的个数。

由于 \(x + y + z \le 17\)，可以状压当前的所有位置的后缀和，第 \(i\) 为 \(1\)，代表存在一个后缀和为 \(i + 1\)。

设 \(f_{i,s}\) 表示当前后缀和的情况为 \(s\)，不存在后缀满足 \(x + y + z - 1, y + z - 1, z - 1\) 这三位同时为 \(1\) 的方案数。

当加入一个数 \(k\) 时，只需将 \(s\) 左移 \(k\) 位，并在 \(k - 1\) 位赋值为 \(1\)，当一个后缀和大于 \(x + y + z - 1\) 时之和也一定合法，就不需要再考虑。

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define fi first
#define se second
using namespace std;

typedef long long LL;
typedef pair <int, int> P;
const int inf = 0x3f3f3f3f, N = 55, mod = 1e9 + 7;
template <typename T>
void rd_(T &x) {
	x = 0; int f = 1;
	char ch = getchar();
	for (; ch > ‘9‘ || ch < ‘0‘; ch = getchar()) if (ch == ‘-‘) f = -1;
	for (; ch >= ‘0‘ && ch <= ‘9‘; ch = getchar()) x = x*10 + ch - ‘0‘;
	x *= f;
}

int n, x, y, z, f[N][1<<17], S, ed, ans = 1;

int main() {
	rd_(n), rd_(x), rd_(y), rd_(z);
	S = (1<<x + y + z) - 1, ed = (1<<x + y + z - 1) + (1<<y + z - 1) + (1<<z - 1);
	f[0][0] = 1;
	rep (i, 0, n - 1) {
		ans = 10ll*ans%mod;
		rep (s, 0, S) 
			if (f[i][s]) {
				rep (j, 1, 10) {
					int t = ((s<<j) + (1<<j - 1))&(S);
					if ((ed&t) == ed) continue;
					f[i + 1][t] = (f[i + 1][t] + f[i][s])%mod;
				}
			}
	}
	rep (i, 0, S)
		ans = (ans - f[n][i])%mod;
	cout<<(ans + mod)%mod<<endl;
}

ARC 058 E Iroha and Haiku

原文：https://www.cnblogs.com/ympc2005/p/14322048.html