CF2150D 题解

刘梓轩2010 · 2025-11-18 17:00:44 · 题解

做这题的时候读错了好几次题，生气了。

思路

首先，由于我们只关心位置数组的贡献和，位置数组之间的排列顺序我们是不关心的，所以我们将拍到桶里，设 cnt_i 表示位置 i 在原位置数组里的出现次数，不难发现，cnt 与原位置数组是一一对应的。

然后我们可以发现，由于每一次移动的时候，表现为所有人向某一个位置集中，所以有人的位置一定是一个区间，表现在 cnt 上就是我们的非零的 cnt_i 的 i 一定形成了一个区间，我们将这个区间称为 [L,R]。

我们通过手玩一下可以发现，每个一组 cnt_i 除了在区间端点上的，其他的都是奇数。为啥呢？我们考虑每次移动过程在 cnt 数组上的表现，要么是整体移动，要么是把相邻的两个（在端点上）或三个合并起来，那合并后不在端点上的原来也一定不在，所以如果合并前满足限制，那么合并后也满足。由于最开始的时候 cnt 数组全是 1，所以我们的限制是对的。

那么满足了这些要求的一定合法吗？

我们可以由最开始的数组进行考虑，从 cnt_L 开始从左往右一个一个的合并，一定能合并出当前的 [L,R] 内的每一个数，然后再对它进行位置的偏移即可。

现在我们得到了一些关于 cnt 的性质，可以对他进行计数了。

虽然我们最终求的是所有位置数组的权值和，但是我们考虑，我们可以将所有去掉非零部分后一样的 cnt 数组一块考虑，因为它只有权值不一样。

端点处的奇偶性我们可以分类讨论，引入 x 和 y，他们的取值都是 1 或 2，令 cnt_L=2g_L+x,cnt_R=2g_R+y，其中 g_L 和 g_R 都是非负整数，这样，我们就成功表示出了端点处的值。我们如法炮制，\forall i \in (L,R) 的整数 i，令 cnt_i=2g_i+1。

所以我们可以对于 g 进行计数，那么在去掉 x,y 和给每个位置分配的 1 之后，我们还剩下 tot=n-x-y-R+L-1 的和需要分配给 [L,R] 中的每一个位置，显然 tot 要是偶数，至于分配的话就是 tot 除以 2 然后隔板法。

然后来处理权值和的部分。我们令区间长度为 len，由于我们是隔板法分配，所以每个区间内的每一个位置被分配的权值的期望都是 \frac{tot}{len}+1（端点处需要注意单独处理，因为是偶数时会多 1），所以每个位置在每一种方案中的 cnt_i 的和是可以结合上面的部分算出来的。再考虑原序列的权值，那我们现在缺的就是 a 序列中所有长为 len 的区间的区间和之和。即为 \sum_{1\le L\le n-len+1} \sum _{len\le R \le n} a_i。

这个东西很很可以前缀和啊，我们推一推式子。令 sum_i 表示 a_i 的前缀和。

于是我们对 sum_i 再做一次前缀和就行了。

终于做完了。

Code

::::info[Code]

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
const int p=998244353;
int fpm(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%p;
        a=a*a%p,b>>=1;
    }
    return res;
}
int fac[N<<1],inv[N<<1];
void init()
{
    fac[0]=inv[0]=1;
    for(int i=1;i<=4e5;i++) fac[i]=fac[i-1]*i%p,inv[i]=fpm(fac[i],p-2);
}
int C(int n,int m)
{
    if(n<m) return 0;
    return fac[n]*inv[m]%p*inv[n-m]%p;
}
int mod(int x)
{
    while(x>=p) x-=p;
    while(x<0) x+=p;
    return x;
}
void add(int &x,int y)
{
    x=x+y;
    while(x>=p) x-=p;
    while(x<0) x+=p;
}
int T;
int n,a[N],s[N];
void solve()
{
    int ans=0;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],add(ans,n*a[i]%p),add(a[i],a[i-1]);
    for(int i=1;i<=n;i++) s[i]=mod(s[i-1]+a[i]);
    for(int len=2;len<=n;len++)
    {
        for(int x=1;x<=2;x++) for(int y=1;y<=2;y++)
        {
            int tot=n-x-y-len+2;
            if(tot<0||tot&1) continue;
            int num=C(len+tot/2-1,len-1);
            add(ans,num*mod(tot*fpm(len,p-2)%p+1)%p*mod(s[n]-s[len-1]-s[n-len])%p);
            if(x==2) add(ans,num*a[n-len+1]%p);
            if(y==2) add(ans,num*mod(a[n]-a[len-1])%p);
        }
    }
    cout<<ans<<endl;
}
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    init();
    cin>>T;
    while(T--) solve();
    return 0;
}

::::