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

Mark_Pei · 2025-11-22 12:07:21 · 题解

Solution

此题本人NFLSPC正赛场切。

让我们先一步步分析这个问题。

有 n 个城市，初始第 i 个城市的炸弹威力为 a_i。

进行 k 次爆炸，每次随机选择一个城市（等概率 1/n）。

一次爆炸过程（假设选到城市 x）：

1. 该城市的 危险度 为 当前炸弹威力 a_x。
2. 爆炸后，该城市的炸弹威力 清零（a_x \to 0）。
3. 其它每个城市 j \neq x 的炸弹威力 增加 a_x / (n-1)（保持总威力不变）。

注意：这里“增加 a_x / (n-1)” 是精确的数学关系，因为 a_x 被均分给其它 n-1 个城市。

问题转化

设 E_i^{(t)} 表示第 t 次爆炸后，城市 i 的炸弹威力的期望值。

初始：E_i^{(0)} = a_i。

一次爆炸选到城市 x 时：

• 若 i = x：a_i \to 0。
• 若 i \neq x：a_i \to a_i + \frac{a_x}{n-1}。

推导递推式

考虑一次随机爆炸（每个城市概率 1/n）对 E_i^{(t+1)} 的影响。

情况 1：爆炸发生在城市 i（概率 1/n）

• 爆炸后 E_i^{(t+1)} = 0。

情况 2：爆炸发生在城市 j \neq i（概率 \frac{n-1}{n} 中的某一个 j）

• 对于固定的 j，概率 1/n，爆炸后： E_i^{(t+1)} = E_i^{(t)} + \frac{E_j^{(t)}}{n-1}

  注意这里 E_j^{(t)} 是爆炸前 j 的期望威力。

情况 3：爆炸发生在其它城市 p（p \neq i 且 p \neq j 的情况已经包含在情况 2 的求和里）

所以：

对 S^{(t)} 的递推

总威力守恒：每次爆炸只是把 a_x 从城市 x 均分给其它 n-1 个城市，所以总威力不变：

因此 S^{(t)} = S 对所有 t 成立。

代入化简

合并 E_i^{(t)} 的系数：

计算系数：

所以：

解递推式

这是一个一阶线性递推：

其中 C 是稳态值，令 E = \frac{n-2}{n-1} E + \frac{S}{n(n-1)} 解得：

所以稳态时每个城市期望威力相同，等于平均值。

因此：

即：

模运算实现

要求取模 998244353，需要快速幂求 \left( \frac{n-2}{n-1} \right)^k \bmod M，以及乘逆元。

记为：

平均值 avg = S \cdot n^{-1} \pmod{M}。

则：

时间复杂度

计算总和：O(n)。

快速幂：O(\log k)。

总和：O(n+\log k)。

AC code

#include<bits/stdc++.h>
using namespace std;
const int M=998244353;
long long modpow(long long a,long long b)
{
    long long r=1;
    while(b)
    {
        if(b&1) r=r*a%M;
        a=a*a%M;
        b/=2;
    }
    return r;
}
int n,k,a[1000003];
int main()
{
    cin>>n>>k;
    long long s=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s=(s+a[i])%M;
    }
    long long inv_n=modpow(n,M-2),avg=s*inv_n%M,p=n-2,q=n-1,coef=modpow(p,k)*modpow(modpow(q,k),M-2)%M;
    for(int i=1;i<=n;i++)
    {
        long long res=(avg+coef*(a[i]-avg+M))%M;
        cout<<res<<" ";
    }
    return 0;
}