很明显今天我闲的没事儿。
出于种种原因P5300RE了5个点所以待会儿再说，，
这道题是个好题。而且是个很简单的假黑题
思维1：考虑如何从前面答案得到后面答案（递推）
设f(i)表示n=i时的答案。
考虑又加了一列。
如果这一列直接用一个2x1竖着，那就为f(i-1);
如果这一列和上一列用两个1x2横着，那就是f(i-2)
这是不加单块的情况。
考虑单块放在了新的这一列中。
我们发现，单块和另一个单块所框出来的矩阵里面的放法时唯一确定的。依次交错的那种。
所以我们只需要枚举另一个单块的位置。不过这样会复杂度死亡。
我们设g(i)表示i列都用完整块放的方案数。我们发现这跟上面的假f是一样的，即斐波那契。
设h(i)表示g(i)的前缀和。即
那么
i-3是因为只有1列或者2列的时候是没有方案的。乘2是因为最后一个单块可以放上面或者下面。
其实到这个时候已经可以做了。但
事实上斐波那契前缀和
证明：
当n=1时，命题成立。
假设n=k时，命题成立。
则
得证。
所以原题中的f就可以表示为
矩阵快速幂随便乱搞就星。
#include<bits/stdc++.h>
using namespace std;
#define in read()
#define int long long
int in{
int cnt=0,f=1;char ch=0;
while(!isdigit(ch)){
ch=getchar();if(ch=='-')f=-1;
}
while(isdigit(ch)){
cnt=cnt*10+ch-48;
ch=getchar();
}return cnt*f;
}
int t,n;
const int mod=1e9+7;
struct node{
int a[7][7];
friend node operator *(node a,node b){
node ans;memset(ans.a,0,sizeof(ans.a));
for(int i=1;i<=5;i++){
for(int j=1;j<=5;j++){
for(int k=1;k<=5;k++){
ans.a[i][j]+=(a.a[i][k]*b.a[k][j]%mod);ans.a[i][j]%=mod;
}
}
}
return ans;
}
};
node ans,one;
node jzpow(node a,int b){
node gu;memset(gu.a,0,sizeof(gu.a));
for(int i=1;i<=5;i++)gu.a[i][i]=1;
while(b){
if(b&1)gu=gu*a;
b>>=1;a=a*a;
}return gu;
}
signed main(){
t=in;
while(t--){
int n=in;if(n<=2){
printf("0\n");continue;
}
ans.a[3][1]=ans.a[4][1]=ans.a[5][1]=1;ans.a[3][1]=2;ans.a[5][1]=1;
one.a[1][1]=one.a[1][2]=one.a[2][1]=one.a[3][3]=one.a[3][4]=one.a[4][3]=one.a[5][5]=1;
one.a[1][3]=2;one.a[1][5]=mod-2;
node sum=jzpow(one,n-2);//for(int i=1;i<=5;i++)cout<<sum.a[i][1]<<" ";cout<<endl;
sum=sum*ans;
printf("%lld\n",sum.a[1][1]);
}
return 0;
}
转载：https://blog.csdn.net/qq_42835815/article/details/102056676
查看评论