[ZJOI2014] 力 - 多项式乘法 FFT

题意：给定 \({q_i}\)，求

\[E_i = \sum_{i<j}{\frac{q_j}{(j-i)^2}} - \sum_{i>j}{\frac{q_j}{(j-i)^2}}
\]

Solution: 我们令

\[p_i = \frac{1}{(j-i)^2}
\]

那么很容易将\(E_i\)处理为卷积形式

\[E_i = \sum_{i<j}{p_{j-i}q_j} - \sum_{i>j}{p_{i-j}q_j}
\]

可以暴力地把两边分开处理，不需要的区域直接置为\(0\)，对于下标出现负数的暴力加上一个\(n\)即可。最终我们将答案转化为

\[E_i = \sum_{i<j}{p_{j-i}q'_{n-i-1}} - \sum_{i>j}{p_{i-j}q_j}
\]

其中 \(q'\) 是\(q\)的翻转序列，即 \(q'_i=q_{n-i-1}\) 。

之所以在这个算式里仍然需要考虑负数下标，是因为我们在做卷积的时候无法对 \(i<j\) 和 \(i>j\) 这样的约束进行满足，因此我们将 \(p\) 序列整体平移一个 \(n\) 即可。

poly p,q;

int main() {

	int n;

	scanf("%d",&n);

	q.read(n-1);

	p.c.resize(n+n);

	for(int i=0;i<=n;i++) p.c[i]=0;

	for(int i=1;i<n;i++) p.c[n+i]=1.0/((double)i*(double)i);

	poly A=p*q;

	reverse(q.c.begin(),q.c.end());

	poly B=p*q;

	for(int i=0;i<n;i++) {

		printf("%.3lf\n",-B.c[2*n-i-1]+A.c[n+i]);

	}

}

当然很容易发现这样做毫无必要。既然我们已经对下标为负数的情况做了处理，不妨顺便把它利用上。

poly p,q;

int main() {

	int n;

	scanf("%d",&n);

	q.read(n-1);

	p.c.resize(n+n);

	for(int i=1;i<n;i++)

		p.c[n+i]=1.0/((double)i*(double)i),

		p.c[n-i]=-1.0/((double)i*(double)i);

	poly A=p*q;

	for(int i=0;i<n;i++) {

		printf("%.3lf\n",A.c[n+i]);

	}

}

巴特西

[ZJOI2014] 力 - 多项式乘法 FFT

最新文章

热门文章