题目描述
czy要妥善安排他的后宫，他想在机房摆一群妹子，一共有n个位置排成一排，每个位置可以摆妹子也可以不摆妹子。有些类型妹子如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种妹子数量无限，求摆妹子的方案数。
输入输出格式
输入格式：
输入有m+1行，第一行有两个用空格隔开的正整数n、m，m表示妹子的种类数。接下来的m行，每行有m个字符1或0,若第i行第j列为1，则表示第i种妹子第j种妹子不能排在相邻的位置，输入保证对称。（提示：同一种妹子可能不能排在相邻位置）。
输出格式：
输出只有一个整数，为方案数（这个数字可能很大，请输出方案数除以1000000007的余数。
输入输出样例
输入样例#1：
2 2 01 10
输出样例#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 <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <cmath> 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 ", anss); return 0; }