[人工智能]【UOJ500】任意基DFT——卷积、NTT、Bluestain算法

[UOJ500]任意基DFT

前言

一整天都耗在这题上了…

偷懒一时，却被迫勤奋一日

题解

这个给数据的方式，看似是为了随机，但是模数好巧不巧，居然和答案一样的取模 $998244353$，那么此处一定不是单纯为了随机的。于是可以不用往多点求值上面想了（我没往上面想单纯是因为我不会）。

显然答案为 $an{s}_i={\sum }_{n=0}^{N?1}{a}_n{q}_i^n$。

由于数列 $q$ 满足 $q_{n+1}=q_x{q}_n+q_y$，用 $\mathrm{B}\mathrm{a}\mathrm{l}\mathrm{l}$ 老师教的方法，可以求出它的通项为 $q_n=d{f}^n+g(d=q_0+\frac{q_y}{q_x?1},f=q_x,g=?\frac{q_y}{q_x?1})$。

然后代入答案中：
$$\begin{gathered} an{s}_i=\sum _{n=0}^{N?1}{a}_n{q}_i^n \\ =\sum _{n=0}^{N?1}{a}_n(d{f}^i+g{)}^n \\ =\sum _{n=0}^{N?1}{a}_n\sum _{j=0}^n(\genfrac{}{}{0ex}{}{n}{j})d^j{f}^{ij}{g}^{n?j} \\ =\sum _{n=0}^{N?1}{a}_n\sum _{j=0}^n\frac{n!}{j!(n?j)!}{d}^j{f}^{ij}{g}^{n?j} \\ =\sum _{n=0}^{N?1}{a}_{n}n!\sum _{j=0}^n\frac{(d{f}^i{)}^j}{j!}\frac{g^{n?j}}{(n?j)!} \\ =\sum _{j=0}^{N?1}\frac{d^j}{j!}{f}^{ij}\sum _{n=j}^{N?1}{a}_{n}n!\frac{g^{n?j}}{(n?j)!} \end{gathered}$$

后面那坨把前一半倒过来就是一个卷积形式，卷完后再和前面的合并，就可以化为以下形式：
$$an{s}_i=\sum _{n=0}^{N?1}{b}_n{f}^{ni}$$
用 $\mathrm{B}\mathrm{l}\mathrm{u}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{i}\mathrm{n}$ 算法，原式可以再次变换：
$$\begin{gathered} an{s}_i=\sum _{n=0}^{N?1}{b}_n{f}^{ni} \\ =\sum _{n=0}^{N?1}{b}_n{f}^{\left(\genfrac{}{}{0ex}{}{n+i}{2}\right)?\left(\genfrac{}{}{0ex}{}{n}{2}\right)?\left(\genfrac{}{}{0ex}{}{i}{2}\right)} \\ =f^{?\left(\genfrac{}{}{0ex}{}{i}{2}\right)}\sum _{n=0}^{N?1}{b}_n{f}^{?\left(\genfrac{}{}{0ex}{}{n}{2}\right)}{f}^{\left(\genfrac{}{}{0ex}{}{n+i}{2}\right)} \end{gathered}$$
这又是一个卷积形式，需要把前一半倒过来。总共做两次卷积，复杂度 $O((n+m)\log (n+m))$，$\mathrm{L}\mathrm{i}\mathrm{n}\mathrm{u}\mathrm{x}$ 一秒能过。

除了各种范围的倒换外，还需要特别注意的是，求组合数时现算就行了，一定不要患懒癌用你预处理的阶乘和逆元。组合数在指数那，模数是 $?(998244353)=998244352$，而预处理的阶乘逆元都是取模 $998244353$ 的。

代码

