约定：$[x^{n}]F(x)$​​​​​​表示多项式$F$​​​​​​的$n$​​​​​​次项系数

对于多项式$F$​​​​​​，定义$F$​​​​​的复合逆$hat{F}$​​​​​为满足$F(hat{F}(x))=x$​​​​​​的多项式

性质1：$F$​​​​​​​​存在复合逆的充要条件为$[x^{0}]F(x)=0$​​​​​​​​且$[x^{1}]F(x)
e 0$​​​​​​​​

性质2：若$F$​存在复合逆，则$hat{F}$​存在复合逆且复合逆为$F$​（那么显然$hat{F}$​​​满足性质1的条件）

拉格朗日反演：若$F$​​​​​存在复合逆，则$[x^{n}]hat{F}(x)=frac{1}{n}[x^{n-1}]frac{1}{F^{n}(x)}$​

另类拉格朗日反演：若$F$​​​存在复合逆，则$[x^{n}]hat{F}^{k}(x)=[x^{-(k+1)}]frac{F'(x)}{F^{n+1}(x)}$​

为了方便，将该式子变形，也即$[x^{n}]hat{F}^{k}(x)=[x^{n-k}]F'(x)(frac{x}{F(x)})^{n+1}$​​​​​

枚举其中非0的元素个数$i$，这$i$个数不在同一列上，即有${nchoose i}$种选法，同时其元素值有$(2c)^{i}$​种，接下来对于剩下的$n-i$​个0，只需要在剩下的$2n-i$个位置中任填即可

综上，即有$q_{n}=sum_{i=0}^{n}{nchoose i}(2c)^{i}{2n-ichoose n-i}=sum_{i=0}^{n}{nchoose i}(2c)^{i}{2n-ichoose n}$

考虑$q_{n}$的生成函数$Q(x)=sum_{nge 0}q_{n}x^{n}$​，由上式不难得到
$$
Q(x)=(2cx+1)^{n}sum_{ige 0}{i+nchoose n}x^{i}=(2cx+1)^{n}frac{1}{(1-x)^{n+1}}=frac{1}{2cx+1}(frac{2cx+1}{1-x})^{n+1}
$$
关于$sum_{ige 0}{i+nchoose n}x^{i}=frac{1}{(1-x)^{n-1}}$，将${n+ichoose i}$利用插板法理解为$i$个数划分为$n+1$个段（可以为0），利用生成函数即为$[x^{i}](sum_{jge 0}x^{j})^{n+1}=[x^{i}]frac{1}{(1-x)^{n+1}}$​​​​（当然也可以暴力展开验证）

将后者写成$frac{x}{F(x)}$​​​的形式，显然$F(x)=frac{x(1-x)}{2cx+1}$​​​，进而求导可得
$$
F'(x)=frac{(1-2x)(2cx+1)-2c(x-x^{2})}{(2cx+1)^{2}}=-frac{2cx^{2}+2x-1}{(2cx+1)^{2}}
$$
将$F'(x)$​​在$frac{1}{2cx+1}$​​​​​中提出，并代入另类拉格朗日反演的式子，即
$$
Q(x)=-frac{2cx+1}{2cx^{2}+2x-1}F'(x)(frac{x}{F(x)})^{n+1}=-frac{2chat{F}(x)+1}{2chat{F}^{2}(x)+2hat{F}(x)-1}
$$
考虑$F$​的复合逆$hat{F}(x)$​，将$F$​代入$F(hat{F}(x))=x$​并整理，即$hat{F}^{2}(x)+(2cx-1)hat{F}(x)+x=0$​​，再根据求根公式不难得到
$$
hat{F}(x)=frac{-(2cx-1)pmsqrt{Delta(x)}}{2}(Delta(x)=(2cx-1)^{2}-4x=4c^{2}x^{2}-4(c+1)x+1)
$$
代入$Q(x)$​​并计算，可得$Q(x)=Delta^{-frac{1}{2}}(x)$​​​，进而$2Delta Q’=2Delta(-frac{1}{2}Delta^{-frac{3}{2}}cdot Delta’)=-Delta’Q$

考虑两者的$n$​​次项系数，即
$$
8c^{2}(n-1)q_{n-1}-8(c+1)nq_{n}+2(n+1)q_{n+1}=-8c^{2}q_{n-1}+4(c+1)q_{n}
$$
整理后可得$q_{n+1}=frac{(2c+2)(2n+1)q_{n}-4c^{2}nq_{n-1}}{n+1}$​​​​​（初始$q_{0}=1$​​​​且$q_{1}=2c+2$​​​​）​

预处理逆元后即可$o(n)$​求解，总复杂度为$o(tn)$，可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 10000005
 4 #define mod 998244353
 5 #define ll long long
 6 int t,n,c,ans,inv[N],q[N];
 7 int main(){
 8     inv[0]=inv[1]=1;
 9     for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
10     scanf("%d",&t);
11     while (t--){
12         scanf("%d%d",&n,&c);
13         c=(c<<1)%mod,ans=0,q[0]=1,q[1]=(c+2)%mod;
14         for(int i=1;i<n;i++)q[i+1]=((ll)(c+2)*((i<<1)+1)%mod*q[i]-(ll)c*c%mod*i%mod*q[i-1]%mod+mod)%mod*inv[i+1]%mod;
15         for(int i=1;i<=n;i++)ans^=q[i];
16         printf("%d
",ans);
17     } 
18     return 0;
19 } 

View Code