洛谷1357 花园

题意

要求构造一个长度为 $n(\le 10^{15})$ 的 $0/1$ 环形序列，满足任意连续 $m(2\le m \le 5)$ 个数的和不超过 $k$ 。求方案数。

题解

$m$ 比较小，可以状压。可以发现答案其实就是把一个状态往后推 $n$ 次，最后回到自己的方案数。

两个状态之间的转移关系 $s[i][j]$ 可以提前预处理出来，然后把 $s$ 看成一个矩阵，合法状态 $i$ 对答案的贡献就是 $s^n[i][i]$ 。

注意：因为矩阵下标从 $0$ 开始，所以也要相应的改构造函数。

#include<bits/stdc++.h>
#define ll long long
#define ha 1000000007

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

struct matrix {
    ll n,s[32][32];
    matrix (ll len=-1) {
        n=len;
        memset(s,0,sizeof(s));
        for (ll i=0;i<=n;i++) s[i][i]=1;
    }
    matrix operator * (const matrix &x) const {
        matrix y; y.n=n;
        for (ll i=0;i<=n;i++)
            for (ll j=0;j<=n;j++)
                for (ll k=0;k<=n;k++)
                    y.s[i][j]=(y.s[i][j]+s[i][k]*x.s[k][j]%ha)%ha;
        return y;
    }
} x;
bool ok[32];
ll n,m,k,M;

inline void work(ll cnt,ll cur)
{
    ok[cur]=1;
    ll lst=cur>>1; //上一个状态
    x.s[lst][cur]=1;
    if (cnt==k && !(cur&1)) return; //不能再放1了
    x.s[lst|(1<<(m-1))][cur]=1;
}

void dfs(ll x,ll cnt,ll cur) //用dfs枚举当前状态
{
    if (x==m+1) return work(cnt,cur);
    dfs(x+1,cnt,cur);
    if (cnt<k) dfs(x+1,cnt+1,cur|(1<<(x-1)));
}

inline matrix qpow(ll y)
{
    matrix ans(M-1);
    while (y)
    {
        if (y&1) ans=ans*x;
        y>>=1;
        x=x*x;
    }
    return ans;
}

signed main()
{
    n=read(); m=read(); k=read();
    M=1<<m; x.n=M-1;
    dfs(1,0,0);
    matrix res=qpow(n);
    ll ans=0;
    for (ll i=0;i<M;i++) ans=(ans+res.s[i][i])%ha;
    return !printf("%lld",ans);
}