求问 exp 多项式长度
查看原帖
求问 exp 多项式长度
131591
蒟蒻君HJT泽渡透香楼主2022/7/6 23:58

先放部分代码::

void exp(int *A, int *B, int m){
	m *= 2;
	int F[m << 2], H[m << 2], G[m << 2], K[m << 2];
	memset(F, 0, sizeof(int) * m * 4);
	memset(G, 0, sizeof(int) * m * 4);
	memset(K, 0, sizeof(int) * m * 4);
	memset(H, 0, sizeof(int) * m * 4);
	G[0] = 1;
	int limit = 1;
	while(limit < m){
		for(int i = 0; i < limit; ++i) H[i] = G[i];
		for(int i = limit; i < (limit << 1); ++i) H[i] = 0;
		for(int i = 0; i < limit; ++i) G[i] = 0;
		ln(H, K, limit);
		G[0] = 1;
		for(int i = 0; i < (limit << 1); ++i){
			G[i] = minus(G[i], K[i]);
			G[i] = add(G[i], A[i]);
		}
		work2(G, H, limit << 2);
		limit <<= 1; 
	}
	for(int i = 0; i < m; ++i) B[i] = G[i];
	return ;
}
int a[N], Ans[N], n;
signed main(){
	scanf("%d", &n);
	for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
	Inv[0] = Inv[1] = 1;
	for(int i = 2; i <= n; ++i) Inv[i] = mul(mod - mod / i, Inv[mod % i]);
	exp(a, Ans, n);
	for(int i = 0; i < n; ++i) printf("%d ", Ans[i]);
	printf("\n");
	return 0;
}

如果 exp 函数开头不写

m *= 2

求出的 exp 的 x4,x5x^4,x^5 项系数就会错误,为什么呢?

2022/7/6 23:58
加载中...