描述 Description
艺术馆门前将摆出许多花，一共有 n 个位置排成一排，每个位置可以摆花也可以不摆花。有些花如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种花数量无限，求摆花的方案数。
输入格式 InputFormat
输入有 1+m 行，第一行有两个用空格隔开的正整数 n、m，m 表示花的种类数。接下来的 m 行，每行有 m 个字符 1 或 0, 若第 i 行第 j 列为 1，则表示第 i 种花和第 j 种花不能排在相邻的位置，输入保证对称。（提示：同一种花可能不能排在相邻位置）。
输出格式 OutputFormat
输出只有一个整数，为方案数（这个数字可能很大，请输出方案数除以 1000000007 的余数）。
样例输入 SampleInput
5 10
0000000000
0000000000
0000000001
0000000000
0000000000
0000000001
0000000000
0000000000
0000000000
0010010000
样例输出 SampleOutput
142249
数据范围和注释 Hint
20% 的数据，1＜n≤5,0＜m≤10。
60% 的数据，1＜n≤200,0＜m≤100。
100% 的数据，1＜n≤1000000000，0＜m≤100。
代码 Code
假定不摆花也算一种花，构建邻接矩阵当且仅当 i 与 j 种花不冲突时 A(i,j)=1. 矩阵快速幂求 A^n。
（即经典题目：给定一个有向图，问从 A 点恰好走 k 步（允许重复经过边）到达 B 点的方案数 mod p 的值）。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define mod 1000000007
struct matrix
{
long long mat[201][201];
};
matrix a,f;
char ch[101];
int i,j,t,n,m,l,r,k,z,y,x;
void TEST()
{
int i,j,t;
for (i=0;i<=m;i++)
{
for (j=0;j<=m;j++) cout<<a.mat[i][j]<<" ";
cout<<endl;
}
cout<<endl;
for (i=0;i<=m;i++)
{
for (j=0;j<=m;j++) cout<<f.mat[i][j]<<" ";
cout<<endl;
}
}
matrix matrixmul(matrix a,matrix b)
{
matrix c;
int i,j,t,k;
for (i=0;i<=m;i++) for (j=0;j<=m;j++)
{
c.mat[i][j]=0;
for (k=0;k<=m;k++) c.mat[i][j]+=(a.mat[i][k]*b.mat[k][j])%mod;
c.mat[i][j]%=mod;
}
return c;
}
void qp(int n)
{
f=a;
while (n)
{
if (n&1) f=matrixmul(f,a);
n>>=1;
a=matrixmul(a,a);
}
}
int main()
{
memset(a.mat,0,sizeof(a.mat));
scanf("%d%d",&n,&m);
for (i=0;i<=m;i++) a.mat[0][i]=a.mat[i][0]=1;
for (i=1;i<=m;i++)
{
scanf("%s",ch);
for (j=1;j<=m;j++) if (ch[j-1]=='0') a.mat[i][j]=1;
}
qp(n);
printf("%I64d\n",f.mat[0][0]);
return 0;
}