王强路的模拟赛 T2 haiku

题面

给定一个长度为 $N$ 的序列 $a$，序列中的每个数都可以是 $1 \sim 10$ 中的某一个，总共有 $10^N$ 种序列，现在给出 $N,X,Y,Z$，问有多少个长度为$N$的序列满足其有四个下标 $x,y,z,w$ 使得

• $a[x]+a[x+1]+...+a[y-1]=X$
• $a[y]+a[y+1]+...+a[z-1]=Y$
• $a[z]+a[z+1]+...+a[w]=Z$

Sample Input

3 5 7 5

Sample Output

1

样例解释

在这组样例中，只存在一组合法的序列，即 $a = [5,7,5]$。

数据范围

$3 \le N \le 40$。

$1 \le X \le 5$，$1 \le Y \le 7$，$1 \le Z \le 5$。

题解

神题。。首先膜拜zyy大佬用AC自动机水了此题。

P.S.王强路应该不会说什么的对吧

直接说正解吧。。

很容易想到的方法枚举所有成立的序列 $a[x],a[x+1],a[x+2],...,a[z-1],a[z]$，然后计算其余位数随便取的方案数就行了。

但这样会有重复的出现。

注意到 $n$、$x$、$y$、$z$ 都很小，于是我们可以从第一位开始 dfs 枚举每一位取什么。

如果以当前位为 $z$，前面有符合条件的 $x$ 和 $y$ 的话，就可以直接加上后面几位随便取的方案数并返回。

这样就不会有重复计算的了。

那么问题就在于如何快速地算出有没有符合条件的 $x$、$y$、$z$ 了。

标算提供了一种状压的思路。

我们可以用"1"来代替1，"10"来代替2，"100"来代替3，以此类推。

拿样例 $x=5,y=7,z=5$ 来说，这样替换一个符合条件的数组 [2, 3, 2, 5, 1, 4] 即为 "10100101000011000"。

而 $xyz$ 组成的数组替换后即为"10000100000010000"。

可以注意到，两个 01 串的 & 值即为 $xyz$ 组成的 01 串。

这样就可以愉快地在$O(1)$的时间里判断是否满足条件啦。 具体可以看我程序。

#include "bits/stdc++.h"
#define mod 1000000007
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')ch=='-'&&(f=0)||(ch=getchar());
	while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return f?x:-x;
}
int f[41][1<<17], p[41];
int n, z, y, x, end_state;
int dfs(int i, int j){
	if (i == n) return 0;
	if (~f[i][j]) return f[i][j];
	long long res = 0;
	for (int k = 1; k <= 10; k++) {
		int next_state = (j << k) | (1 << k-1);
		res += ((next_state & end_state) == end_state)
			? p[n-i-1] : dfs(i+1, next_state & ((1 << x+y+z) - 1));
	}
	return f[i][j] = res%mod;
}
int main(int argc, char const *argv[]){
	freopen("haiku.in", "r", stdin);
	freopen("haiku.out", "w", stdout);
	memset(f, -1, sizeof(int)*5373952);
	n = read(); x = read(); y = read(); z = read(); p[0] = 1;
	for (int i = 1; i <= 40; i++) p[i] = p[i-1]*10ll%mod;
	end_state = (1 << x+y+z-1) | (1 << y+z-1) | (1 << z-1);
	printf("%d\n", dfs(0, 0));
	return 0;
}