题目链接：
FZU 1911 Construct a Matrix
题意：
将Fibonacci数列前n项求和后%m得到res，问存不存在这样的一个res*res阶矩阵，
矩阵中每个元素只能是-1,0或者1，并且矩阵的每行每列和都不一样。如果存在输出任意一种矩阵的构造方式。
分析：
求出res的过程用矩阵快速幂很好解决。主要是构造矩阵这个东西比较麻烦。我是先用dfs跑了一下，
void dfs(int cnt,int n)
{if(con[n]) return ;if(cnt==n*n+1){s.clear();for(int i=1;i<=n;i++){if(s.find(row[i])!=s.end()) return;else s.insert(row[i]);if(s.find(col[i])!=s.end()) return ;else s.insert(col[i]);}printf("*****************\n");for(int i=1;i<=n;i++){printf("row[%d]=%3d col[%d]=%3d\n",i,row[i],i,col[i]);}con[n]=1;if(con[n]){printf("******n=%d*********\n",n);for(int j=1;j<=n;j++){for(int k=1;k<=n;k++){printf("%3d ",map[n][j][k]);}printf("\n");}}return;}int sti=cnt/n+(cnt%n?1:0);int stj=cnt-(sti-1)*n;//printf("n=%d cnt=%d sti=%d stj=%d\n",n,cnt,sti,stj);for(int i=1;i<4;i++) {map[n][sti][stj]=dir[i];int t=cnt%n;if(t==0){t=cnt/n;row[t]=0;for(int j=1;j<=n;j++) row[t]+=map[n][t][j];int flag=1;for(int j=1;j<t;j++){if(row[j]==row[t]){flag=0;break;}}for(int j=1;j<col[cnt-n*(n-1)];j++){if(row[t]==col[j]){flag=0;break;}}if(flag==0) continue;}if(cnt>n*(n-1)){t=cnt-n*(n-1);col[t]=0;for(int j=1;j<=n;j++) col[t]+=map[n][j][t];int flag=1;for(int j=1;j<t;j++){if(col[j]==col[t]){flag=0;break;}}for(int j=1;j<cnt/n;j++){if(row[j]==col[t]){flag=0;break;}}if(flag==0) continue;}dfs(cnt+1,n);if(con[n]) return;}return ;
}
int main()
{//freopen("Pout.txt","w",stdout);memset(con,0,sizeof(con));for(int i=2;i<=tot;i+=2){dfs(1,i);}for(int i=1;i<=tot;i++){if(con[i]){printf("******i=%d*********\n",i);for(int j=1;j<=i;j++){for(int k=1;k<=i;k++){printf("%3d ",map[i][j][k]);}printf("\n");}}}return 0;
}可能是因为dfs写残了，只跑出来res=2,4,6时的构造方式，构造矩阵如下
*****************
row[1]= -2 col[1]= -1
row[2]= 1 col[2]= 0
******n=2*********-1 -1 0 1
*****************
row[1]= -4 col[1]= -2
row[2]= -3 col[2]= -1
row[3]= 2 col[3]= 0
row[4]= 3 col[4]= 1
******n=4*********-1 -1 -1 -1 -1 -1 -1 0 -1 1 1 1 1 0 1 1
*****************
row[1]= -6 col[1]= -3
row[2]= -5 col[2]= -2
row[3]= -4 col[3]= -1
row[4]= 3 col[4]= 0
row[5]= 4 col[5]= 1
row[6]= 5 col[6]= 2
******n=6*********-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 0 0 -1 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 所以我就猜想奇数的时候矩阵不存在，偶数的时候矩阵的构造方式就按照上面的方式，然后试着提交了。。。
一开始是想将所有情况都初始化，然后居然MLE了，所以改了下随时输出就AC了。。。。，尽管这样的构造方式很丑。。
学长说了另外一种构造方式，比我的简单多了，意思是
矩阵右上角全是-1，左下角全是+1，主对角线0，1,0,1间替就好了，好强。。。。。。
//380K 15MS
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
void Print();
void check();int cases=0;
long long n,mod;
int res;
int map[210][210];struct Matrix{int row,col;long long data[10][10];
};void init1(int k)
{for(int i=1;i<=k/2;i++){
//上半部分for(int j=1;j<=k;j++){if(j>=k-i+2) map[i][j]=0;else map[i][j]=-1;}}for(int i=k/2+1;i<=k;i++){
//右下角for(int j=k/2+1;j<=k;j++){map[i][j]=1;}}for(int j=1;j<=k/2;j++){for(int i=k/2+1;i<=k;i++){if(j==1){if(k==2){map[i][j]=0;continue;}if(i==k/2+1) map[i][j]=-1;else if(i==k) map[i][j]=1;else map[i][j]=0;}else if(j==k/2){if(i==k) map[i][j]=0;else map[i][j]=1;}else {if(i>j+k/2) map[i][j]=1;else map[i][j]=0;}}}//check();//Print();
}
/*
void init2(int k)
{for(int i=1;i<=k;i++){for(int j=1;j<=k;j++){if(j<=k-i) map[i][j]=-1;else if(j==k-i+1){if(i&1) map[i][j]=0;else map[i][j]=1;}else map[i][j]=1; }}//Print();
}
*/
/*
void Print()
{for(int k=2;k<=200;k+=2){printf("******%d*******\n",k);for(int i=1;i<=k;i++){for(int j=1;j<=k;j++){printf("%3d ",map[k][i][j]);}printf("\n");}}
}
*/
/*
void check()
{set<int> vec;for(int k=2;k<=200;k+=2){vec.clear();for(int i=1;i<=k;i++){int tmp=0;for(int j=1;j<=k;j++){tmp+=map[k][i][j];}if(vec.find(tmp)!=vec.end()){printf("%d---------Error\n",k);}else vec.insert(tmp);}for(int j=1;j<=k;j++){int tmp=0;for(int i=1;i<=k;i++){tmp+=map[k][i][j];}if(vec.find(tmp)!=vec.end()){printf("%d---------Error\n",k);}else vec.insert(tmp);}}
}
*/
inline Matrix mul(Matrix a,Matrix b)
{Matrix ans;ans.row=a.row,ans.col=a.col;memset(ans.data,0,sizeof(ans.data));for(int i=1;i<=ans.row;i++){for(int j=1;j<=ans.col;j++){for(int k=1;k<=a.col;k++){ans.data[i][j]+=a.data[i][k]*b.data[k][j]%mod;ans.data[i][j]%=mod;}}}return ans;
}inline Matrix quick_power(Matrix a,long long m)
{Matrix ans,tmp=a;ans.row=ans.col=a.row;memset(ans.data,0,sizeof(ans.data));for(int i=1;i<=ans.row;i++) ans.data[i][i]=1;while(m){if(m&1) ans=mul(ans,tmp);tmp=mul(tmp,tmp);m>>=1;}return ans;
}int main()
{//freopen("Pin.txt","r",stdin);//freopen("Pout.txt","w",stdout);//init1();//init2();//check();int T;scanf("%d",&T);while(T--){scanf("%lld%lld",&n,&mod);Matrix ans,tmp;ans.row=ans.col=tmp.row=3;tmp.col=1;memset(ans.data,0,sizeof(ans.data));ans.data[1][2]=ans.data[2][1]=ans.data[2][2]=ans.data[3][1]=ans.data[3][2]=ans.data[3][3]=1;tmp.data[1][1]=tmp.data[2][1]=1;tmp.data[3][1]=2;ans=quick_power(ans,n-2);tmp=mul(ans,tmp);res=(int)(tmp.data[3][1]);if(res&1||res==0){printf("Case %d: No\n",++cases);}else{init1(res);//init2(res);printf("Case %d: Yes\n",++cases);//printf("res=%d\n",res);for(int i=1;i<=res;i++){for(int j=1;j<=res;j++){if(j<res) printf("%d ",map[i][j]);else printf("%d\n",map[i][j]);}}}}return 0;
}