ARC124E Pass to Next 题解

· · 题解

设第 i 个人给下一个人传了 c_i 个球，第 i 个人的手中最终有 x_i 个球，则有 x_i=a_i-c_i+c_{i-1}，其中我们认为 c_0=c_n。显然，若 \min\limits_{i=1}^n c_i \gt 0 则可以通过使所有 c_i 都减去 1 的方式保持最终局面不变，而所有 \min\limits_{i=1}^n c_i=0 所形成的最终局面又两两不同，也就是说所有 \min\limits_{i=1}^n c_i=0 的操作序列 c 与最终局面 x 形成了双射。因此，我们考虑转化计数对象：对于所有 c_i \in [0,a_i] 且 \min\limits_{i=1}^n c_i=0 的数列 c，计算 \prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 的和。

先上一个经典手法，把所有 c_i \in [0,a_i] 且 \min\limits_{i=1}^n c_i=0 的数列 c 的 \prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和转化为，所有 c_i \in [0,a_i] 的数列 c 的 \prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和减去所有 c_i \in [1,a_i] 的数列 c 的 \prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和。

接下来尝试计算所有 c_i \in [0,a_i] 的数列 c 的 \prod\limits_{i=1}^n (a_i-c_i+c_{i-1}) 之和。考虑其组合意义：对于所有最终局面，从每个人手中选一个球的方案数。

设 f_i 表示考虑完前 i-1 个人且第 i 个人选择了自己的球的方案数，g_i 表示考虑完前 i 个人且第 i 个人选择了上一个人传来的球的方案数。这样设计状态是因为，若第 i 个人选择了自己的球，则其贡献需要在 f_i 向 f_{i+1} 或 g_{i+1} 转移时计算，而若第 i 个人选择了上一个人传来的球，则其贡献需要在 f_{i-1} 或 g_{i-1} 向 g_i 转移时计算。

转移方程为：

由于这是一个环，所以我们还需要枚举一下第 1 个人的状态：先初始化 f_1=1,g_1=0，dp 一轮，给答案加上 f_{n+1}；再初始化 f_1=0,g_1=1，重新 dp 一轮，给答案加上 g_{n+1}。

解决了 c_i \in [0,a_i] 的情况，c_i \in [1,a_i] 的情况是基本相同的，但由于要求每个人都要传递至少一个球，所以转移方程变为了：

其余部分都是一样的，按照上面的方法计算即可。

时间复杂度 \mathcal O(n)。

const int N=3e5+5,mod=998244353,inv2=499122177,inv6=166374059;
int n,a[N],f[N],g[N];
int ad(int a,int b){
    a+=b;
    if(a>=mod) a-=mod;
    return a;
}
int s1(int x){
    return 1ll*x*(x+1)%mod*inv2%mod;
}
int s2(int x){
    return 1ll*x*(x+1)%mod*(x+x+1)%mod*inv6%mod;
}
int work(int x,int y){
    if(!x) f[1]=1,g[1]=0;
    else f[1]=0,g[1]=1;
    for(int i=1;i<=n;i++){
        f[i+1]=ad(1ll*f[i]*s1(a[i]-y)%mod,1ll*g[i]*(a[i]-y+1)%mod);
        g[i+1]=ad(1ll*f[i]*ad(1ll*a[i]*s1(a[i])%mod,mod-s2(a[i]))%mod,1ll*g[i]*s1(a[i])%mod);
    }
    if(!x) return f[n+1];
    else return g[n+1];
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    cout<<ad(ad(work(0,0),work(1,0)),mod-ad(work(0,1),work(1,1)))<<endl;
}