标签：AtCoder ARC058 le Contest Iroha 058 序列 统计
题意：
对于所有长度为\(n\),每个数在1到10之间的序列，问有多少个中包含一字串，满足字串可以分为三段和恰好为\(x,y,z\)的部分
数据满足：
\[3 \le n \le 40 ,
1 \le x \le 5 ,
1 \le y \le 7,
1 \le z \le 5,
\]
思路
正向统计有多少个序列满足会遇到重复统计的问题，难以克服，考虑统计统计非法序列总数
注意到 \(x+y+z \le 17\)
则考虑用状压表示一个序列尾部所能表示的所有数字
下以二进制举例：
对于序列
2 3 1 2
其状态为 \(10100110\)
即从尾部来看，其和可以表示为
2 3 6 8
记当前序列状态为\(k\)
则合法状态为 $k \& ((1 << (z-1)) | (1 << (z+y-1)) | (1 << (z+y+x-1))) = ((1 << (z-1)) | (1 << (z+y-1)) | (1 << (z+y+x-1))) \(
假设添加了一个新的数\)j\(
\)k\(变成\)(k<<j)|(1<<(j-1))$
转移统计即可
点击查看代码
```cpp
void solve(){
ll x , y , z , n;
cin >> n >> x >> y >> z;
ll lg = (1ll << (z-1)) + (1ll << (y+z-1)) + (1ll << (x+y+z-1)) , maxn = (1ll << (x+y+z));
dp[0][0] = 1;
for (int i = 1 ; i <= n ; ++i){
for (ll j = 1 ; j <= 10 ; ++j){
for (ll k = 0 ; k <= maxn ; ++k){
ll tmp = (k << j)|(1ll << (j-1));
tmp %= maxn;
if ((tmp&lg) == lg) continue;
dp[tmp][i] += dp[k][i-1];
dp[tmp][i] %= mod;
}
}
}
ll ans = quick_pow(10 , n)%mod;
for (ll k = 0 ; k <= maxn ; ++k){
ans = ((ans-dp[k][n])%mod+mod)%mod;
}
cout << ans << "\n";
}
```
标签：AtCoder,
ARC058,
le,
Contest,
Iroha,
058,
序列,
统计
From： https://www.cnblogs.com/happyalg/p/18673868