【题目描述】
czy要妥善安排他的后宫，他想在机房摆一群妹子，一共有n个位置排成一排，每个位置可以摆妹子也可以不摆妹子。有些类型妹子如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种妹子数量无限，求摆妹子的方案数。
【输入格式】
输入有m+1行，第一行有两个用空格隔开的正整数n、m，m表示妹子的种类数。接下来的m行，每行有m个字符1或0,若第i行第j列为1，则表示第i种妹子第j种妹子不能排在相邻的位置，输入保证对称。（提示：同一种妹子可能不能排在相邻位置）。
【输出格式】
输出只有一个整数，为方案数（这个数字可能很大，请输出方案数除以1000000007的余数。
【样例输入】
2 2
01
10
【样例输出】
7
【样例说明】
七种方案为(空，空)、（空，1）、（1、空）、（2、空）、（空、2）、（1,1）、（2,2）。
【数据范围】
20%的数据，1＜n≤5,0＜m≤10。
60%的数据，1＜n≤200,0＜m≤100。
100%的数据，1＜n≤1000000000，0＜m≤100。
注：此题时限1.5s是因为本评测机跑太慢，大家正常做
但写的太丑可能T一俩个点
前辈都忙着开后宫了，就我这个苦逼在弱校挣扎。。。
F[i][j]={F[i-1][k]} i表示由i个妹子组成，j代表以j结尾
用异或状态压缩
60分：
#include<iostream>
using namespace std; const int mod=; int n,m,ans,p=;
int F[][];
bool D[][];
char s[]; int main()
{
cin>>n>>m;
for(int i=;i<=m;i++)
{
scanf("%s",s+);
for(int j=;j<=m;j++)
D[i][j]=s[j]-'';
}
for(int i=;i<=m;i++) F[][i]=;
for(int i=;i<=n;i++)
{
p^=;
for(int j=;j<=m;j++)
{
F[p][j]=;
for(int k=;k<=m;k++)
if(!D[j][k])
F[p][j]=(F[p][j]+F[p^][k])%mod;
}
}
for(int i=;i<=m;i++)
ans=(ans+F[p][i])%mod;
cout<<ans<<endl;
return ;
}
100分要用矩阵乘法配合图论来做
f[i][k]表示从i到k的路径条数，即以第i盆花开始，第k盆花结束的摆法有多少种
那么f[i][k]=Σ(f[i][j]*f[j][k])
即f=f*g
配合快速幂
最后ans=Σ(f[i][0])
#define LL long long #include<iostream>
#include<cstring>
using namespace std; const int MAXN=;
const int mod=; struct MAT
{
LL mat[MAXN][MAXN];
}f,g;
LL n,m,ans;
char ch[]; MAT mult(MAT a,MAT b)
{
MAT t;
memset(t.mat,,sizeof(t.mat));
for(int i=;i<=m;i++)
for(int j=;j<=m;j++)
if(a.mat[i][j])
for(int k=;k<=m;k++)
t.mat[i][k]=(t.mat[i][k]+a.mat[i][j]*b.mat[j][k])%mod;
return t;
} void modexp(int b)
{
while(b)
{
if(b&) f=mult(f,g);
g=mult(g,g);
b>>=;
}
} int main()
{
cin>>n>>m;
for(int i=;i<=m;i++)
{
scanf("%s",ch+);
for(int j=;j<=m;j++)
if(ch[j]=='') g.mat[i][j]=;
}
for(int i=;i<=m;i++)
{
g.mat[][i]=g.mat[i][]=;
f.mat[i][i]=;
}
modexp(n);
for(int i=;i<=m;i++)
ans=(ans+f.mat[i][])%mod;
cout<<ans<<endl;
return ;
}