专栏文章

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

MMark_Pei
P14514题解参与者 3已保存评论 2

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@min35zb5
此快照首次捕获于
2025/12/01 19:48
3 个月前
此快照最后确认于
2025/12/01 19:48
3 个月前
查看原文

Solution

此题本人NFLSPC正赛场切。
让我们先一步步分析这个问题。
有 nn 个城市，初始第 ii 个城市的炸弹威力为 aia_i。
进行 kk 次爆炸，每次随机选择一个城市（等概率 1/n1/n）。
一次爆炸过程（假设选到城市 xx）：
  1. 该城市的 危险度 为 当前炸弹威力 axa_x。
  2. 爆炸后，该城市的炸弹威力 清零（ax→0a_x \to 0）。
  3. 其它每个城市 j≠xj \neq x 的炸弹威力 增加 ax/(n−1)a_x / (n-1)（保持总威力不变）。
注意：这里“增加 ax/(n−1)a_x / (n-1)” 是精确的数学关系，因为 axa_x 被均分给其它 n−1n-1 个城市。

问题转化

设 Ei(t)E_i^{(t)} 表示第 tt 次爆炸后，城市 ii 的炸弹威力的期望值。
初始：Ei(0)=aiE_i^{(0)} = a_i。
一次爆炸选到城市 xx 时：
  • 若 i=xi = x：ai→0a_i \to 0。
  • 若 i≠xi \neq x：ai→ai+axn−1a_i \to a_i + \frac{a_x}{n-1}。

推导递推式

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

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

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

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

  • 对于固定的 jj，概率 1/n1/n，爆炸后： Ei(t+1)=Ei(t)+Ej(t)n−1E_i^{(t+1)} = E_i^{(t)} + \frac{E_j^{(t)}}{n-1} 注意这里 Ej(t)E_j^{(t)} 是爆炸前 jj 的期望威力。

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

所以：
Ei(t+1)=1n⋅0+∑j≠i1n[Ei(t)+Ej(t)n−1]。E_i^{(t+1)} = \frac{1}{n} \cdot 0 + \sum_{j \neq i} \frac{1}{n} \left[ E_i^{(t)} + \frac{E_j^{(t)}}{n-1} \right]。

化简递推式

Ei(t+1)=∑j≠i1nEi(t)+∑j≠i1n⋅Ej(t)n−1。E_i^{(t+1)} = \sum_{j \neq i} \frac{1}{n} E_i^{(t)} + \sum_{j \neq i} \frac{1}{n} \cdot \frac{E_j^{(t)}}{n-1}。
第一项：∑j≠i1nEi(t)=n−1nEi(t)\sum_{j \neq i} \frac{1}{n} E_i^{(t)} = \frac{n-1}{n} E_i^{(t)}。
第二项：∑j≠iEj(t)n(n−1)\sum_{j \neq i} \frac{E_j^{(t)}}{n(n-1)}。
注意 ∑j≠iEj(t)=S(t)−Ei(t)\sum_{j \neq i} E_j^{(t)} = S^{(t)} - E_i^{(t)}，其中 S(t)=∑j=1nEj(t)S^{(t)} = \sum_{j=1}^n E_j^{(t)}。
所以：
Ei(t+1)=n−1nEi(t)+S(t)−Ei(t)n(n−1)。E_i^{(t+1)} = \frac{n-1}{n} E_i^{(t)} + \frac{S^{(t)} - E_i^{(t)}}{n(n-1)}。

对 S(t)S^{(t)} 的递推

总威力守恒：每次爆炸只是把 axa_x 从城市 xx 均分给其它 n−1n-1 个城市，所以总威力不变：
S(t)=∑i=1nai=S。S^{(t)} = \sum_{i=1}^n a_i = S。
因此 S(t)=SS^{(t)} = S 对所有 tt 成立。

代入化简

Ei(t+1)=n−1nEi(t)+S−Ei(t)n(n−1)。E_i^{(t+1)} = \frac{n-1}{n} E_i^{(t)} + \frac{S - E_i^{(t)}}{n(n-1)}。
合并 Ei(t)E_i^{(t)} 的系数：
Ei(t+1)=[n−1n−1n(n−1)]Ei(t)+Sn(n−1)E_i^{(t+1)} = \left[ \frac{n-1}{n} - \frac{1}{n(n-1)} \right] E_i^{(t)} + \frac{S}{n(n-1)}
计算系数：
n−1n−1n(n−1)=(n−1)2−1n(n−1)=n2−2n+1−1n(n−1)=n(n−2)n(n−1)=n−2n−1\frac{n-1}{n} - \frac{1}{n(n-1)} = \frac{(n-1)^2 - 1}{n(n-1)} = \frac{n^2 - 2n + 1 - 1}{n(n-1)} = \frac{n(n-2)}{n(n-1)} = \frac{n-2}{n-1}
所以：
Ei(t+1)=n−2n−1Ei(t)+Sn(n−1)E_i^{(t+1)} = \frac{n-2}{n-1} E_i^{(t)} + \frac{S}{n(n-1)}

解递推式

这是一个一阶线性递推：
Ei(t)−C=n−2n−1(Ei(t−1)−C),E_i^{(t)} - C = \frac{n-2}{n-1} \left( E_i^{(t-1)} - C \right),
其中 CC 是稳态值，令 E=n−2n−1E+Sn(n−1)E = \frac{n-2}{n-1} E + \frac{S}{n(n-1)} 解得：
E−n−2n−1E=Sn(n−1),E - \frac{n-2}{n-1} E = \frac{S}{n(n-1)}, En−1=Sn(n−1),\frac{E}{n-1} = \frac{S}{n(n-1)}, E=Sn.E = \frac{S}{n}.
所以稳态时每个城市期望威力相同，等于平均值。
因此：
Ei(t)−Sn=(n−2n−1)t(ai−Sn)E_i^{(t)} - \frac{S}{n} = \left( \frac{n-2}{n-1} \right)^t \left( a_i - \frac{S}{n} \right)
即：
Ei(k)=Sn+(n−2n−1)k(ai−Sn)E_i^{(k)} = \frac{S}{n} + \left( \frac{n-2}{n-1} \right)^k \left( a_i - \frac{S}{n} \right)

模运算实现

要求取模 998244353998244353，需要快速幂求 (n−2n−1)k mod M\left( \frac{n-2}{n-1} \right)^k \bmod M，以及乘逆元。
记为：
coef=(n−2n−1)k=(n−2)k⋅(n−1)−k(modM)。\text{coef} = \left( \frac{n-2}{n-1} \right)^k = (n-2)^k \cdot (n-1)^{-k} \pmod{M}。
平均值 avg=S⋅n−1(modM)avg = S \cdot n^{-1} \pmod{M}。
则：
Ei(k)=avg+coef⋅(ai−avg)(modM)。E_i^{(k)} = avg + \text{coef} \cdot (a_i - avg) \pmod{M}。

时间复杂度

计算总和：O(n)O(n)。
快速幂：O(log⁡k)O(\log k)。
总和：O(n+log⁡k)O(n+\log k)。

AC code

CPP
#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;
}

评论

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

正在加载评论...