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

· · 题解

居然是 P14514！写题解留念。

来一个不一样的做法。（其实就是我懒得推式子。。。）
首先观察到每次的爆炸可以通过上次爆炸的期望值推算，考虑 O(nk) 的计算每个点的答案。

对于第 i 个点在第 j 次爆炸后的期望值 E_{i,j}，有：

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=\sum\limits_{i=1}^{n}a_i，对于任意 1 \le i \le n 有 E_{i,0}=a_i。
解释一下上面这个公式，就是若爆炸点 k=i，则贡献为 0，否则贡献为 a_i 加上对应点的贡献 \frac{E_{k,j-1}}{n-1}。

进一步化简得到

E_{i,j}=\frac{sum}{n(n-1)}+\frac{n(n-2)}{n(n-1)}E_{i,j-1}.

又由于 sum 是定值，可以看作常数，所以 E_{i,j} 就只跟 E_{i,j-1} 有关了！

于是考虑矩阵快速幂，令答案矩阵如下：

\begin{bmatrix} E_{i,j}\\ sum \end{bmatrix}

其中

E_{i,j}=\frac{sum}{n(n-1)}+\frac{n(n-2)}{n(n-1)}E_{i,j-1} sum=sum

可以推出递推关系如下：

\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}.

所以

{{}\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}.

注意到转移矩阵与 i 无关，所以其 k 次方可以提前预处理。
时间复杂度 O(nN^3)，其中 N=2 为矩阵大小，可以通过。

代码高能预警，密恐慎入。

#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++!
所以我还在这里水题解干嘛。