CSU-2173 Use FFT

Description

Bobo computes the product P(x)⋅Q(x)=$c_0 + c_1x + … + c_{n+m}x^{n + m}$ for two polynomials P(x)=$a_0 + a_1x + … + a_nx^n$ and Q(x)=$b_0 + b_1x + … + b_mx^m$. Find $ (c_L + c_{L + 1} + … + c_R) $ modulo ($10^9 $ + 7) for given L and R.

1 ≤ n, m ≤ 5 × $10^5$
0 ≤ L ≤ R ≤ n + m
0 ≤ $a_i, b_i$ ≤ $10^9$
Both the sum of n and the sum of m do not exceed $10^6$.

Input

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains four integers n, m, L, R.

The second line contains (n + 1) integers $a_0, a_1, …, a_n$.

The third line contains (m + 1) integers $b_0, b_1, …, b_m$.

Output

For each test case, print an integer which denotes the reuslt.

Sample Input

1 1 0 2

1 2

3 4

1 1 1 2

1 2

3 4

2 3 0 5

1 2 999999999

1 2 3 1000000000

Sample Output

题解

这题标题是Use FFT所以当然是用FFT做了(滑稽)

这题其实是个数学题+找规律题，借用一张图片

所以我们对b求前缀和，用a去乘，注意细节就好了

#include<bits/stdc++.h>

#define maxn 500050

#define p 1000000007

using namespace std;

typedef long long ll;

ll a[maxn], b[maxn];

ll pre[maxn * 2];

int main() {

	int n, m, l, r;

	while (scanf("%d%d%d%d", &n, &m, &l, &r) != EOF) {

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

			scanf("%lld", &a[i]);

		}

		for (int i = 1; i <= m + 1; i++) {

			scanf("%lld", &b[i]);

			pre[i] = (pre[i - 1] + b[i]) % p;

		}

		for (int i = m + 2; i <= r + 1; i++) {

			pre[i] = pre[i - 1];

		}

		ll ans = 0;

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

			ans = (ans + a[i] * (pre[r + 1] - pre[l] + p) % p) % p;

			if (l > 0) l--;

			if (r >= 0) r--;

		}

		printf("%lld\n", (ans + p) % p);

	}

	return 0;

}

巴特西

CSU-2173 Use FFT

CSU-2173 Use FFT

Description

Input

Output

Sample Input

Sample Output

题解

最新文章

热门文章