luogu1357花园（矩阵运算）（状压DP）

不得不说本蒻做这个题目的时候内心是很蒙蔽的qwq

推了规律找错了结果还没有暴力的分数高qwq......

开数组\(f[i][j]\)来记录前i个花圃，（这里运用到状压的思想）其中最近的m个的状态（二进制，1表示C，0表示P），然后因为这个状态是可以递推下一个状态的（比如说1_m到2m+1），然后我们发现每一次的状态转移都可以用同一个矩阵实现，那么该题目就可以用矩阵快速幂来加速计算。因为题目中是一个环状，那么转换n次一定还是原先的状态。那么题目就转换成了一个合法状态（这个需要预先判断出来）转移n次到自己的方案数量qwq。f数组的第一维也不需要了，那么直接\(f[j]\)乘以矩阵的n次方依次累加就是答案数量了qwq

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

const int M=5,p=1000000007;

long long n,m,k,ans=0;

long long f[1<<M],a[1<<M][1<<M];

int MAX,cnt;

bool pd[1<<M];

inline void mulself(long long a[1<<M][1<<M]) {

    long long c[1<<M][1<<M];

    memset(c,0,sizeof(c));

    for(int i=0;i<MAX;++i)

        for(int j=0;j<MAX;++j)

            for(int k=0;k<MAX;++k)

                c[i][j]=(c[i][j]+a[i][k]*a[k][j])%p;

    memcpy(a,c,sizeof(c));

}

inline void mul(long long f[1<<M],long long a[1<<M][1<<M])

{

    long long c[1<<M];

    memset(c,0,sizeof c);

    for(int j=0;j<MAX;++j)

        for(int k=0;k<MAX;++k)

            c[j]=(c[j]+f[k]*a[k][j])%p;

    memcpy(f,c,sizeof(c));

}

//以上是矩阵乘法的内容

int main() {

    scanf("%lld%lld%lld",&n,&m,&k);

    MAX=1<<m;

    //最大的情况统计

    for(int i=0;i<MAX;++i) {

        cnt=0;

        for(int j=0;j<m;++j)

            if(i&1<<j)++cnt;

        if(cnt<=k) pd[i]=true;

        //记录合法方案

    }

    for(int i = 0; i < MAX; ++i)

        if(pd[i]) //这个是合法状态

		{

            memset(f,0,sizeof(f));

			f[i]=1;//初始化该状态的方案数为1

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

            for(int j=0;j<MAX;++j) //搜寻转移的下一个状态

				if(pd[j])//如果这个状态合法

                	a[j>>1][j]=1,a[(j>>1)+(1<<(m-1))][j]=1;//记录状态之间转移是合法的

					//进行矩阵快速幂加速运算

            for(long long y=n;y;y>>=1,mulself(a))

                if(y&1)

                    mul(f,a);

            ans=(ans+f[i])%p;//统计答案

         }

    printf("%lld\n", ans);

    return 0;

}

巴特西

luogu1357花园（矩阵运算）（状压DP）

最新文章

热门文章