【AtCoder Regular Contest 058 E】Iroha and Haiku | Mrsrz's blog

状压DP。

题目大意：

给定 $n,X,Y,Z$，问有多少长度为 $n$ 的数列，满足：

• 数列中都是 $1\sim 10$ 的整数。
• 数列中存在一个连续子序列，这个子序列可以分成三个连续的部分，使得三部分的和依次是 $X,Y,Z$。

题解：

由于 $X,Y,Z$ 和 $X+Y+Z$ 都比较小，我们考虑状压。

对于 $x$，我们用二进制数 $2^{x-1}$ 表示（即 $1$ 后面跟 $x-1$ 个 $0$）。这样每个状态，我们都可以用若干个这样的数首尾相连得到。

不难发现，一个 $1$ 到它后面的某个 $1$ 之前（或到末尾）有多少位，就代表这中间的和是多少。有多少个 $1$ 就代表有多少个数。

那么，如果一个状态中第 $X+Y+Z$ 位、第 $Y+Z$ 位、第 $Z$ 位都是 $1$，则说明构成满足题目条件的子序列。

在后面加数，直接插入到尾部即可。开头超过 $X+Y+Z$ 的部分会自动溢出。

用状压 DP 计算不存在这样的段的情况。转移直接枚举插进去的数即可。

时间复杂度 $O(2^{X+Y+Z}n)$。

Code：

#include<cstdio>
const int md=1e9+7;
int n,x,y,z,dp[41][1<<18],ans=1;
inline void upd(int&a){a+=a>>31&md;}
int main(){
    scanf("%d%d%d%d",&n,&x,&y,&z);
    const int C=1<<(x+y+z-1)|(1<<(y+z-1))|(1<<z-1),ALL=(1<<x+y+z)-1;
    dp[0][0]=1;
    for(int i=1;i<=n;++i){
        ans=ans*10LL%md;
        for(int S=0;S<=ALL;++S)if(int k=dp[i-1][S])if((S&C)!=C)
        for(int w=1;w<=10;++w)upd(dp[i][(S<<w|(1<<(w-1)))&ALL]+=k-md);
    }
    for(int S=0;S<=ALL;++S)
    if((S&C)!=C)upd(ans-=dp[n][S]);
    printf("%d\n",ans);
    return 0;
}