https://ac.nowcoder.com/acm/contest/7079
D - 牛牛的粉丝
题意：环上 n 个位置，每个位置有 x[i] 个人，每个人独立，有 p1 的概率顺时针移动，p2 概率逆时针移动，p3 概率不动。问移动 k 轮后，每个位置上的人数的期望。3≤n≤500,0≤k≤1018,xi≤106
矩阵快速幂+循环矩阵
每个人都是独立的，所以可以分别考虑每个人最终移动到各个位置上的概率。
假设 一个人初始在位置 0 ，f[i][j] 表示第 i 轮后这个人在位置 j 的概率。
转移方程为 f[i][j]=p1f[i−1][j−1]+p2f[i−1][j+1]+p3f[i−1][j]。
用 n*1 的向量表示 f[i][0⋯n−1]，转移 k 次，矩阵快速幂计算。
复杂度 O(n3logk) 太大。
关键点在矩阵乘法的时间上。
本题的矩阵很特殊，是个循环矩阵，每行等于上一行右移一格。
循环矩阵有个特殊的性质：循环矩阵的线性组合或者两个循环矩阵相乘的结果仍为循环矩阵。
所以实际计算矩阵乘法时只需要计算出一行，后面的几行都可以由上一行右移得到。则一次矩阵乘法的复杂度降为 O(n2)。总复杂度为 O(n2logk)。
upd. 之前的代码有个地方忘记乘longlong导致溢出了，没想到 clang 给自动优化了0.o 。现在是正确代码了。
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 5e5 + 10;
const ll mod = 998244353;
struct Mat {
int a[510][510];
int r, c;
Mat(int _r, int _c) { r = _r, c = _c, memset(a, 0, sizeof(a)); }
};
Mat operator * (Mat X, Mat Y) {
Mat Z(X.r, Y.c);
for (int i = 0; i < X.r; ++i) {
for (int j = 0; j < Y.c; ++j) {
for (int k = 0; k < X.c; ++k) {
Z.a[i][j] = (Z.a[i][j] + 1ll * X.a[i][k] * Y.a[k][j] % mod) % mod;
}
}
}
return Z;
}
Mat mul(Mat X, Mat Y) {
Mat Z(X.r, Y.c);
for (int j = 0; j < Y.c; ++j) {
for (int k = 0; k < X.c; ++k) {
Z.a[0][j] = (Z.a[0][j] + 1ll * X.a[0][k] * Y.a[k][j] % mod) % mod;
}
}
for (int i = 1; i < X.r; ++i) {
for (int j = 0; j < Y.c; ++j) {
Z.a[i][j] = Z.a[i - 1][(j - 1 + Y.c) % Y.c];
}
}
return Z;
}
Mat pow(Mat a, ll n) {
Mat res(a.r, a.c);
for (int i = 0; i < a.r; i++)
res.a[i][i] = 1;
while (n) {
if (n & 1) res = mul(res, a);
a = mul(a, a);
n >>= 1;
}
return res;
}
int n;
ll k;
ll Pow(ll a, ll b) {
ll res = 1ll;
while (b) {
if (b & 1)res = res * a%mod;
a = a * a%mod;
b >>= 1;
}
return res;
}
ll a, b, c, s;
ll p1, p2, p3;
int x[510];
ll ans[510];
int main() {
scanf("%d%lld", &n, &k);
scanf("%lld%lld%lld", &a, &b, &c);
for (int i = 0; i < n; i++)scanf("%d", &x[i]);
s = a + b + c;
ll invs = Pow(s, mod - 2);
p1 = a * invs%mod;
p2 = b * invs%mod;
p3 = c * invs%mod;
Mat A(n, n); Mat f(n, 1);
f.a[0][0] = 1;
for (int i = 0; i < n; i++) {
A.a[i][i] = p3;
A.a[i][(i - 1 + n) % n] = p1;
A.a[i][(i + 1) % n] = p2;
}
A = pow(A, k);
f = A * f;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ans[(i + j) % n] = (ans[(i + j) % n] + 1ll * f.a[j][0] * x[i] % mod) % mod;
}
}
for (int i = 0; i < n; i++)printf("%lld%c", ans[i], " \n"[i == n - 1]);
return 0;
}
|
