自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 22:24:23，当前版本为作者最后更新于2021-03-04 13:39:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\text{Link}$

板子题，极限卡常差评。

居然没有题解，就来写一篇吧。

upd2021.7.15：修式子和 $\LaTeX$。

题意

给 $n,m,c$ 和 $n-1$ 次多项式 $F(x)$，求出 $\forall k\in[0,m) F(c^k)$。

解法

首先我们有

$$F(c^k)=\sum_{i=0}^{n-1}a_ic^{ik}$$

考虑化 $ik$，

$$ik=\dfrac{2ik}{2}$$ $$=\dfrac{i^2+2ik+k^2-i-k-i^2+i-k^2+k}{2}$$ $$=\binom{i+k}{2}-\binom{i}{2}-\binom{k}{2}$$

于是就有

$$F(c^k)=\sum_{i=0}^{n-1}a_ic^{ik}$$ $$=\sum_{i=0}^{n-1}a_ic^{\binom{i+k}{2}-\binom{i}{2}-\binom{k}{2}} $$$$=c^{-\binom{k}{2}}\sum_{i=0}^{n-1}a_ic^{-\binom{i}{2}}c^{\binom{i+k}{2}} $$

可以卷积。

见模数为 $998244353$ 的版本。

模数不对就用 $\text{MTT}$，时间复杂度 $O(n\log n)$。

---

然而这道题还没结束，我们发现了时限 1.23s 空限 345MB，没错，这道题卡时间+卡空间。

下面给出本题卡常的几个技巧：

• $\text{MTT}$ 必须用 $4$ 次 $\text{FFT}$,不知道三模 $\text{NTT}$ 能不能过，好像在板子题道三模 $\text{NTT}$ 时间和空间都比 $\text{MTT}$ 优秀。
• 手动二分数组大小，$N=2.1\times 10^6$ 左右就行了。
• 预处理单位根幂。
• 开 double 而不是 long double。
• 有良好的编码习惯，只在乘法时开 long long，数组开 int，加减法尽量少使用 % 运算。
• fread，fwrite 快读快写。
• 在夜深人静的时候交/多交亿次等评测机波动。

为了方便各位神仙调试，这里给出大部分代码：

#define ll long long
#define ld double
const ld pi=acos(-1);
const int mod=1e9+7,N=2.1e6;
inline void print(int *a){
	for(int i=0;a[i]||a[i+1]||a[i+2]||a[i+3]||a[i+4]||a[i+5];i++){
		printf("%d ",a[i]);
	}
	puts("");
}
struct comp{
	double x,y;
	comp(ld a=0,ld b=0){x=a,y=b;}
	comp neg(){
		return comp(x,-y);
	}
	friend comp operator+(const comp &a,const comp &b){
		return comp(a.x+b.x,a.y+b.y);
	}
	friend comp operator-(const comp &a,const comp &b){
		return comp(a.x-b.x,a.y-b.y);
	}
	friend comp operator*(const comp &a,const comp &b){
		return comp(a.x*b.x-a.y*b.y,a.y*b.x+a.x*b.y);
	}
};
struct ntt{
	comp A[N],B[N],C[N],D[N],qp[N];
	int n,rev[N],f[N],g[N],lim,c[N],ic[N];
	int m,_c;
	inline void init(int n,int mode=1){
		if(mode){
			int l=0;
			for(lim=1;lim<=n;lim<<=1)l++;
			for(int i=1;i<lim;i++){
				rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
			}
			for(int i=1;i<lim;i<<=1){
				for(int j=0;j<i;j++){
					qp[lim/i*j]=comp(cos(j*pi/i),sin(j*pi/i));
				}
			}
		}else{
			for(lim=1;lim<=n;lim<<=1);
		}
	}
	inline int qpow(int x,int y){
		int res=1;
		while(y){
			if(y&1) res=1ll*res*x%mod;
			x=1ll*x*x%mod;
			y>>=1;
		}
		return res;
	}
	inline void FFT(comp *a,int tpe){
		for(int i=0;i<lim;i++){
			if(i<rev[i]){
				swap(a[i],a[rev[i]]);
			}
		}
		for(int i=1;i<lim;i<<=1){
			for(int j=0;j<lim;j+=(i<<1)){
				for(int k=0;k<i;k++){
					comp t=a[i+j+k]*(tpe==1?qp[lim/i*k]:qp[lim/i*k].neg());
					a[i+j+k]=a[j+k]-t;
					a[j+k]=a[j+k]+t;
				}
			}
		}
	}
	inline void MTT(int *f,int *g,int *ans){
		for(int i=0;i<lim;i++){
			A[i].x=f[i]>>15,A[i].y=f[i]&32767;
			C[i].x=g[i]>>15,C[i].y=g[i]&32767;
		}
		FFT(A,1);
		FFT(C,1);
		for(int i=1;i<lim;i++){
			B[i]=A[lim-i].neg();
		}
		B[0]=A[0].neg();
		for(int i=1;i<lim;i++){
			D[i]=C[lim-i].neg();
		}
		D[0]=C[0].neg();
		for(int i=0;i<lim;i++){
			comp aa=(A[i]+B[i])*comp(0.5,0);
			comp bb=(A[i]-B[i])*comp(0,-0.5);
			comp cc=(C[i]+D[i])*comp(0.5,0);
			comp dd=(C[i]-D[i])*comp(0,-0.5);
			A[i]=aa*cc+comp(0,1)*(aa*dd+bb*cc);
			B[i]=bb*dd;
		}
		FFT(A,-1);
		FFT(B,-1);
		for(int i=0;i<lim;i++){
			int aa=(ll)(A[i].x/lim+0.5)%mod;
			int bb=(ll)(A[i].y/lim+0.5)%mod;
			int cc=(ll)(B[i].x/lim+0.5)%mod;
			ans[i]=((1ll*aa*(1<<30)+1ll*bb*(1<<15)+cc)%mod+mod)%mod;
		}
	}
	inline void MAIN(){
		n=read(),_c=read(),m=read();
		c[0]=ic[0]=1;
		for(int i=1;i<=n+m;i++){
			c[i]=1ll*c[i-1]*_c%mod;
		}
		for(int i=1;i<=n+m;i++){
			c[i]=1ll*c[i-1]*c[i]%mod;
		}
		ic[1]=qpow(_c,mod-2);
		int qq=ic[1];
		for(int i=1;i<=max(n,m);i++){
			ic[i]=1ll*ic[i-1]*qq%mod;
		}
		for(int i=1;i<=max(n,m);i++){
			ic[i]=1ll*ic[i-1]*ic[i]%mod;
		}
		f[0]=read();
		for(int i=1;i<n;i++){
			f[i]=1ll*read()*ic[i-1]%mod;
		}
		init(n+m);
		g[0]=1;
		for(int i=1;i<=n+m;i++){
			g[i]=c[i-1];
		}
		reverse(f,f+n+1);
		MTT(f,g,f);
		for(int i=0;i<m;i++){
			write((long long)f[i+n]*(i?ic[i-1]:1)%mod);
			out[len++]=' ';
		}
	}
}w;

最慢点 1.23s（没错卡常卡到这种程度），最大空间 196.23MB。

希望各位卡常愉快，早日卡过~。

若有问题请私信/评论。

---

再见 qwq~