http://nyoj.top/problem/1273

状压dp+矩阵快速幂+dfs

 

1273-宣传墙

 

• 内存限制:64MB 时间限制:1000ms 特判: No

• 
  
• 通过数:19 提交数:64 难度:4

题目描述:

ALPHA 小镇风景美丽，道路整齐，干净，到此旅游的游客特别多。CBA 镇长准备在一条道路南 面 4*N 的墙上做一系列的宣传。为了统一规划，CBA 镇长要求每个宣传栏只能占相邻的两个方格 位置。但这条道路被另一条道路分割成左右两段。CBA 镇长想知道，若每个位置都贴上宣传栏， 左右两段各有有多少种不同的张贴方案。 例如： N=6，M=3, K=2, 左，右边各有 5 种不同的张贴方案 

---

 

输入描述:

第一行： T 表示以下有 T 组测试数据 （ 1≤T ≤8 ）
接下来有T行， 每行三个正整数 N M K 分别表示道路的长度，另一条道路的起点和宽度
（1≤ N ,M ≤ 1 000 000, 1≤ K ≤ 100000）

输出描述:

每组测试数据，输出占一行：两个整数，分别表示左右两段不同的张贴方案数。由于方案总数
可能很大，请输出对 997 取模后的结果。

样例输入:

复制

2
6 3 2
5 3 2

样例输出:

5 5
5 1

 一开始按poj铺砖块的裸题写），直接与处理1e6的答案，tle了。

然后把1e6的数据粘在数组里交，告诉我代码太长。。。

然后发现只有4行，那么直接把所有的可能转移的状态都写出来，题目放过了这种做法。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 997;
const int max_n= 1e6+5;
int dp[max_n][1<<4];
int main(){
    dp[0][0]=1;
    for(int i=0;i<=1e6+1;i++){
        dp[i+1][0]=(dp[i+1][0]+dp[i][0]+dp[i][3]+dp[i][9]+dp[i][12]+dp[i][15])%mod;
        dp[i+1][3]=(dp[i][0]+dp[i][12]+dp[i+1][3])%mod;
        dp[i+1][9]=(dp[i][0]+dp[i][6]+dp[i+1][9])%mod;
        dp[i+1][12]=(dp[i+1][12]+dp[i][0]+dp[i][3])%mod;
        dp[i+1][15]=(dp[i][0]+dp[i+1][15])%mod;
        dp[i+1][6]=(dp[i+1][6]+dp[i][9])%mod;
    }
    int T;cin>>T;
    while(T--){
       int n,m,k;cin>>n>>m>>k;
       int a=m-1;
       int b=n-a-k;
       cout<<dp[a][0]<<' '<<dp[b][0]<<endl;
    }
    return 0;
}

如果不是4行，而是x行，如果n到达1e10，只有用矩阵快速幂+dfs+状压dp了。

通过上面发现f(n)的每一个状态都是由f(n-1)的每一个状态转移而来，那么就直接上矩阵快速幂

用dfs构造转移的矩阵。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 997;
const int max_n= 1e6+5;
LL nn;
struct mat{
    LL m[17][17];
};
mat unit,init; //单位矩阵
mat matmul(mat a,mat b){
    mat re;
    memset(re.m,0,sizeof(re.m));
    for(int i=0;i<nn;i++){
        for(int j=0;j<nn;j++){
            for(int k=0;k<nn;k++){
                re.m[i][j]=(re.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
            }
        }
    }
    return re;
}
mat quickmod(LL x,mat jin){
    mat re;
    memset(re.m,0,sizeof(re.m));
    for(int i=0;i<nn;i++) re.m[i][i]=1;
    while(x){
        if(x&1)
            re=matmul(re,jin);
        x=x>>1;
        jin=matmul(jin,jin);
    }
    return re;
}

void dfs(int j,int h,int st,int toth){ //前一列满，当前列二进制是j，后一列二进制是st
    if(h==toth+1) {     //递归出口
        unit.m[st][j]=1; //构造矩阵。
        return ;
    }
    if((j&(1<<(h-1)))>0) {  //当前行不能放
        dfs(j,h+1,st,toth);return;
    }
    if(h==toth){        //最后一行只能横着放
        dfs(j,h+1,st+(1<<(h-1)),toth);
        return ;
    }
    dfs(j,h+1,st+(1<<(h-1)),toth);
    if((j&(1<<(h)))==0)  //竖着放
        dfs(j,h+2,st,toth);
}
int main(){
    memset(unit.m,0,sizeof(unit.m)); //单位矩阵
    for(int i=0;i<1<<4;i++){
        dfs(i,1,0,4);
    }
    memset(init.m,0,sizeof(init.m)); //初始矩阵
    init.m[0][0]=1;
    int T;cin>>T;
    while(T--){
       int n,m,k;cin>>n>>m>>k;
       int a=m-1;
       int b=n-a-k;
       nn=1<<4;
       mat ans1=quickmod(a,unit);
       ans1=matmul(init,ans1);
       mat ans2=quickmod(b,unit);
       ans2=matmul(init,ans2);
       cout<<ans1.m[0][0]<<' '<<ans2.m[0][0]<<endl;
    }
    return 0;
}