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

21
18
5

这题标题是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

原文：https://www.cnblogs.com/artoriax/p/10349114.html