自动搬运

查看原文

来自洛谷，原作者为

	Scarlet_Hypoc ...

搬运于2025-08-24 22:23:09，当前版本为作者最后更新于2020-10-09 12:59:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

可能是一篇比较硬核的题解

容易想到的思路是分别考虑每一条边的贡献，设 $h_i$ 表示 $i$ 个点的图的方案数，则答案为：

$$\frac 1 {h_n}\sum_{i=1}^n\sum_{j=i+1}^na_ia_j\frac {h_{j-i+1}h_{n-(j-i-1)}} 4 $$

$\sum$ 里面的式子表示：连 $i,j$ 这条边，权值为 $a_i\times a_j$，图被分开成两部分，这两部分随便连边的方案数分别为 $h_{j-i+1},h_{n-(j-i-1)}$，但是两个部分内都有一条边强制要连上，不难发现这条边对别的边没有影响，所以直接除以 $2$ 就能得到连了这条边的方案，两个部分都除以 $2$ 就是除以 $4$ 了。

令 $f_i=h_{i+1}h_{n-i+1}$，代入得：

$$\begin{aligned} &=\frac 1 {4h_n}\sum_{i=1}^n\sum_{j=i+1}^n a_ia_jf_{j-i}\\ &=\frac 1 {4h_n}\sum_{j=1}^na_j\sum_{i=1}^{j-1}a_if_{j-i} \end{aligned} $$

不难发现后面是个卷积的形式，这样就求出答案了。

剩下的唯一一个问题是：如何求出 $h$？

考虑与 $1$ 号节点连边的编号最小的节点是谁，设为 $i$，则 $i$ 以后的节点与 $1,i$ 又构成了一个子问题，并强制连 $1,i$ 这条边，跟上面一样，方案数为 $h_{n-i+1}/2$，剩下 $1$ ~ $i-1$ 也是个子问题，方案数为 $h_i$。

还需要考虑没有点和 $1$ 连边的方案，可以看做点 $1$ 不存在，剩下的点构成一个子问题，方案数为 $h_{n-1}$。

于是有：

$$\begin{aligned} h_n&=h_{n-1}+\frac 1 2\sum_{i=2}^n h_ih_{n-i+1}\\ &=2h_{n-1}+\sum_{i=2}^{n-1}h_i h_{n-i+1} \end{aligned} $$

边界为 $h_1=1$。

令 $g_n=h_{n+1}$，代入得：

$$\begin{aligned} g_{n-1}&=2g_n+\sum_{i=2}^{n-1}g_{i-1}g_{n-i}\\ g_n&=2g_{n-1}+\sum_{i=1}^{n-1}g_ig_{n-i} \end{aligned} $$

看起来如果后面的卷积能把 $g_0$ 算上就会很棒，稍微改改：

$$\begin{aligned} g_n+2g_n&=2g_{n-1}+2g_n+\sum_{i=1}^{n-1} g_ig_{n-i}\\ g_n+2g_n&=2g_{n-1}+\sum_{i=0}^ng_ig_{n-i}\\ g_n&=\dfrac 2 3 g_{n-1}+\frac 1 3\sum_{i=0}^ng_ig_{n-i}\\ \end{aligned} $$

设 $G(x)$ 为 $g$ 的生成函数，将递推式写成封闭形式：

$$G=\frac 2 3Gx+\frac 1 3G^2+\frac 2 3$$

求解得到：

$$G=\frac {3-2x\pm\sqrt{4x^2-12x+1}} 2$$

由于 $G(0)$ 应该等于 $1$，所以这里取 $-$ 号，即：

$$G=\frac {3-2x-\sqrt{4x^2-12x+1}} 2$$

考虑如何展开 $\sqrt{4x^2-12x+1}$，令 $f=4x^2-12x+1$，$F=f^{\frac 1 2}$，可以得到：

