QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#397293 | #3749. Use FFT | SamponYW | AC ✓ | 88ms | 7892kb | C++14 | 1.4kb | 2024-04-23 21:33:21 | 2024-04-23 21:33:22 |
Judging History
answer
#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 500005
#define P 1000000007
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
int s = 1;
while(n) {
if(n & 1) s = 1ll * s * p % P;
p = 1ll * p * p % P, n >>= 1;
}
return s;
}
int n, m, L, R;
int a[N], b[N];
il int calc(int x) {
int s = 0;
FOR(i, 0, min(m, x)) addr(s, 1ll * b[i] * a[min(n, x - i)] % P);
return s;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
while(cin >> n >> m >> L >> R) {
FOR(i, 0, n) cin >> a[i], addr(a[i], a[i - 1]);
FOR(i, 0, m) cin >> b[i];
cout << add(calc(R), P - calc(L - 1)) << "\n";
}
cerr << 1.0 * clock() / CLOCKS_PER_SEC;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 88ms
memory: 7892kb
input:
121 285 293 344 72406343 29062835 764055826 405957571 16850604 195010152 172508328 95932334 831517980 743997761 105129557 514312920 823346977 323074892 692747568 19841766 27687784 347985813 687459437 105444325 409463081 290623333 617535612 772316325 337644791 385678680 277673818 798282616 401321010 ...
output:
844655532 265155792 721082700 495929230 51368183 333395998 317686334 360990019 417166860 777286141 790612844 963001524 160679555 18876664 993526858 577807872 57755040 386940508 941107272 983715250 846414206 784228123 996873567 716573418 156108377 323145621 213071341 252732267 964022445 861123759 102...
result:
ok 1001 numbers