BZOJ2194 快速傅立叶之二 < FFT >

Posted on Symbols count in article: 298 Reading time ≈ 1 mins.

Problem

快速傅立叶之二

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  259  MB\mathrm{Memory\;Limit:\;259\;MB}

Description

请计算c[k]=∑i=1na[i]⋅b[i−k]c[k]=\sum_{i=1}^{n}a[i]\cdot b[i-k]其中k≤i<nk\le i<n，并且有n≤105n\le10^5。
a,ba,b中的元素均为小于等于100100的非负整数。

Input

第一行一个整数NN，接下来NN行，每行两个数，依次表示a[i],b[i]  (0≤i<N)a[i],b[i]\;(0\le i<N)。

Output

输出NN行，每行一个整数，第ii行输出c[i−1]c[i-1]。

Sample Input

1
2
3
4
5
6
5
3 1
2 4
1 1
2 4
1 4

Sample Output

1
2
3
4
5
24
12
10
6
1

标签：FFT

Solution

FFT\mathrm{FFT}裸题。

ck=∑i=1n∑j=1nai⋅bj⋅[i−j=k]=∑i=1n∑j=−n−1ai⋅b−j⋅[i+j=k]\begin{aligned} c_k&=\sum_{i=1}^{n}\sum_{j=1}^{n}a_i\cdot b_j\cdot[i-j=k]\\ &=\sum_{i=1}^{n}\sum_{j=-n}^{-1}a_i\cdot b_{-j}\cdot[i+j=k]\\ \end{aligned}

将bb的下标变为负值做FFT\mathrm{FFT}即可，变为负值可以直接将数组整体右移。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
#define MOD 9999991
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n;    lnt ans = 1;
int main() {
    read(n);
    for (int i = 1; i <= n-2; i++) (ans *= 1LL*n) %= MOD; 
    for (int i = 1; i <= n-1; i++) (ans *= 1LL*i) %= MOD;
    return printf("%lld\n", ans), 0;
}