$$F'f=(\frac 1 2f^{-\frac 1 2}f')f=\frac 1 2 f^{\frac 1 2}f'=\frac 1 2Ff' $$

设 $F=\sum_{i=0}a_ix^i$，$F'=\sum_{i=0}a_{i+1}(i+1)x^i$，根据 $f=4x^2-12x+1$，可以得到 $f'=8x-12$，展开 $F'f$ 和 $\frac 1 2 Ff'$：

$$F'f=\sum_{i=0} (4a_{i-1}(i-1)-12a_ii+a_{i+1}(i+1))x^i $$$$\frac 1 2 Ff'=\sum_{i=0}(4a_{i-1}-6a_i)x^i$$

由于两个多项式相等，即每一项系数都相等，于是可以得到等式：

$$4a_{i-1}(i-1)-12a_ii+a_{i+1}(i+1)=4a_{i-1}-6a_i$$ $$a_{i+1}=\frac {(12i-6)a_i-4(i-2)a_{i-1}} {i+1}$$

边界为 $a_0=1,a_1=\dfrac {(12\times 0-6)a_0} {0+1}=-6$。

不开 $O2$，$45ms$，目前洛谷rk1，代码如下：

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 300010
#define mod 998244353
#define bin(x) (1<<(x))

int n,a[maxn];
int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
int inv[maxn],w[maxn];void prep(int lg){int N=bin(lg);
	inv[1]=1;for(int i=2;i<=N;i++)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1,wn;i<N;i<<=1){
		w[i]=1;wn=ksm(3,(mod-1)/(i<<1));
		for(int j=1;j<i;j++)w[i+j]=1ll*w[i+j-1]*wn%mod;
	}
}
int limit,r[maxn];
void InitR(int lg){for(int i=1;i<bin(lg);i++)r[i]=(r[i>>1]>>1)|((i&1)<<(lg-1));}
int add(int x){return x>=mod?x-mod:x;}
int dec(int x){return x<0?x+mod:x;}
void ntt(int *f,int lg,int type=0){
	limit=bin(lg);if(type)reverse(f+1,f+limit);
	for(int i=1;i<limit;i++)if(i<r[i])swap(f[i],f[r[i]]);
	for(int mid=1,t;mid<limit;mid<<=1)for(int j=0;j<limit;j+=(mid<<1))for(int i=0;i<mid;i++)
	{t=1ll*f[j+i+mid]*w[mid+i]%mod;f[j+i+mid]=dec(f[j+i]-t);f[j+i]=add(f[j+i]+t);}
	if(type)for(int i=0;i<limit;i++)f[i]=1ll*f[i]*inv[limit]%mod;
}
int g[maxn],f[maxn];

int main()
{
	scanf("%d",&n);
	int lg=ceil(log2((n+1)<<1));prep(lg);InitR(lg);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	g[0]=1;g[1]=mod-6;
	for(int i=1;i<n;i++)g[i+1]=1ll*dec( 1ll*(12ll*i%mod-6+mod)*g[i]%mod - 4ll*(i-2)%mod*g[i-1]%mod )*inv[i+1]%mod;
	for(int i=0;i<=n;i++)g[i]=(mod-g[i]);
	g[0]=(g[0]+3)%mod;g[1]=(g[1]-2+mod)%mod;
	for(int i=0;i<=n;i++)g[i]=1ll*g[i]*inv[2]%mod;
	
	for(int i=1;i<=n;i++)f[i]=1ll*g[i]*g[n-i]%mod;
	ntt(a,lg);ntt(f,lg);for(int i=0;i<bin(lg);i++)f[i]=1ll*f[i]*a[i]%mod;
	ntt(a,lg,1);ntt(f,lg,1);int ans=0;
	for(int i=1;i<=n;i++)ans=add(ans+1ll*a[i]*f[i]%mod);
	ans=1ll*ans*ksm(4ll*g[n-1]%mod,mod-2)%mod;
	printf("%d",ans);
}