题意：
要求在nxm的棋盘上放置小象，要求没有小象互相攻击；
小象的攻击方式如下所示；
求在棋盘上有多少摆放的方式；
1<=n<=100000000，1<=m<=7；
题解：
数据范围出卖了做法。。。
7有啥做法。。状压。。
一亿怎么做。。log。。
然后这题就是状压+矩乘的递推咯，，复杂度在5s内是可以跑出来的；
首先就是如何构造矩阵；
实际上还是求出那些状态之间可以互相转移，然后拿临界矩阵去乘；
对于两个状态来说，如果有斜对角相连的小象，并且没有将其连起来的小象的话，二者就互相攻击；
依据这个建立矩阵就可以了，复杂度O(128*128)；
然后矩乘模板一上就完了；
时间复杂度O(128^3*logn)；
三题能68真是太好了23333；
代码：
#include<stdio.h>#include<string.h>#include<algorithm>#define N 128#define mod 1000000007using namespace std;typedef long long ll;int len,m;struct matrix{int a[N][N];}T,ans,In;bool judge(int x,int y){for(int i=0;i<m;i++){if(x&(1<<i)){if(i!=0)if((y&(1<<i-1))&&!(x&(1<<i-1))&&!(y&(1<<i)))return 0;if(i!=m-1)if((y&(1<<i+1))&&!(x&(1<<i+1))&&!(y&(1<<i)))return 0;}}return 1;}void mul(matrix &x,matrix &y){static matrix temp1,temp2;memcpy(&temp1,&x,sizeof(matrix));memcpy(&temp2,&y,sizeof(matrix));memset(&x,0,sizeof(matrix));for(int i=0;i<len;i++){for(int j=0;j<len;j++){for(int k=0;k<len;k++){x.a[i][j]=(x.a[i][j]+(ll)temp1.a[i][k]*temp2.a[k][j]%mod)%mod;}}}}matrix& pow(matrix &x,int y){static matrix ret;ret=In;while(y){if(y&1)mul(ret,x);mul(x,x);y>>=1;}return ret;}int main(){int n,i,j,k,sum;for(i=0;i<N;i++) In.a[i][i]=1;while(scanf("%d%d",&n,&m)!=EOF){len=(1<<m);memset(&T,0,sizeof(matrix));for(i=0;i<len;i++){for(j=0;j<len;j++){if(judge(i,j))T.a[i][j]=1;}}memset(&ans,0,sizeof(matrix));ans.a[0][0]=1;mul(ans,pow(T,n));for(i=0,sum=0;i<len;i++){for(j=0;j<len;j++){sum=(sum+ans.a[i][j])%mod;}}printf("%d\n",sum);}return 0;}
含泪播种的人一定能含笑收获。
