【ch30】摆花

2014年4月5日2,0790

背景及描述

艺术馆门前将摆出许多花,一共有n个位置排成一排,每个位置可以摆花也可以不摆花。有些花如果摆在相邻的位置(隔着一个空的位置不算相邻),就不好看了。假定每种花数量无限,求摆花的方案数。

输入格式

输入有1+m行,第一行有两个用空格隔开的正整数n、m,m表示花的种类数。接下来的m行,每行有m个字符1或0,若第i行第j列为1,则表示第i种花和第j种花不能排在相邻的位置,输入保证对称。(提示:同一种花可能不能排在相邻位置)。

输出格式

输出只有一个整数,为方案数(这个数字可能很大,请输出方案数除以1000000007的余数)。

样例输入

样例输出

样例说明

七种方案为(空,空)、(空,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。
 题解
首先dp很好想

然后我们可以再搞个矩阵乘法来加速转移

这个不仔细说了。。