P13682 [IAMOI R2] 污水博弈

神秘数数题。

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

我们记

s_i=\sum\limits_{j=1}^ia_i

，然后分类讨论：

$l=1,r=n$ ，这部分没什么好说的，贡献为 $\frac{s_n}{n}$ 。
$l=1,r\in[1,n-1]$ ，我们枚举后面一段可以分割成多少个区间，

$\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}$
$l\in[2,n],r=n$ ，类似的枚举前一段可分割成多少段， $\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}$
$[l,r]\subseteq[2,n-1]$ ，我们同时枚举左右两边： $\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$，因此，

CPP

\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$ 时，有： $$\begin{align*} 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$ 时，有： $$\begin{aligned} 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)$。 代码很短。 ```cpp #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; } ```

P13682 [IAMOI R2] 污水博弈

文章操作

相关推荐

评论

P13682 [IAMOI R2] 污水博弈