[LuoguP1357] 花园

暴力 DP

首先有一个暴力状压 DP, 表示以第 个花盆结尾,后 个花盆的二进制状态为 (1 为 C,0 为 P)时的方案数

对于环形的处理,我们让两个相同状态作为 DP 的初始和结尾即可.具体的说,初始化 ,表示第 的花盆的状态为 ,目标 (n,0 重合)

其中 表示 k 可以转移到 j.

#include<cstdio>
#include<cstring>
#define int long long
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
const int N=1e5,M=5,P=1000000007;
int n,m,k,ans;
int f[N][1<<M];
int s[1<<M],cnt;// 可行状态集
bool v[1<<M][1<<M];
void pre_work(){//v[i,j]=1 表示可以从 s[i] 转移到 s[j]
    int m2=(1<<m)-1;
    FOR(i,0,m2)if((i&1)+(i>>1&1)+(i>>2&1)+(i>>3&1)+(i>>4&1)<=k)s[++cnt]=i;
    FOR(i,1,cnt)FOR(j,1,cnt)if((s[i]<<1&m2)==(s[j]&(m2-1)))v[i][j]=1;
}
int calc(int st){
    memset(f,0,sizeof(f));
    f[0][st]=1;
    FOR(i,1,n)FOR(j,1,cnt)FOR(k,1,cnt)
        if(v[k][j])f[i][j]=(f[i][j]+f[i-1][k])%P;
    return f[n][st];
}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    pre_work();
    FOR(i,1,cnt)(ans+=calc(i))%=P;
    printf("%lld",ans);
    return 0;
}

矩阵优化

本题 ,显然不能直接 DP,则只有矩阵优化. 改写方程

忽略第一维

则把 当作 的矩阵, 当作 的矩阵,俨然一个矩阵乘法模型

这是一次转移,而一共转移 次,于是给 来一个矩阵 次快速幂;

最后统计答案,按我们之前的思路,每一次初始化 ,转移出来乘上矩阵的结果恰好为为 ,则整体的答案相当于 的对角线之和

本题解建立在这篇文章上

代码

#include<cstdio>
#include<cstring>
#define int long long
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
const int N=1e5,M=5,P=1000000007;
int n,m,k,ans;
int f[N][1<<M],s[1<<M],cnt;// 可行状态集
struct matrix{int c[1<<M][1<<M];};
matrix mt;
matrix operator*(matrix a,matrix b){// 定义矩阵乘法
    matrix c;
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=cnt;j++){
            c.c[i][j]=0;
            for(int k=1;k<=cnt;k++)(c.c[i][j]+=a.c[i][k]*b.c[k][j])%=P;
        }
    }
    return c;
}
matrix ksm(matrix a,int m){
    matrix res=a;--m;
    while(m){
        if(m&1)res=res*a;
        a=a*a,m>>=1;
    }
    return res;
}
void pre_work(){
    int m2=(1<<m)-1;
    FOR(i,0,m2)if((i&1)+(i>>1&1)+(i>>2&1)+(i>>3&1)+(i>>4&1)<=k)s[++cnt]=i;
    FOR(i,1,cnt)FOR(j,1,cnt)if((s[i]<<1&m2)==(s[j]&(m2-1)))mt.c[i][j]=1;
}
signed main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    pre_work();// 计算 mt 矩阵
    mt=ksm(mt,n);//n 次幂计算
    for(int i=1;i<=cnt;i++)(ans+=mt.c[i][i])%=P;
    printf("%lld",ans);
    return 0;
}

  转载请注明: Sshwy's Blog [LuoguP1357] 花园

 上一篇
线段树初步 线段树初步
线段树基础线段树,是利用一个区间建立一个完全二叉树,来快速实现区间修改、查询操作。 例如,要求对序列 A{1,3,4,2,5,3,7,8} 进行如下两种操作: add(l,r,v): 把 [l,r] 的元素都增加 v sum(l,r):
2018.12.19
下一篇 
[SDOI2010] 地精部落 [SDOI2010] 地精部落
题意问 1-n 的排列中,峰谷交替的排列有多少个,答案对 P 取模。 峰谷交替:即对于一个排列中的任意一个数 ,满足以下条件之一: a_{i-1}>a_i using namespace std; const int N=420
2018.12.15
  目录