Contest Hunter - Handle

タイトル:
b[i]=ΣC[j][i]*a[j];
0<=i<=n,i<=j<=n;
ここでb[i]、a[i]、型取り998244353を与える.
この問題はch【弱省胡策】Round#5試合のT 3である.
問題:
関数多項式とかを生成します.の本当に毒腫ですね.
まず組合せ数を分解し,b[i]=Σ(j!/(j-i)!/を得る.i!)*a[j];(i<=j<=n)
同乗i!,b[i]*i!=∑a[j]*j!/(j-i)!;(i<=j<=n)
再定義B[i]=b[i]*i!,A[i]=a[i]*i!;(i<=j<=n)
原式化:B[i]=ΣA[j]/(j-i)!(i<=j<=n)
すでに畳み込みの形に近いので、A[i],B[i]を反転させ、F[i]=B[n-i],G[i]=A[n-i];
これがF[i]=ΣG[j]/(i-j)!;(0<=j<=i)
私たちはそれを生成関数の形式に列挙します.
F(x)をF[i]の生成関数、G(x)をG[i]の生成関数、K(x)を1/iにします!の生成関数です.
したがって、方程式はF(x)=K(x)*G(x)であり、G(x)を要求する.の
このようにK(x)をあちらに移してF(x)でK(x)を除去すればよい.
しかし、私も多項式除算はできません.
K(x)=1/0!+x/1!+x^2/2!+x^3/3!+...+x^∞/∞!=e^x;
これがあのマクローリン展開なのか、過去を除いてe^(-x)の多項式展開を求めた後の表現です.
xの前にマイナス記号を付けるのは明らかに奇数項にしか影響しないので、K^(-1)(x)=1/0!-x/1!+x^2/2!-x^3/3!+...+x^∞/∞!;
そしてこれをF(x)と乗じて、式を作って答えが出てきました!
複雑度はNTTのO(nlogn);
コード:

#include
#include
#include
#define N 262144<<1
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll a[N],b[N],c[N];
ll tb[N],ans[N],fact[N];
ll pow(ll x,ll y)
{
	ll ret=1;
	while(y)
	{
		if(y&1)
			ret=ret*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ret;
}
void NTT(ll* a,int len,int type)
{
	int i,j,h,t;
	for(i=0,t=0;it)	swap(a[i],a[t]);
		for(j=(len>>1);(t^=j)>=1);
	}
	for(h=2;h<=len;h<<=1)
	{
		ll wn=pow(3,(mod-1)/h);
		for(i=0;i>1);j++,w=w*wn%mod)
			{
				ll temp=w*a[i+j+(h>>1)]%mod;
				a[i+j+(h>>1)]=(a[i+j]-temp+mod)%mod;
				a[i+j]=(a[i+j]+temp)%mod;
			}
		}
	}
	if(type==-1)
	{
		for(i=1;i>1);i++)
			swap(a[i],a[len-i]);
	}
}
void slove(ll* a,ll* b,int len)
{
	NTT(a,len,1),NTT(b,len,1);
	for(int i=0;i>=1)
		if(n&i)
			{m=(i<<1);break;}
	m<<=1;
	slove(a,b,m);
	for(i=0;i