本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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_{1\le L\le n-len+1} \sum_{len\le R \le n} a_i=\sum_{len\le R \le n} sum_R-\sum_{1\le L\le n-len+1}sum_{L-1}$$ 于是我们对 $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;
}

::::