题解 [ARC124E] Pass to Next

· · 题解

闲话

组合意义 dp，化式子大法好，暴力出奇迹。

\text{Solution}

\text{Part1}

在化式子之前，我们先来做一些准备工作。

设 x_i 表示第 i 个人传走的球的数量。那么最终第 i 个人手上有 a_i-x_i+x_{i-1} 个球。

考虑一下如何去重，对于 x 相同的差分数组，最后的结果是一样的。所以我们可以钦定求至少有一个 x_i=0 的答案，这样就能不重不漏的算出所有情况了。

至于怎么求，我们用 x_i\in[0,a_i] 和 x_i\in[1,a_i] 容斥一下即可。下面以 x_i\in[0,a_i] 为例。

再改写一下这个不太好看的式子。

\sum_{1\leq j\leq n,0 \leq x_j\leq a_j}\prod\limits_{i=1}^n (a_i-x_i+x_{i-1})

\text{Part2}

设 S_i(a)=\sum\limits_{x=1}^{a} x^i。

暴力展开一些项，

\begin{aligned} &\sum\limits_{1\leq j\leq n,0 \leq x_j\leq a_j}(a_1-x_1+x_n)(a_2-x_2+x_1)\prod\limits_{i=3}^n (a_i-x_i+x_{i-1})\\ &\sum_{1\leq j\leq n,0 \leq x_j\leq a_j}(a_1a_2-a_1x_2+a_1x_1-a_2x_1+x_1x_2-x_1^2+a_2x_n-x_2x_n+x_1x_n)\prod\dots \end{aligned}

我们用分配率把式子拆开，先考虑标红的项，

\sum({\color{red}a_1a_2}-a_1x_2{\color{red}{+a_1x_1}}{\color{red}-a_2x_1}+x_1x_2{\color{red}-x_1^2}+a_2x_n-x_2x_n+x_1x_n)\prod

在 \prod 中不含 x_1，所以现在 x_1 是已知的了，因此：

\sum a_1a_2(a_1+1)+S_1(a_1)(a_1-a_2)-S_2(a_1)\prod

记 f_0=a_1a_2(a_1+1)+S_1(a_1)(a_1-a_2)-S_2(a_1)，表示都能算出来。

\sum({\color{grey}a_1a_2}{\color{red}-a_1x_2}{\color{grey}{+a_1x_1}}{\color{grey}-a_2x_1}{\color{red}+x_1x_2}{\color{grey}-x_1^2}+a_2x_n-x_2x_n+x_1x_n)\prod

同理，

\sum[-(a_1+1)a_1+S_1(a_1)]x_2\prod

记 f_p=-(a_1+1)a_1+S_1(a_1)，表示 含 x_{i+1} 算不出。

\sum({\color{grey}a_1a_2}{\color{grey}-a_1x_2}{\color{grey}{+a_1x_1}}{\color{grey}-a_2x_1}{\color{grey}+x_1x_2}{\color{grey}-x_1^2}{\color{red}{+a_2x_n}}-x_2x_n{\color{red}+x_1x_n})\prod

记 f_n=(a_1+1)a_2+S_1(a_1)，表示含 x_n 算不出。

\sum({\color{grey}a_1a_2}{\color{grey}-a_1x_2}{\color{grey}{+a_1x_1}}{\color{grey}-a_2x_1}{\color{grey}+x_1x_2}{\color{grey}-x_1^2}{\color{grey}{+a_2x_n}}{\color{red}-x_2x_n}{\color{grey}+x_1x_n})\prod

记 f_{np}=-(a_1+1) 表示含 x_{i+1}x_n 算不出。

现在式子变成，

\sum\limits_{2\leq j\leq n,0 \leq x_j\leq a_j}(f_0+f_px_2+f_nx_n+f_{np}x_2x_n)\prod\limits_{i=3}^n(a_i-x_i+x_{i-1})

\text{Part3}

我们再来展开一项，

\sum(f_0+f_px_2+f_nx_n+f_{np}x_2x_n)(a_3-x_3+x_2)\prod\limits_{i=4}^n(a_i-x_i+x_{i-1})

现在 x_2 又是已知的了。同上，

\begin{aligned} f_0^{(2)}&=f_0(a_2+1)a_3+f_0S_1(a_2)+f_pS_1(a_2)a_3+f_pS_2(a_2)\\ f_p^{(2)}&=-f_0(a_2+1)-f_pS_1(a_2)\\ f_n^{(2)}&=f_n(a_2+1)a_3+f_nS1(a_2)+f_{np}S_1(a_2)a_3+f_{np}S_2(a_2)\\ f_{np}^{(2)}&=-f_n(a_2+1)-f_{np}S_1(a_2)\\ \end{aligned}

以此类推，做 n-1 次。

f_0^{(n)}+f_p^{(n)}x_n+f_n^{(n)}x_n+f_{np}^{(n)}x_n^2

这时 x_n 是已知的，

ans=f_0^{(n)}(a_n+1)+f_p^{(n)}S_1(a_n)+f_n^{(n)}S_1(a_n)+f_{np}^{(n)}S_2(a_n)

初始时，f_0=a_1,f_p=-1,f_n=1,f_{np}=0。

完结撒花。

\text{Code}

#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define cout cerr
#define debug cout<<"debug"<<endl;
using namespace std;
const int N=1e5+5;
const int mod=998244353;
const ll inv2=499122177;
const ll inv6=166374059;
int n;
ll a[N];
inline int read() {
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=1; ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return f?-x:x;
}
inline void inc(ll &x,int y) {x+=y-mod;x+=(x>>63)&mod;}
inline ll S1(ll x) {return x*(x+1)%mod*inv2%mod;}
inline ll S2(ll x) {return x*(x+1)%mod*(2*x+1)%mod*inv6%mod;}
inline ll calc(ll op) {
    ll f0=a[1],fp=-1,fn=1,fnp=0;
    for(int i=2;i<=n;i++) {
        ll t0=0,tp=0,tn=0,tnp=0;
        inc(t0,f0*(a[i-1]+op)%mod*a[i]%mod);
        inc(t0,f0*S1(a[i-1])%mod);
        inc(t0,fp*S1(a[i-1])%mod*a[i]%mod);
        inc(t0,fp*S2(a[i-1])%mod);

        inc(tp,(mod-f0*(a[i-1]+op)%mod)%mod);
        inc(tp,(mod-fp*S1(a[i-1])%mod)%mod);

        inc(tn,fn*(a[i-1]+op)%mod*a[i]%mod);
        inc(tn,fn*S1(a[i-1])%mod);
        inc(tn,fnp*S1(a[i-1])%mod*a[i]%mod);
        inc(tn,fnp*S2(a[i-1])%mod);

        inc(tnp,(mod-fn*(a[i-1]+op)%mod)%mod);
        inc(tnp,(mod-fnp*S1(a[i-1])%mod)%mod);
        f0=t0,fp=tp,fn=tn,fnp=tnp;
    }
    ll ans=0;
    inc(ans,f0*(a[n]+op)%mod);
    inc(ans,fp*S1(a[n])%mod);
    inc(ans,fn*S1(a[n])%mod);
    inc(ans,fnp*S2(a[n])%mod);
    return ans;
}
int main()
{
    freopen("random_01.txt","r",stdin);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    printf("%lld",(calc(1)-calc(0)+mod)%mod);
    return 0;
}