洛谷 P3711 - 仓鼠的数学题（多项式）

提供一种不太一样的做法。

假设要求的多项式为 \(f(x)\)。我们考察 \(f(x)-f(x-1)\)，不难发现其等于 \(\sum\limits_{i=0}^na_ix^i\)

考虑设 \(f(x)=\sum\limits_{i=0}^{n+1}b_ix^i\)，那么直接代入 \(x-1\) 并化简可以得到：

\[\begin{aligned}
f(x-1)&=\sum\limits_{i=0}^{n+1}b_i(x-1)^i\\
&=\sum\limits_{i=0}^{n+1}b_i\sum\limits_{j=0}^i\dbinom{i}{j}(-1)^{i-j}x^j\\
&=\sum\limits_{i=0}^{n+1}(\sum\limits_{j=i}^{n+1}\dbinom{j}{i}(-1)^{j-i}b_j)x^i
\end{aligned}
\]

故

\[\begin{aligned}
f(x)-f(x-1)&=\sum\limits_{i=0}^{n+1}(\sum\limits_{j=i+1}^{n+1}\dbinom{j}{i}(-1)^{j-i}b_j)x^i
\end{aligned}
\]

根据 \(f(x)-f(x-1)=\sum\limits_{i=0}^na_ix^i\) 可得

\[\sum\limits_{j=i+1}^{n+1}\dbinom{j}{i}(-1)^{j-i}b_j=a_i
\]

按照套路拆组合数：

\[\dfrac{1}{i!}\sum\limits_{j=i+1}^{n+1}(j!·b_j)·(\dfrac{1}{(j-i)!}(-1)^{j-i})=a_i
\]

设

\[f_i=i!·b_i
\]

\[g_i=\dfrac{1}{i!}(-1)^i,g_0=0
\]

\[h_i=a_i·i!
\]

那么上式可以写作：

\[h_i=\sum\limits_{x-y=i}f_xg_y
\]

喜闻乐见的减法卷积，按照套路设

\[f'_i=f_{n+1-i},h'_i=h_{n+1-i}
\]

那么有 \(h'\) 为 \(f'\) 与 \(g\)，按照常理是一遍求逆就可以解决的事，但是非常悲催的是 \(g_0=0\)，因此无法直接求逆，不过注意到对于 \(f'\) 和 \(h'\) 同样有它们的第 \(0\) 项为 \(0\)，因此可以将数组全部向前平移一位然后求逆。还有就是原数组是 \(n+1\) 次多项式，平移以后变成了 \(n\) 次多项式，因此我们可以大致确定的 \(f_i\) 只有 \(n+1\) 位，怎么办呢？首先注意到 \(f'_{n+1}=b_0\)，也就是待求多项式的常数项，因此我们可以代入 \(x=0\) 求得 \(f'_{n+1}=a_{0}\)。还有就是由于你对 \(f',g\) 卷积是在 \(\bmod x^{n+1}\) 意义下进行，并且 \(g_0=0\)，因此理论上来说 \(f'_n\) 是不能通过 \(f'\) 与 \(g\) 卷积为 \(h'\) 这一条件确定的，不过注意到多项式求逆的过程中如果我们固定住 \(f'_0\)，那么所有数都可表示为 \(f'_i=v_i·\dfrac{1}{f'_0}\) 的形式，其中 \(v_i\) 为常数，也就是说我们求出来的 \(f'\) 与真正的 \(f'\) 是存在比例关系的，因此我们考虑代入 \(x=1\) 求出待求多项式的系数和，这样即可求出真正的 \(f'\) 相较于我们求出的 \(f'\) 缩放了多少倍，也就可以求出真正的 \(f'\)。

时间复杂度 \(n\log n\)。

const int pr=3;

const int ipr=332748118;

const int MAXN=255555;

const int MAXP=524288;

int n,fac[MAXN+5],ifac[MAXN+5];

void init_fac(int n){

	for(int i=(fac[0]=ifac[0]=ifac[1]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;

	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;

}

int qpow(int x,int e){

	int ret=1;

	for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;

	return ret;

}

int rev[MAXP+5];

void NTT(vector<int> &a,int len,int type){

	int lg=31-__builtin_clz(len);

	for(int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<lg-1);

	for(int i=0;i<len;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);

	for(int i=2;i<=len;i<<=1){

		int W=qpow((type<0)?ipr:pr,(MOD-1)/i);

		for(int j=0;j<len;j+=i){

			for(int k=0,w=1;k<(i>>1);k++,w=1ll*w*W%MOD){

				int X=a[j+k],Y=1ll*w*a[(i>>1)+j+k]%MOD;

				a[j+k]=(X+Y)%MOD;a[(i>>1)+j+k]=(X-Y+MOD)%MOD;

			}

		}

	} if(!~type){

		int ivn=qpow(len,MOD-2);

		for(int i=0;i<len;i++) a[i]=1ll*a[i]*ivn%MOD;

	}

}

vector<int> conv(vector<int> a,vector<int> b){

	int LEN=1;while(LEN<a.size()+b.size()) LEN<<=1;

	a.resize(LEN,0);b.resize(LEN,0);NTT(a,LEN,1);NTT(b,LEN,1);

	for(int i=0;i<LEN;i++) a[i]=1ll*a[i]*b[i]%MOD;

	NTT(a,LEN,-1);return a;

}

vector<int> getinv(vector<int> a,int len){

	vector<int> b(len,0);b[0]=qpow(a[0],MOD-2);

	for(int i=2;i<=len;i<<=1){

		vector<int> c(b.begin(),b.begin()+(i>>1));

		vector<int> d(a.begin(),a.begin()+i);

		c=conv(conv(c,c),d);

		for(int j=0;j<i;j++) b[j]=(2ll*b[j]-c[j]+MOD)%MOD;

	} return b;

}

vector<int> A,B;

int res[MAXN+5];

int main(){

	scanf("%d",&n);init_fac(MAXN);A.resize(n+2);int sum=0;

	for(int i=n;~i;i--) scanf("%d",&A[i]),sum=(sum+A[i])%MOD,A[i]=1ll*A[i]*fac[n-i]%MOD;

	B.resize(n+2);for(int i=1;i<=n+1;i++) B[i-1]=(i&1)?(MOD-ifac[i]):ifac[i];

	int LEN=1;while(LEN<=n+2) LEN<<=1;

	A.resize(LEN,0);B.resize(LEN,0);

	vector<int> C=conv(A,getinv(B,LEN));

//	printf("A: ");for(int i=0;i<n+1;i++) printf("%d%c",A[i]," \n"[i==n]);

//	printf("B: ");for(int i=0;i<n+1;i++) printf("%d%c",B[i]," \n"[i==n]);

	for(int i=1;i<=n+1;i++) res[i]=1ll*C[n+1-i]*ifac[i]%MOD;

	res[0]=A[n];int iv=qpow(res[n+1],MOD-2);

	for(int i=1;i<=n+1;i++) res[i]=1ll*res[i]*iv%MOD;

	int ssum=0;for(int i=1;i<=n+1;i++) ssum=(ssum+res[i])%MOD;

	int mul=1ll*sum*qpow(ssum,MOD-2)%MOD;

	for(int i=1;i<=n+1;i++) res[i]=1ll*res[i]*mul%MOD;

	for(int i=0;i<=n+1;i++) printf("%d%c",res[i]," \n"[i==n+1]);

	return 0;

}

巴特西

洛谷 P3711 - 仓鼠的数学题（多项式）

最新文章

热门文章