题目链接：https://atcoder.jp/contests/arc170/tasks/arc170_e
题目大意：现在有一个 $n$ 个点的环，然后每个点的权值 $a_i$ ，一开始都是 $-1$ ，然后有个队列，初始只有一个 $(1,0)$，
然后每次弹出队首 $(d,v)$，若 $a_d=-1$ ，则：
- $a_d=v$ 。
- 从小到大考虑 $d$ 相邻的权值为 $-1$ 的邻居 $x$ ，然后有 $p$ 的概率把 $(x,v+1)$ 加入队首，否则加入队尾。
问最后所有点的权值和的期望。
做法
唐，太唐了，转换完题意不会做，一个经典的二阶期望不会，唐，太烫了。
首先，这道题目显然可以转换成这个题意：
现在有一个长度为二的数组：$a[0]=-1,a[1]=0$ ，然后 $type=0$ ，现在进行 $n-1$ 轮：
a[type]++ 。- 有 $p$ 的概率不发生变化，有 $1-p$ 的概率
type^=1 。
问最后 $\frac{a0}{2}+\frac{a1}{2}$ 的期望值。
首先，多少阶的期望都是能做的，开对应阶数个状态就行了，像自然数幂求和那样推一下式子就行了。
这里是二阶期望，开两个状态即可。
但这里由于数组有两个位置，所以还要再多开一个状态，总共三个状态，分别为：
$f_{ans}[n]$ 表示 $n$ 轮后的期望答案，$f_0[n]$ 表示 $a[type]$ 的期望值，$f_1[n]$ 表示 $a[1-type]$ 的期望值。
则式子为：
然后直接矩阵快速幂就行了。
时间复杂度：$O(T\log{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
58
59
60
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=998244353;
struct Matrix{
LL a[4][4];
Matrix(){
memset(a,0,sizeof(a));
}
}O,tr;
Matrix operator*(Matrix x,Matrix y){
Matrix z;
for(int i=0;i<=3;i++){
for(int j=0;j<=3;j++){
for(int k=0;k<=3;k++){
z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
}
}
}
return z;
}
Matrix operator+(Matrix x,Matrix y){
Matrix z;
for(int i=0;i<=3;i++){
for(int j=0;j<=3;j++)z.a[i][j]=(x.a[i][j]+y.a[i][j])%mod;
}
return z;
}
Matrix operator%(Matrix x,LL y){return x;}
template<class T>
T ksm(T x,LL y,T o){
T ans=o;
while(y){
if(y&1)ans=ans*x%mod;
x=x*x%mod;y>>=1;
}
return ans;
}
int main(){
for(int i=0;i<=3;i++){
O.a[i][i]=1;
}
int T;scanf("%d",&T);
while(T--){
LL n,p;scanf("%lld%lld",&n,&p);
p=p*ksm(100ll,mod-2,1ll)%mod;
LL pn=(1-p+mod)%mod;
tr.a[0][0]=tr.a[1][0]=tr.a[3][0]=1;
tr.a[1][1]=tr.a[3][1]=p;tr.a[2][1]=pn;
tr.a[1][2]=tr.a[3][2]=pn;tr.a[2][2]=p;
tr.a[3][3]=1;
Matrix ans=ksm(tr,n,O);
printf("%lld\n",(ans.a[3][0]-ans.a[1][0]+mod)%mod);
}
return 0;
}
|
我当时其实写出了一个正确的式子，但我不知道怎么推了，在文章的最后放一下吧，悲。
唐，怎么每次碰到dp+矩阵快速幂的题都不会做啊，悲。