#include<bits/stdc++.h>//JZM yyds!!
#define ll long long
#define uns unsigned
#define IF (it->first)
#define IS (it->second)
using namespace std;
const int MAXN=3000005;
const ll INF=1e18;
inline ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[30],lpt;
inline void print(ll x,char c='\n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt)putchar(ptf[lpt--]^48);
	putchar(c);
}
const ll MOD=998244353;
inline ll ksm(ll a,ll b,ll mo){
	ll res=1;
	for(;b;b>>=1,a=a*a%mo)if(b&1)res=res*a%mo;
	return res;
}
ll fac[MAXN<<1],inv[MAXN<<1];
inline void init(int n){
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=n;i++)fac[i]=fac[i-1]*i%MOD;
	inv[n]=ksm(fac[n],MOD-2,MOD);
	for(int i=n-1;i>1;i--)inv[i]=inv[i+1]*(i+1)%MOD;
}
inline ll C(int n,int m){
	if(m>n||m<0)return 0;
	if(m==2)return (n*(n-1ll)>>1)%(MOD-1);
	return 0;//否则就不管了
}
//NTT-begin
#define g 3ll
int rev[MAXN<<1];
inline ll ad(ll a,ll b){
	a+=b;return a>=MOD?a-MOD:a;
}
ll omg[MAXN<<1];
inline int NTT(ll*a,int N,int inv){
	int bit=1,n=N;
	while((1<<bit)<n)bit++;
	n=(1<<bit);
	for(int i=0;i<n;i++){
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
		if(i<rev[i])swap(a[i],a[rev[i]]);
	}ll tmp,om,x,y;
	for(int m=1,mi=(MOD-1)>>1;m<n;m<<=1,mi>>=1){
		tmp=ksm(g,inv>0?mi:(MOD-1-mi),MOD),om=0;
		omg[0]=1;
		for(int i=1;i<m;i++)omg[i]=omg[i-1]*tmp%MOD;
		for(int i=0;i<n;i+=(m<<1),om=0)
			for(int j=i;j<i+m;j++,om++)
				x=a[j],y=omg[om]*a[j+m]%MOD,
				a[j]=ad(x,y),a[j+m]=(x-y+MOD)%MOD;
	}
	if(inv<0)
		for(int i=0,iv=ksm(n,MOD-2,MOD);i<n;i++)
			a[i]=a[i]*iv%MOD;
	return n;
}
#undef g
//NTT-end
ll d,f,g,q0,qx,qy,ans,a[MAXN<<1];//q_i=d*f^i+g
int n,m;
ll A[MAXN<<1],B[MAXN<<1],b[MAXN<<1];
ll miA[1000005],miB[1000005];
const ll BL=1000000;
inline void gin(){
	miA[0]=miB[0]=1;
	for(int i=1;i<=BL;i++)miA[i]=miA[i-1]*f%MOD;
	for(int i=1;i<=BL;i++)miB[i]=miB[i-1]*miA[BL]%MOD;
}
inline ll gsm(ll b){
	if(b>MOD-1||b<0)b=b%(MOD-1)+MOD-1;
	return miB[b/BL]*miA[b%BL]%MOD;
}
signed main()
{
	n=read()+1,m=read();
	for(int i=0;i<n;i++)a[i]=(read()%MOD+MOD)%MOD;
	q0=read(),qx=read(),qy=read();
	f=qx,g=qy*ksm(qx-1,MOD-2,MOD)%MOD;
	d=(q0+g)%MOD,g=(-g+MOD)%MOD;
	init(n+n+m),gin();
	for(int i=0;i<n;i++)A[i]=a[n-1-i]*fac[n-1-i]%MOD;
	B[0]=1;
	for(int i=1;i<n;i++)B[i]=B[i-1]*g%MOD;
	for(int i=1;i<n;i++)B[i]=B[i]*inv[i]%MOD;
	int N=NTT(A,n<<1,1);NTT(B,n<<1,1);
	for(int i=0;i<N;i++)A[i]=A[i]*B[i]%MOD;
	NTT(A,n<<1,-1);
	b[0]=1;
	for(int i=1;i<n;i++)b[i]=b[i-1]*d%MOD;
	for(int i=0;i<n;i++)b[i]=b[i]*inv[i]%MOD*A[n-1-i]%MOD;
	memset(A,0,sizeof(A));
	memset(B,0,sizeof(B));
	for(int i=0;i<n;i++)A[i]=b[i]*gsm(MOD-1-C(i,2))%MOD;
	for(int i=0;i<n-1-i;i++)swap(A[i],A[n-1-i]);
	for(int i=0;i<n+m;i++)B[i]=gsm(C(i,2));
	N=NTT(A,m+n+n,1),NTT(B,m+n+n,1);
	for(int i=0;i<N;i++)A[i]=A[i]*B[i]%MOD;
	NTT(A,m+n+n,-1);
	for(int k=1;k<=m;k++)
		ans^=gsm(MOD-1-C(k,2))*A[n-1+k]%MOD;
	print(ans);
	return 0;
}