【题解】Luogu P1357 花园

原题传送门

我们先将花圃断环为链，并将\([1,m]\)复制一份到\([n+1,n+m]\)，最后要求\([1,n+m]\)是合法序列且\([1,m]\)与\([n+1,n+m]\)相等的序列的数量即可

\(m\)很小，珂以考虑状压，\(C\)是\(0\)，\(P\)是\(1\)，可以将长\(m\)的花圃压缩成一个数

我们先考虑\([1,m]\)的可行方法，直接暴力预处理

如何从\([1,m]\)转移到\([2,m+1]\)：设\([1,m]\)的状态为\(a\)，我们珂以将第一个数字删掉再在最后加一个\(0/1\)得到一个新状态\(b/c\)，连一条\(a->b/c\)的边（\(c\)要判断一下\(1\)的数量）

之后亦是如此。这样我们将问题转化为求一个有向图中长度为\(n\)的环的数量

这就珂以用矩阵快速幂优化了qwqwq

#include <bits/stdc++.h>

#define ll long long

#define mod 1000000007

#define N 32

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline ll read()

{

    register ll x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

struct mat{

    int a[N][N];

    inline mat()

    {

        memset(a,0,sizeof(a));

    }

    inline mat operator*(const mat&b)const{

        mat c;

        for(register int i=0;i<N;++i)

            for(register int j=0;j<N;++j)

                for(register int k=0;k<N;++k)

                    c.a[i][j]=(c.a[i][j]+1ll*a[i][k]*b.a[k][j])%mod;

        return c;

    }

}s;

inline mat fastpow(register mat a,register ll b)

{

    mat res;

    for(register int i=0;i<N;++i)

    	res.a[i][i]=1;

    while(b)

    {

        if(b&1)

            res=res*a;

        a=a*a;

        b>>=1;

    }

    return res;

}

ll n,ans;

int m,k,lim,ok[N];

inline void work(register int zt,register int num)

{

    ok[zt]=1;

    int kl=zt>>1;

    s.a[zt][kl]=1;

    if(num==k&&!(zt&1))

        return;

    s.a[zt][kl+(1<<(m-1))]=1;

}

inline void dfs(register int x,register int num,register int zt)

{

    if(x==m+1)

    {

        work(zt,num);

        return;

    }

    dfs(x+1,num,zt);

    if(num<k)

        dfs(x+1,num+1,zt|(1<<(x-1)));

}

int main()

{

    n=read(),m=read(),k=read();

    dfs(1,0,0);

    s=fastpow(s,n);

    for(register int i=0;i<(1<<m);++i)

        if(ok[i])

            ans=(ans+s.a[i][i])%mod;

    write(ans);

    return 0;

}

巴特西

【题解】Luogu P1357 花园

原题传送门

我们先将花圃断环为链，并将\([1,m]\)复制一份到\([n+1,n+m]\)，最后要求\([1,n+m]\)是合法序列且\([1,m]\)与\([n+1,n+m]\)相等的序列的数量即可

\(m\)很小，珂以考虑状压，\(C\)是\(0\)，\(P\)是\(1\)，可以将长\(m\)的花圃压缩成一个数

我们先考虑\([1,m]\)的可行方法，直接暴力预处理

如何从\([1,m]\)转移到\([2,m+1]\)：设\([1,m]\)的状态为\(a\)，我们珂以将第一个数字删掉再在最后加一个\(0/1\)得到一个新状态\(b/c\)，连一条\(a->b/c\)的边（\(c\)要判断一下\(1\)的数量）

之后亦是如此。这样我们将问题转化为求一个有向图中长度为\(n\)的环的数量

这就珂以用矩阵快速幂优化了qwqwq

最新文章

热门文章