nyoj1273 河南省第九届省赛_"宣传墙"、状压DP+矩阵幂加速

宣传墙

时间限制:1000 ms  |  内存限制:65535 KB
难度:4
描述

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

nyoj1273  河南省第九届省赛_"宣传墙"、状压DP+矩阵幂加速


输入
第一行: 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
来源
河南省第九届省赛
上传者
onlinejudge
N高达100w,继续使用前面做这个题目直接状压DP得话复杂度太高(16*16*100w),再算上常数..显然会TLE
这时候引入了矩阵的概念...总感觉莫名其妙的虽然会用但是自己没想到要这样子写
我们在dp时dp[cur][S]得值由dp[last][S]决定,那么由哪些决定呢,last中的某些状态如果能与cur中的某个状态相容,我们就把last中这些满足匹配条件的
状态的方案数得和赋值给cur中的这个状态,一轮结束之后再由这个方法推cur+1的状态,最后的答案来自于dp[N][(1<<N)-1]
仔细观察,如果对于矩阵运算熟悉得话可能会自然而然的联系到这里,cur由last决定相当于让last中的每一项乘以一个1/0,显然匹配时乘1不匹配就是0喽,
转换一下思路我们就是让last数组运算了N(所有状态个数)次,每一次都是SUM(last[i]*(1/0)),然后将这个SUM赋值给cur对应的状态
其实不就是两个矩阵进行了一次乘的操作吗last为一个1*N的矩阵,1/0为一个N*N的关系矩阵,设这个关系矩阵为e,则e[i][j]==1表示状态i与j相容,反之相斥。
每次运算时关系矩阵并不会改变,因此就是在求这个关系矩阵的幂,利用矩阵快速幂求知即可。
为了方便我们把cur==0时的行向量表示为(0,0,0,......1)
这样对于一个询问M,我们只要求关系矩阵的N次方,答案就是a[maxn][maxn];
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define high ((1<<4)-1)
#define MOD 997
int e[20][20];
int fir[20];
bool check(int x,int i)
{  return x&(1<<i); }
int comp(int A,int B,int N)
{
 int i=0,j,k;
 while(i<N){
    if(!check(A,i)){
        if(!check(B,i)) return 0;
        i++;
    }
    else{
        if(!check(B,i)) i++;
        else {
            if(i==N-1||!check(A,i+1)||!(check(A,i+1)&&check(B,i+1))) return 0;
            else i+=2;
        }
    }
 }
 return 1;
}
void init()
{
    int i,j,k;
    for(i=0;i<=high;++i){
        for(j=0;j<=high;++j){
            e[i][j]=comp(j,i,4);
        }
    }
    for(i=0;i<=high;++i) fir[i]=1;
}
struct Martix
{
    int a[18][18];
    Martix(){memset(a,0,sizeof(a));}
};

Martix mul(Martix A,Martix B)
{
    Martix tmp;
    int i,j,k;
    for(i=0;i<=15;i++){
        for(k=0;k<=15;++k){
            for(j=0;j<=15;++j){
                tmp.a[i][j]+=A.a[i][k]*B.a[k][j];
                tmp.a[i][j]%=997;
            }
        }
    }
    return tmp;
}

Martix qpow(Martix tmp,int num)
{
    Martix res;
    memset(res.a,0,sizeof(res.a));
    for(int i=0; i<16; i++) res.a[i][i]=1;
    while(num)
    {
        if(num&1) res=mul(res,tmp);
        tmp=mul(tmp,tmp);
        num>>=1;
    }
    return res;
}
int solve(int N)
{
    Martix ans;
    for(int i=0;i<=15;++i){
        for(int j=0;j<=15;++j){
            ans.a[i][j]=e[i][j];
        }
    }
    ans=qpow(ans,N);
    int p=0;
    return ans.a[15][15];
}
int main()
{
    int N,M,K,i,j,k,t;
    init();
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&N,&M,&K);
        printf("%d %d\n",solve(M-1),solve(N-(M+K-1)));
    }
    return 0;
}

上一篇:状压DP详解+题目


下一篇:MySQL初步研究数据库