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$次方就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#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一俩个点

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