AT_arc231_e [ARC231E] Odd Inversion 题解

· · 题解

这个题居然只评作蓝吗……我觉得，有紫吧。虽然说最终的公式很短代码也很简单，但是这个推导的过程还是非常难想到的吧 qwq。

我们考虑 dp。令 dp_i 表示当前考虑了前 i 个数的情况下的方案数。

思考在已知 dp_1 \sim dp_{i-1} 的情况下如何求出 dp_i。

首先当取 b_i > a_{i-1} 的时候一定有 b_{i-1} < b_i，不增长逆序对，直接继承答案。有 dp_i \gets dp_i + (a_i - a_{i-1}) dp_{i-1}。

那么考虑了上面的情况之后只剩下 b_{i-1},b_i \le a_{i-1}。

显然当 b_{i-1} = b_i 的时候，相对于前 i-2 个数，逆序对的增长数量一定是偶数，因为 b_{i-1} 和 b_i 之间不会增长逆序对，而它们对于那些 j < i-1 的 j 来说增长的逆序对数相等。所以直接继承 dp_{i-2}。有 dp_i \gets dp_i + a_{i-1} dp_{i-2}。

然后只剩下 b_{i-1} \not= b_i 的情况。显然要么 b_{i-1} < b_i 要么 b_{i-1} > b_i。这两种情况相对于前 i-2 个数贡献的逆序对数量是相等的，而这两种情况中，前者不在 b_{i-1} 和 b_i 之间额外贡献逆序对，而后者额外贡献 1。那么总逆序对一定有一个是偶数有一个是奇数。我们并不需要输出构造一类，所以我们不需要关心哪个是偶数哪个是奇数，只需要知道对于无序对 (b_{i-1},b_i)（b_{i-1} \not= b_i）一定贡献一种方案即可。而前面的所有 j < i-1 的 b_j 都可以在 [1,a_j] 之间随便挑，它们不影响这里的答案。有 dp_i \gets dp_i + \frac{a_{i-1} (a_{i-1} -1)}{2} \prod_{j=1}^{i-2} a_j。

综合上面的三种情况，可以得到完整的转移方程：

dp_i \gets (a_i - a_{i-1}) dp_{i-1} + (a_i-1) dp_{i-2} + \frac{a_{i-1} (a_{i-1} -1)}{2} \prod_{j=1}^{i-2} a_j

初值 dp_1 = 0（一个数不可能构成奇数个逆序对，因为不存在逆序对），转移从 i=2 开始。答案为 dp_n。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
const LL MOD = 998244353;
LL T,n,a[N],mul[N],dp[N];
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}

int main(){
    //freopen("odd.in","r",stdin);
    //freopen("odd.out","w",stdout);
    T=read();
    while(T--){
        n=read();mul[0]=1;
        for(int i=1;i<=n;i++)
            a[i]=read(),mul[i]=mul[i-1]*a[i]%MOD;
        dp[0]=0,dp[1]=0;
        for(int i=2;i<=n;i++){
            dp[i]=(a[i]-a[i-1])*dp[i-1]%MOD;
            dp[i]+=a[i-1]*dp[i-2]%MOD;
            dp[i]+=(a[i-1]*(a[i-1]-1)/2)%MOD*mul[i-2]%MOD;
            dp[i]%=MOD;
        }
        cout<<dp[n]<<"\n";
    }
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！