专栏文章

题解：P14514 [NFLSPC #8] 如何区分北京东路和北京东路

ttzhengqing
P14514题解参与者 5已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mimz4lc7
此快照首次捕获于
2025/12/01 17:55
3 个月前
此快照最后确认于
2025/12/01 17:55
3 个月前
查看原文
居然是 P14514！写题解留念。
来一个不一样的做法。（其实就是我懒得推式子。。。）
首先观察到每次的爆炸可以通过上次爆炸的期望值推算，考虑 O(nk)O(nk) 的计算每个点的答案。
对于第 ii 个点在第 jj 次爆炸后的期望值 Ei,jE_{i,j}，有： Ei,j=∑1≤k≤n∧k≠i(Ei,j−1+Ek,j−1n−1)n=(n−1)Ei,j−1+sum−Ei,j−1n−1n.E_{i,j}=\frac{\sum\limits_{1 \le k \le n \wedge k \neq i}(E_{i,j-1}+\frac{E_{k,j-1}}{n-1})}{n}=\frac{(n-1)E_{i,j-1}+\frac{sum-E_{i,j-1}}{n-1}}{n}.
其中 sum=∑i=1naisum=\sum\limits_{i=1}^{n}a_i，对于任意 1≤i≤n1 \le i \le n 有 Ei,0=aiE_{i,0}=a_i。
解释一下上面这个公式，就是若爆炸点 k=ik=i，则贡献为 00，否则贡献为 aia_i 加上对应点的贡献 Ek,j−1n−1\frac{E_{k,j-1}}{n-1}。
进一步化简得到 Ei,j=sumn(n−1)+n(n−2)n(n−1)Ei,j−1.E_{i,j}=\frac{sum}{n(n-1)}+\frac{n(n-2)}{n(n-1)}E_{i,j-1}. 又由于 sumsum 是定值，可以看作常数，所以 Ei,jE_{i,j} 就只跟 Ei,j−1E_{i,j-1} 有关了！
于是考虑矩阵快速幂，令答案矩阵如下：
[Ei,jsum]\begin{bmatrix} E_{i,j}\\ sum \end{bmatrix}
其中 Ei,j=sumn(n−1)+n(n−2)n(n−1)Ei,j−1E_{i,j}=\frac{sum}{n(n-1)}+\frac{n(n-2)}{n(n-1)}E_{i,j-1} sum=sumsum=sum 可以推出递推关系如下：
[n(n−2)n(n−1)1n(n−1)01][Ei,jsum]=[Ei,j+1sum].\begin{bmatrix} \frac{n(n-2)}{n(n-1)}&\frac{1}{n(n-1)}\\ 0&1 \end{bmatrix} \begin{bmatrix} E_{i,j}\\ sum \end{bmatrix}= \begin{bmatrix} E_{i,j+1}\\ sum \end{bmatrix}.
所以
[n(n−2)n(n−1)1n(n−1)01]k[aisum]=[Ei,ksum].{{}\begin{bmatrix} \frac{n(n-2)}{n(n-1)}&\frac{1}{n(n-1)}\\ 0&1 \end{bmatrix}}^k \begin{bmatrix} a_i\\ sum \end{bmatrix}= \begin{bmatrix} E_{i,k}\\ sum \end{bmatrix}.
注意到转移矩阵与 ii 无关，所以其 kk 次方可以提前预处理。
时间复杂度 O(nN3)O(nN^3)，其中 N=2N=2 为矩阵大小，可以通过。
代码高能预警，密恐慎入。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=998244353;
struct mat{int a[2][2];}U,I;
mat mul(mat a,mat b){
	mat c=U;
	for(int i=0;i<2;i++)for(int k=0;k<2;k++)for(int j=0;j<2;j++)c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%p;
	return c;
}
mat mat_pow(mat a,int b){
	mat x=I,y=a;
	while(b){
		if(b&1)x=mul(x,y);
		y=mul(y,y);
		b>>=1;
	}
	return x;
}
int qpow(int a,int b){int x=1,y=a;while(b){if(b&1)x=x*y%p;y=y*y%p;b>>=1;}return x;}
int n,k,sum=0,a[1000005];
signed main(){
	memset(U.a,0,sizeof U.a);memset(I.a,0,sizeof I.a);
	for(int i=0;i<2;i++)I.a[i][i]=1;
	cin>>n>>k;
	for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}
	mat an;
	an.a[0][0]=n*(n-2)%p*qpow(n*(n-1)%p,p-2)%p;
	an.a[0][1]=qpow(n*(n-1)%p,p-2);
	an.a[1][0]=0;
	an.a[1][1]=1;
	an=mat_pow(an,k);
	for(int i=1;i<=n;i++){
		mat b=U;
		b.a[0][0]=a[i];
		b.a[1][0]=sum%p;
		b=mul(an,b);
		cout<<b.a[0][0]<<' ';
	}
	return 0;
}

后记

明天就是 NOIP2025 了，祝大家 rp++!
所以我还在这里水题解干嘛。

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...