题解 P6694 【强迫症】
Scarlet_Hypoc
·
·
题解
可能是一篇比较硬核的题解
容易想到的思路是分别考虑每一条边的贡献，设 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
令 $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，代码如下：
```cpp
#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);
}
```