AtCoder

Luogu

分析

奇妙的状压 DP 。

首先注意到 $X+Y+Z\leq 17$ ,于是可以考虑状压。

具体的状压方式比较神仙:我们把每个后缀和的位置设成 $1$ 。

把给出的俳句表示成 $2^{Z-1}+2^{Y+Z-1}+2^{X+Y+Z-1}$ 的形式,于是可以发现,如果序列 $S$ 合法,那么 $S$ 与俳句的与就等于俳句。

这样子就比较简单了。我们考虑求出不合法方案数的再用 $10^{X+Y+Z}$ 减掉它。

设 $dp_{i,S}$ 表示前 $i$ 个数,最近的 $17$ 为的状态是 $S$ 的不合法方案数,转移枚举在后面加什么数即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int mod=1e9+7;
inline int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,X,Y,Z;
int dp[45][1<<17];

int main() {
    n=read(),X=read(),Y=read(),Z=read();
    int Haiku=(1<<(Z-1))|(1<<(Y+Z-1))|(1<<(X+Y+Z-1));
    int lim=(1<<(X+Y+Z))-1;
    dp[0][0]=1;
    for (re int i=0;i<n;++i)
        for (re int S=0;S<=lim;++S) {
            if (!dp[i][S]) continue;
            for (re int j=1;j<=10;++j) {
                int T=((S<<j)|(1<<(j-1)))&lim;
                if ((T&Haiku)!=Haiku)
                    dp[i+1][T]=(dp[i+1][T]+dp[i][S])%mod;
            }
        }
    int ans=0;
    for (re int i=0;i<=lim;++i) ans=(ans+dp[n][i])%mod;
    printf("%d\n",(qpow(10,n)-ans+mod)%mod);
    return 0;
}
最后修改:2019 年 10 月 13 日 08 : 04 PM