宣传墙
时间限制：1000 ms | 内存限制：65535 KB
难度：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
- 来源
- 河南省第九届省赛
- 上传者
- 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 ",solve(M-1),solve(N-(M+K-1)));
}
return 0;
}