AHSOFNU NOIP模拟题-3 T3(DP+矩阵快速幂)

根据题意,设$f(i, j)$为$i$位置以$j$种妹子结尾的方案数。
则状态转移方程:
$$f(i,j) += f(i-1,k)$$
其中$k$与$j$是不冲突的,但是这题$n<10^9$,显然不行。
这里是DP,又是方案数,想到了什么?对,矩阵乘法优化!
用样例解释,构造形如下面的矩阵
$$
\begin{pmatrix}
1 & 1 & 1 \\\
1 & 1 & 0 \\\
1 & 0 & 1
\end{pmatrix}
\times
\begin{pmatrix}
f_{(i-1, 0)} \\\
f_{(i-1, 1)} \\\
f_{(i-1, 2)}
\end{pmatrix}
=
\begin{pmatrix}
f_{(i, 0)} \\\
f_{(i, 1)} \\\
f_{(i, 2)}
\end{pmatrix}
$$
第二个矩阵从$i-1=0$开始算,这样初始矩阵就是
$$
\begin{pmatrix}
1 \\\
0 \\\
0
\end{pmatrix}
$$
乘上第一个矩阵的$n$次方就行。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "harem"
using namespace std;
const int MAXM = 100 + 5, MO = 1000000007;
struct matrix {
    int x, y;
    LL ma[MAXM][MAXM];
    void init(int X, int Y) {x = X, y = Y;}
    void dw() {for (int i=0;i<x;i++) for (int j=0;j<y;j++) ma[i][j] = (i==j);}
    void em() {for (int i=0;i<x;i++) for (int j=0;j<y;j++) ma[i][j] = 0;}
};
int n, m;
char ch[MAXM];
matrix mul(matrix &a, matrix &b) {
    matrix ret; ret.init(m+1, m+1), ret.em();
    for (int i=0;i<a.x;i++) 
        for (int j=0;j<b.y;j++) 
            for (int k=0;k<a.y;k++) ret.ma[i][j] = (ret.ma[i][j]%MO + (a.ma[i][k]*b.ma[k][j])%MO)%MO;
    return ret;
}
matrix poww(matrix &a, int x) {
    matrix ret, s = a;
    ret.init(m+1, m+1), ret.dw();
    while (x) {
        if (x&1) ret = mul(ret, s);
        s = mul(s, s);
        x>>=1;
    }
    return ret;
}
void clean() {}
void solve() {
    clean();
    matrix a; a.init(m+1, m+1);
    for (int i=1;i<=m;i++) {
        scanf("%s", ch+1);
        for (int j=1;j<=m;j++) 
        if (ch[j]=='0') a.ma[i][j] = 1;
    }
    for (int i=0;i<=m;i++) a.ma[i][0] = a.ma[0][i] = 1;
    matrix b = poww(a, n);
    matrix c; c.init(m+1, 1), c.em(), c.ma[0][0] = 1;
    matrix tot = mul(b, c);
    LL ans = 0;
    for (int i=0;i<=m;i++) ans = (ans + tot.ma[i][0])%MO;
    printf("%lld\n", ans);
}
int main() {
    freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
    scanf("%d%d", &n, &m), solve();
    fclose(stdin); fclose(stdout);
    return 0;
}

Problem 3 czy的后宫
【题目描述】
czy要妥善安排他的后宫,他想在机房摆一群妹子,一共有n个位置排成一排,每个位置可以摆妹子也可以不摆妹子。有些类型妹子如果摆在相邻的位置(隔着一个空的位置不算相邻),就不好看了。假定每种妹子数量无限,求摆妹子的方案数。
【输入格式】
输入有m+1行,第一行有两个用空格隔开的正整数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。
注:此题时限1.5s是因为本评测机跑太慢,大家正常做
但写的太丑可能T一俩个点

------ 本文结束 ------