题目描述

czy要妥善安排他的后宫，他想在机房摆一群妹子，一共有n个位置排成一排，每个位置可以摆妹子也可以不摆妹子。有些类型妹子如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种妹子数量无限，求摆妹子的方案数。

输入输出格式

输入格式：

 

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

 

输出格式：

 

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

 

输入输出样例

输入样例#1：

2 20110

输出样例#1：

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。

分析：求方案数，想到dp,设f[i][j]表示前i个位置，第i个位置放第j类的妹子的方案数，那么显然f[i][j] = Σf[i-1][k],其实可以把“不放妹子”变成一种妹子，这种妹子不与任何妹子冲突，那么套用上面的dp方程，就能得到60分.

      剩下的40分因为n太大了，导致空间和时间都会吃不消，那该怎么优化呢？总不能把第一维去掉吧，接下来就比较难想到了，因为题目给我们的是一个邻接矩阵，邻接矩阵+dp能有什么优化呢？矩阵快速幂！这道题怎么跟矩阵快速幂扯上联系呢？因为我们人为规定了第m+1种妹子："不放妹子"，那么现在就是每个位置都要放上一个妹子了，如果我们把每个妹子抽象成一条边，边权为1，那么就是求长度为n的路径数，这就是经典的矩阵快速幂的应用，套用模板就可以了.

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int mod = 1e9 + 7;int n, m;long long a[110][110],ans[110][110],t[110][110];long long anss;void mul1(){ memset(t, 0, sizeof(t)); for (int i = 0; i <= m; i++) for (int j = 0; j <= m; j++) for (int k = 0; k <= m; k++) { t[i][j] += ans[i][k] * a[k][j]; t[i][j] %= mod; } memcpy(ans, t, sizeof(ans));}void mul2(){ memset(t, 0, sizeof(t)); for (int i = 0; i <= m; i++) for (int j = 0; j <= m; j++) for (int k = 0; k <= m; k++) { t[i][j] += a[i][k] * a[k][j]; t[i][j] %= mod; } memcpy(a, t, sizeof(a));}void qpow(int b){ while (b) { if (b & 1) mul1(); b >>= 1; mul2(); }}int main(){ scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) for (int j = 1; j <= m; j++) { int t; scanf("%1d", &t); t = (t + 1) % 2; a[i][j] = t; } for (int i = 0; i <= m; i++) { a[i][0] = a[0][i] = 1; ans[i][i] = 1; } qpow(n); for (int i = 0; i <= m; i++) anss = (anss + ans[0][i]) % mod; printf("%lld\n", anss); return 0;}