NKOI 3711 擺花

背景及描述

藝術館門前将擺出許多花，一共有n個位置排成一排，每個位置可以擺花也可以不擺花。有些花如果擺在相鄰的位置（隔着一個空的位置不算相鄰），就不好看了。假定每種花數量無限，求擺花的方案數。

輸入格式

輸入有1+m行，第一行有兩個用空格隔開的正整數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。

這道題是一道動規題，我們用f[i][j]表示擺好前i個位置且第i個位置放置第j種花，我們可以用j==0表示不放花的情況，并用map[x][y]=1表示x,y花可以放在一起

于是可以得到方程：f[i][j]=sum{f[i-1][k]}

不過根據資料範圍，暴力dp肯定會逾時，我們注意到m的值很小，是以可以考慮用矩形乘法來優化

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;
const LL mod=1000000007;
LL n,m,c[101],u[101];
typedef LL arr[101][101];
arr ans,z,map;
void cheng(arr y,arr x){
	memset(z,0,sizeof(z));
	LL i,j,k;
    for(i=0;i<=m;i++)
       for(j=0;j<=m;j++)
          for(k=0;k<=m;k++)
             z[i][j]=(z[i][j]+y[i][k]*x[k][j])%mod;
    memcpy(y,z,sizeof(z));
}
void cao(LL y[],arr x){
	memset(u,0,sizeof(u));
	LL i,k;
    for(i=0;i<=m;i++)
          for(k=0;k<=m;k++)
             u[i]=(u[i]+y[k]*x[i][k])%mod;
    memcpy(y,u,sizeof(u));
}
void mb(LL b){
	LL i,j;
	for(i=0;i<=m;i++)ans[i][i]=1;
    while(b){
    if(b&1)cheng(ans,map);
        b>>=1;
        cheng(map,map);
    }
}
int main()
{
	LL i,j,sum=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
		for(j=1;j<=m;j++){
			scanf("%d",&map[i][j]);
			map[i][j]=1-map[i][j];
		}
	for(i=0;i<=m;i++)map[i][0]=map[0][i]=1;
	mb(n);
	c[0]=1;
	cao(c,ans);
	for(i=0;i<=m;i++)sum=(sum+c[i])%mod;
	cout<<sum;
}