题解：AT_arc124_e [ARC124E] Pass to Next

· · 题解

算是很困难的题目了，我做了 5 个小时。希望它能保佑我明年进 SC 省队。

一个 very interesting 的事实是任何 \min x_i\ne 0 的 x 数组都可以让所有的 x_i 减去 x，且之后的计算值相同。所以我们考虑容斥。将所有情况减去 \min x_i>0 的情况。

还有一个 very interesting 的事实是可以将乘积改成若干堆小球，每一堆选一个的方案数。

所以 n 堆小球，每一堆小球选一个的方案可以分成两大类：

所以每一堆小球（这里指移动前的）可能作出四种贡献：

接下来的 dp 更是我这样的唐氏儿不可能做得到的。

设 dp 数组 f,g。然后进行 4 次 dp。

第一次 dp 时钦定第一个位置的被选的小球的位置原先也在第一个，第二次钦定在最后一个。第三次、第四次分别与第一次、第二次类似，但是要增加一个条件，就是 \min x_i>0，要把这两部分减掉。

第一轮的转移情况如下：（所有的 \gets 代表累加）

g_{i+1}=f_i\times \binom{a_i+1}{3} f_{i+1}\gets f_i\times \sum_{j=1}^{a_i}j g_{i+1}\gets g_i\times \sum_{j=1}^{a_i}j f_{i+1}=g_i\times (a_i+1)

第三第四轮反应的 f_{i+1} 的贡献要把 a_i 改成 a_i-1，因为至少要有一个的转移。

还有就是对那个组合数的解释：a_i 个元素分为两组，每一组选一个。相当于 a_i+1 个元素选一个当隔板，剩下的两边选。

我写的是 O(n\log n) 的版本。

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
} 
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48);
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
/*
其实是确定了前面的若干个吗？ 

硬控我一天的题终于得解了吗？  
*/

const int mod=998244353;
inline int qpow(int x,int y){
    if(y==0)    return 1;
    if(y==1)    return x;
    int ret=qpow(x,y/2);
    ret=ret*ret%mod;
    if(y&1) ret=ret*x%mod;
    return ret;
} 
inline int inv(int x){
    return qpow(x,mod-2);
}
int n;
int a[2*114514],f[2*114514],g[2*114514];
//其实到 dp[i+1] 的时候才把 dp[i] 算完吗？ 

int cal1(int x){
    return x*(x+1)%mod*inv(2)%mod;
}
int cal2(int x){
    return x*(x-1)%mod*(x-2)%mod*inv(6)%mod;
}
inline int dp(int o1,int o2){
    //o1 代表钦定第一个位置的选择方式为 f 还是为 g。f 的含义是选到这里 g 的含义是上一个位置把这里选了 
    /*
    转移非常棘手 

    ff 代表 i+1 就选 i+1 的部分 这里乘 i 的地方即可？ 
    gg 代表 i+1 使用 i 的部分 也是简单的乘 i 
    fg 代表 i+1 用 i+1，i 用 i-1 更简单了吗？ 
    gf 代表 i和 i+1 都用 i 相当于要选三个？ 之后到了再讨论  

    o2 为 1 代表必须有所转移 并且会被容斥掉  
    */ 
    memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
    if(o1==1)   f[1]=1;
    else    g[1]=1;
    for(int i=1;i<=n;i++){
//      if(!o2){
            //分开讨论 o2=0 和 o2=1 的情况 
            //ff 
            //留下来的数目在 [1,a_i] 之间 然后每一个再乘上对应的值即可  
            f[i+1]+=f[i]*cal1(a[i]-o2)%mod; 
            g[i+1]+=g[i]*cal1(a[i])%mod;
            g[i+1]+=f[i]*cal2(a[i]+1)%mod;
            f[i+1]+=g[i]*(a[i]+1-o2)%mod;
            f[i+1]%=mod,g[i+1]%=mod;
//      } 
    } 
    if(o1==1)   return f[n+1]%mod;
    else    return g[n+1]%mod;
} 
#undef int
int main(){
    #define int long long
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    write((dp(0,0)+dp(1,0)-dp(0,1)-dp(1,1)+mod+mod)%mod);
    return 0;
} //重振绵中荣光我辈义不容辞，重振四川荣光我辈义不容辞！