牛客国庆集训派对Day4 F - NTT

题目链接:点击这里

 

解题思路:

f(x)的i阶导可以写为：

                                                                

那么总的式子就是：

                             

 

变换f(x)第i此导,使得式子对应第j位对应x的j次方的系数：

                                                          

i+j>=n时a[i+j]=0,,没影响.

设F(i)=a[i]*i!。

gd为g(x)的x的d次幂对应的系数是：

                              

令i=i+j，那么有：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int g = 3; 
const int mod = 998244353;
const int mx = 1<<18;
ll fac[mx],inv[mx],a[mx],b[mx];
int rev[mx],n;
void init()
{
	inv[0] = fac[0] = 1;
	inv[1] = fac[1] = 1;
	for(int i=2;i<mx;i++){
		fac[i] = fac[i-1]*i%mod;
		inv[i] = (mod-mod/i)*inv[mod%i]%mod;
	}
	for(int i=2;i<mx;i++) inv[i] = inv[i]*inv[i-1]%mod;
}
void get_rev(int len)
{
	for(int i=1;i<(1<<len);i++)
	rev[i] = (rev[i>>1]>>1)|((i&1)<<(len-1));
}
ll qpow(ll x,ll y)
{
	ll ans = 1;
	while(y){
		if(y&1) ans = ans*x%mod;
		y >>= 1;
		x = x*x%mod;
	}
	return ans;
}
void ntt(ll *p,int len,int v)
{
	for(int i=0;i<len;i++)
	if(i<rev[i]) swap(p[i],p[rev[i]]);
	for(int i=1;i<len;i<<=1){
		ll tep = qpow(g,(mod-1)/(2*i));
		if(v<0) tep = qpow(tep,mod-2);
		for(int j=0;j<len;j+=(i<<1)){
			ll mul = 1;
			for(int k=j;k<i+j;k++){
				ll x = p[k];
				ll y = mul*p[k+i]%mod;
				p[k] = (x + y)%mod;
				p[k+i] = (x - y + mod)%mod;
				mul = mul*tep%mod;
			}
		}
	}
	if(v==-1){
		ll invs = qpow(len,mod-2);
		for(int i=0;i<len;i++) p[i] = p[i]*invs%mod;
	}
}
int main()
{
	init();
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%lld",a+i);
		a[i] = a[i]*fac[i]%mod; 
		b[i] = inv[i];
	}
	int len = 1;
	while((1<<len)<2*n) len++;
	get_rev(len);
	len = 1<<len;
	ntt(a,len,1);ntt(b,len,1);
	for(int i=0;i<len;i++) a[i] = a[i]*a[i]%mod;
	for(int i=0;i<len;i++) b[i] = b[i]*b[i]%mod;
	ntt(a,len,-1);ntt(b,len,-1);
	for(int i=0;i<n;i++)
	printf("%lld%c",a[i+n-1]*b[i]%mod,i==n-1?'\n':' ');
	return 0;
}