题目传送门
题目大意： 有 n n n 个点在圆上，第 i i i 个点权值为 a i a_i ai，一条连接 i , j i,j i,j 的边权值为 a i × a j a_i\times a_j ai×aj，现在随机生成一幅图，图内任意两条边不相交，问期望边权和。
可能是一篇比较硬核的题解
容易想到的思路是分别考虑每一条边的贡献，设 h i h_i hi 表示 i i i 个点的图的方案数，则答案为： 1 h n ∑ i = 1 n ∑ j = i + 1 n a i a j h j − i + 1 h n − ( j − i − 1 ) 4 \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 hn1i=1∑nj=i+1∑naiaj4hj−i+1hn−(j−i−1)
∑ \sum ∑ 里面的式子表示：连 i , j i,j i,j 这条边，权值为 a i × a j a_i\times a_j ai×aj，图被分开成两部分，这两部分随便连边的方案数分别为 h j − i + 1 , h n − ( j − i − 1 ) h_{j-i+1},h_{n-(j-i-1)} hj−i+1,hn−(j−i−1)，但是两个部分内都有一条边强制要连上，不难发现这条边对别的边没有影响，所以直接除以 2 2 2 就能得到连了这条边的方案，两个部分都除以 2 2 2 就是除以 4 4 4 了。
令 f i = h i + 1 h n − i + 1 f_i=h_{i+1}h_{n-i+1} fi=hi+1hn−i+1，代入得： = 1 4 h n ∑ i = 1 n ∑ j = i + 1 n a i a j f j − i = 1 4 h n ∑ j = 1 n a j ∑ i = 1 j − 1 a i f j − i \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} =4hn1i=1∑nj=i+1∑naiajfj−i=4hn1j=1∑naji=1∑j−1aifj−i
不难发现后面是个卷积的形式，这样就求出答案了。
剩下的唯一一个问题是：如何求出 h h h？
考虑与 1 1 1 号节点连边的编号最小的节点是谁，设为 i i i，则 i i i 以后的节点与 1 , i 1,i 1,i 又构成了一个子问题，并强制连 1 , i 1,i 1,i 这条边，跟上面一样，方案数为 h n − i + 2 / 2 h_{n-i+2}/2 hn−i+2/2，剩下 1 1 1 ~ i − 1 i-1 i−1 也是个子问题，方案数为 h i − 1 h_{i-1} hi−1。
还需要考虑没有点和 1 1 1 连边的方案，可以看做点 1 1 1 不存在，剩下的点构成一个子问题，方案数为 h n − 1 h_{n-1} hn−1。
于是有： h n = h n − 1 + 1 2 ∑ i = 2 n h i − 1 h n − i + 2 = 2 h n − 1 + ∑ i = 3 n h i − 1 h n − i + 2 \begin{aligned} h_n&=h_{n-1}+\frac 1 2\sum_{i=2}^n h_{i-1} h_{n-i+2}\\ &=2h_{n-1}+\sum_{i=3}^n h_{i-1} h_{n-i+2} \end{aligned} hn=hn−1+21i=2∑nhi−1hn−i+2=2hn−1+i=3∑nhi−1hn−i+2
边界为 h 1 = 1 h_1=1 h1=1。
令 g n = h n + 1 g_n=h_{n+1} gn=hn+1，代入得： g n − 1 = 2 g n − 2 + ∑ i = 3 n g i − 2 g n − i + 1 g n = 2 g n − 1 + ∑ i = 1 n − 1 g i g n − i \begin{aligned} g_{n-1}&=2g_{n-2}+\sum_{i=3}^n g_{i-2} g_{n-i+1}\\ g_n&=2g_{n-1}+\sum_{i=1}^{n-1} g_i g_{n-i} \end{aligned} gn−1gn=2gn−2+i=3∑ngi−2gn−i+1=2gn−1+i=1∑n−1gign−i
看起来如果后面的卷积能把 g 0 g_0 g0 算上就会很棒，稍微改改： g n + 2 g n = 2 g n − 1 + 2 g n + ∑ i = 1 n − 1 g i g n − i g n + 2 g n = 2 g n − 1 + ∑ i = 0 n g i g n − i g n = 2 3 g n − 1 + 1 3 ∑ i = 0 n g i g n − i \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} gn+2gngn+2gngn=2gn−1+2gn+i=1∑n−1gign−i=2gn−1+i=0∑ngign−i=32gn−1+31i=0∑ngign−i
设 G ( x ) G(x) G(x) 为 g g g 的生成函数，将递推式写成封闭形式： G = 2 3 G x + 1 3 G 2 + 2 3 G=\frac 2 3Gx+\frac 1 3G^2+\frac 2 3 G=32Gx+31G2+32
求解得到： G = 3 − 2 x ± 4 x 2 − 12 x + 1 2 G=\frac {3-2x\pm\sqrt{4x^2-12x+1}} 2 G=23−2x±4x2−12x+1
由于 G ( 0 ) G(0) G(0) 应该等于 1 1 1，所以这里取 − - − 号，即： G = 3 − 2 x − 4 x 2 − 12 x + 1 2 G=\frac {3-2x-\sqrt{4x^2-12x+1}} 2 G=23−2x−4x2−12x+1
考虑如何展开 4 x 2 − 12 x + 1 \sqrt{4x^2-12x+1} 4x2−12x+1 ，令 f = 4 x 2 − 12 x + 1 f=4x^2-12x+1 f=4x2−12x+1， F = f 1 2 F=f^{\frac 1 2} F=f21，可以得到： F ′ f = ( 1 2 f − 1 2 f ′ ) f = 1 2 f 1 2 f ′ = 1 2 F f ′ F'f=(\frac 1 2f^{-\frac 1 2}f')f=\frac 1 2 f^{\frac 1 2}f'=\frac 1 2Ff' F′f=(21f−21f′)f=21f21f′=21Ff′
设 F = ∑ i = 0 a i x i F=\sum_{i=0}a_ix^i F=∑i=0aixi， F ′ = ∑ i = 0 a i + 1 ( i + 1 ) x i F'=\sum_{i=0}a_{i+1}(i+1)x^i F′=∑i=0ai+1(i+1)xi，根据 f = 4 x 2 − 12 x + 1 f=4x^2-12x+1 f=4x2−12x+1，可以得到 f ′ = 8 x − 12 f'=8x-12 f′=8x−12，展开 F ′ f F'f F′f 和 1 2 F f ′ \frac 1 2 Ff' 21Ff′： F ′ f = ∑ i = 0 ( 4 a i − 1 ( i − 1 ) − 12 a i i + a i + 1 ( i + 1 ) ) x i 1 2 F f ′ = ∑ i = 0 ( 4 a i − 1 − 6 a i ) x i 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 F′f=i=0∑(4ai−1(i−1)−12aii+ai+1(i+1))xi21Ff′=i=0∑(4ai−1−6ai)xi
由于两个多项式相等，即每一项系数都相等，于是可以得到等式： 4 a i − 1 ( i − 1 ) − 12 a i i + a i + 1 ( i + 1 ) = 4 a i − 1 − 6 a i a i + 1 = ( 12 i − 6 ) a i − 4 ( i − 2 ) a i − 1 i + 1 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} 4ai−1(i−1)−12aii+ai+1(i+1)=4ai−1−6aiai+1=i+1(12i−6)ai−4(i−2)ai−1
边界为 a 0 = 1 , a 1 = ( 12 × 0 − 6 ) a 0 0 + 1 = − 6 a_0=1,a_1=\dfrac {(12\times 0-6)a_0} {0+1}=-6 a0=1,a1=0+1(12×0−6)a0=−6。
不开 O 2 O2 O2， 44 m s 44ms 44ms，目前洛谷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); }