P13682 [IAMOI R2] 污水博弈

SukiYuri · 2025-08-10 01:04:59 · 题解

神秘数数题。

我们考虑计算所有区间的贡献。

我们记 s_i=\sum\limits_{j=1}^ia_i，然后分类讨论：

$$\frac{s_r}{r}\sum\limits_{i=2}^{n-r+1}\frac{1}{i}\binom{n-r-1}{i-2}=\frac{s_r}{r}\sum\limits_{i=0}^{n-r-1}\frac{1}{i+2}\binom{n-r-1}{i}$$
$$\frac{s_n-s_{l-1}}{n-l+1}\sum\limits_{i=2}^{l}\frac{1}{i}\binom{l-2}{i-2}=\frac{s_n-s_{l-1}}{n-l+1}\sum\limits_{i=0}^{l-2}\frac{1}{i+2}\binom{l-2}{i}$$
$$\frac{s_r-s_{l-1}}{r-l+1}\sum\limits_{i=3}^{n-r+l+1}\frac{1}{i}\sum\limits_{j=1}^{l-1}\binom{l-2}{j-2}\binom{n-r}{i-j-1}$$ 后半部分是一个范德蒙德卷积，于是贡献为： $$\frac{s_r-s_{l-1}}{r-l+1}\sum\limits_{i=3}^{n-r+l+1}\frac{1}{i}\binom{n-r+l-2}{i-3}=\frac{s_r-s_{l-1}}{r-l+1}\sum\limits_{i=0}^{n-r+l-2}\frac{1}{i+3}\binom{n-r+l-2}{i}$$

发现复杂度瓶颈在于 g(i,k)=\sum\limits_{j=0}^{n-i-k}\frac{1}{j+k+1}\binom{n-i-k}{j} 的计算。

我们当然可以 NTT 做完，但那样太不牛了。

考虑如下化简：

g(i,k) &= \sum\limits_{j=0}^{n-i-k}\frac{\binom{n-i-k}{j}}{j+k+1}\\ g(n-i-k,k)&= \sum\limits_{j=0}^{i}\binom{i}{j}\int_0^1 t^{j+k}\mathrm dt\\ &=\int_0^1t^k\sum\limits_{j=0}^{i}\binom{i}{j}t^j\mathrm dt\\ &=\int_0^1t^k(t+1)^i\mathrm dt \end{aligned}

次数太高没法做，但是这题 k=1,2 所以我们令 u=t+1，有 \mathrm du=\mathrm dt，因此，

\begin{align*} \int_0^1 t^k(t+1)^i\mathrm dt &= \int_{1}^{2} (u-1)^ku^i\mathrm du\\ &=\int_{1}^{2} u^i\cdot\sum_{l=0}^k \binom{k}{l}\cdot (-1)^lu^{k-l} \mathrm du \end{align*}

当 k=2 时，有：

g(n-i-2,2)&=\int_{1}^{2} u^i(u^2-2u+1) \mathrm du\\ &=\left[\frac{u^{i+3}}{i+3}-\frac{2u^{i+2}}{i+2}+\frac{u^{i+1}}{i+1}\right]^2_1\\ &=\frac{2^{i+3}}{i+3}-\frac{2^{i+3}}{i+2}+\frac{2^{i+1}}{i+1}-\frac{1}{i+3}+\frac{2}{i+2}-\frac{1}{i+1} \end{align*}

当 k=1 时，有：

g(n-i-1,1)&=\int_{1}^{2} u^i(u-1) \mathrm du\\ &=\left[\frac{u^{i+2}}{i+2}-\frac{u^{i+1}}{i+1}\right]^2_1\\ &=\frac{2^{i+2}}{i+2}-\frac{2^{i+1}}{i+1}-\frac{1}{i+2}+\frac{1}{i+1} \end{aligned}

至此，我们在 O(1) 时间算出了 g(i,1/2)。

代码很短。

#include "iostream"
#define int long long
using namespace std;
const int maxn=11e5+5,P=998244353;
int inv[maxn],s[maxn],pw[maxn],g[maxn],h[maxn],f[maxn];
inline int fp(int a,int k) {
    int r=1;
    for(;k;k>>=1,a=a*a%P) if(k&1) r=r*a%P;
    return r;
}
inline void init(int n) {
    pw[1]=2; inv[1]=pw[0]=1;
    for(int i=2;i<=n;++i) inv[i]=inv[P%i]*(P-P/i)%P,pw[i]=2*pw[i-1]%P;
}
inline int G(int u) { // \sum_{i=0}^{u} \binom{u}{i}\frac{1}{i+3}
    if(u<0) return 0;
    return ((pw[u+3]*inv[u+3]-pw[u+3]*inv[u+2]+pw[u+1]*inv[u+1]
    -inv[u+3]+2*inv[u+2]-inv[u+1])%P+P)%P;
}
inline int H(int u) { // \sum_{i=0}^{u} \binom{u}{i}\frac{1}{i+2}
    if(u<0) return 0;
    return ((pw[u+2]*inv[u+2]-pw[u+1]*inv[u+1]
    -inv[u+2]+inv[u+1])%P+P)%P;
}
signed main() {
    ios::sync_with_stdio(0);
    int n,ans=0,lim; cin>>n; init(n+10);
    for(int i=1;i<=n;++i) {
        cin>>s[i],s[i]=(s[i-1]+s[i])%P;
        g[i]=G(n-i-2); h[i]=H(n-i-1);
    }
    ans=(s[n]*inv[n])%P; lim=(n-1)/2;
    for(int i=1;i<n;++i) ans=(ans+h[i]*s[i]%P*inv[i])%P;
    for(int i=n;i>1;--i) ans=(ans+h[n-i+1]*(s[n]-s[i-1]+P)%P*inv[n-i+1])%P;
    for(int i=1;i<=lim;++i) f[i]=(s[n-i]-s[i]+f[i-1]+P)%P,f[n-i-1]=f[i];
    for(int i=1;i<n-1;++i) ans=(ans+inv[i]*f[i]%P*g[i])%P;
    cout<<ans*fp(pw[n-1],P-2)%P;
    return 0;
}