QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#601473 | #9429. Subarray | ucup-team4474 | AC ✓ | 266ms | 188720kb | C++20 | 5.7kb | 2024-09-30 00:56:39 | 2024-09-30 00:56:40 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using namespace std;
const int P = 998244353;
using Poly = vector<int>;
#define MUL(a, b) (i64(a) * (b) % P)
#define ADD(a, b) (((a) += (b)) >= P ? (a) -= P : 0)
#define SUB(a, b) (((a) -= (b)) < 0 ? (a) += P : 0)
Poly getInv(int L)
{
Poly inv(L);
inv[1] = 1;
for (int i = 2; i < L; i++)
inv[i] = MUL((P - P / i), inv[P % i]);
return inv;
}
int POW(i64 a, int b = P - 2, i64 x = 1)
{
for (; b; b >>= 1, a = a * a % P)
if (b & 1)
x = x * a % P;
return x;
}
namespace NTT
{
const int g = 3;
Poly Omega(int L)
{
int wn = POW(g, P / L);
Poly w(L);
w[L >> 1] = 1;
for (int i = L / 2 + 1; i < L; i++)
w[i] = MUL(w[i - 1], wn);
for (int i = L / 2 - 1; i >= 1; i--)
w[i] = w[i << 1];
return w;
}
auto W = Omega(1 << 20);
void DIF(int *a, int n)
{
for (int k = n >> 1; k; k >>= 1)
for (int i = 0, y; i < n; i += k << 1)
for (int j = 0; j < k; j++)
y = a[i + j + k], a[i + j + k] = MUL(a[i + j] - y + P, W[k + j]), ADD(a[i + j], y);
}
void IDFT(int *a, int n)
{
for (int k = 1; k < n; k <<= 1)
for (int i = 0, x, y; i < n; i += k << 1)
for (int j = 0; j < k; j++)
x = a[i + j], y = MUL(a[i + j + k], W[k + j]),
a[i + j + k] = x - y < 0 ? x - y + P : x - y, ADD(a[i + j], y);
int Inv = P - (P - 1) / n;
for (int i = 0; i < n; i++)
a[i] = MUL(a[i], Inv);
reverse(a + 1, a + n);
}
}
namespace Polynomial
{
int norm(int n) { return 1 << (__lg(n - 1) + 1); }
void norm(Poly &a)
{
if (!a.empty())
a.resize(norm(a.size()), 0);
else
a = {0};
}
void DFT(Poly &a) { NTT::DIF(a.data(), a.size()); }
void IDFT(Poly &a) { NTT::IDFT(a.data(), a.size()); }
Poly &dot(Poly &a, Poly &b)
{
for (int i = 0; i < a.size(); i++)
a[i] = MUL(a[i], b[i]);
return a;
}
Poly operator*(Poly a, Poly b)
{
int n = a.size() + b.size() - 1, L = norm(n);
if (a.size() <= 8 || b.size() <= 8)
{
Poly c(n);
for (int i = 0; i < a.size(); i++)
for (int j = 0; j < b.size(); j++)
c[i + j] = (c[i + j] + (i64)a[i] * b[j] % P) % P;
return c;
}
a.resize(L), b.resize(L);
DFT(a), DFT(b), dot(a, b), IDFT(a);
return a.resize(n), a;
}
}
using namespace Polynomial;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
vector<array<int, 19>> b(n + 1);
map<int, vector<int>> pos;
vector<int> logn(n + 1, -1);
for (int i = 1; i <= n; i++)
{
logn[i] = logn[i >> 1] + 1;
pos[a[i]].push_back(i);
b[i][0] = a[i];
}
for (int j = 1; j <= 18; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
b[i][j] = max(b[i][j - 1], b[i + (1 << (j - 1))][j - 1]);
auto ask = [&](int l, int r) -> int
{
int s = logn[r - l + 1];
return max(b[l][s], b[r - (1 << s) + 1][s]);
};
Poly ans(n + 1);
auto solve = [&](auto &solve, int cur, int l, int r) -> void
{
if (l < cur)
{
int val = ask(l, cur - 1);
auto &t = pos[val];
vector<int> tmp{l - 1};
for (auto it = lower_bound(t.begin(), t.end(), l); it != t.end() and *it < cur; it++)
tmp.push_back(*it);
tmp.push_back(cur);
Poly f(tmp.size() - 1);
for (int j = 1; j < tmp.size(); j++)
f[j - 1] = tmp[j] - tmp[j - 1];
auto g = f;
reverse(g.begin(), g.end());
auto h = f * g;
int p = f.size();
for (int j = p - 1; j < p * 2 - 1; j++)
ADD(ans[j - p + 1], h[j]);
for (int j = 1; j + 1 < tmp.size(); j++)
{
if (j == 1)
solve(solve, tmp[j], tmp[j - 1] + 1, tmp[j + 1] - 1);
else
solve(solve, tmp[j], tmp[j], tmp[j + 1] - 1);
}
}
if (cur < r)
{
int val = ask(cur + 1, r);
auto &t = pos[val];
vector<int> tmp{cur};
for (auto it = lower_bound(t.begin(), t.end(), cur); it != t.end() and *it <= r; it++)
tmp.push_back(*it);
tmp.push_back(r + 1);
Poly f(tmp.size() - 1);
for (int j = 1; j < tmp.size(); j++)
f[j - 1] = tmp[j] - tmp[j - 1];
auto g = f;
reverse(g.begin(), g.end());
auto h = f * g;
int p = f.size();
for (int j = p - 1; j < p * 2 - 1; j++)
ADD(ans[j - p + 1], h[j]);
for (int j = 1; j + 1 < tmp.size(); j++)
{
if (j == 1)
solve(solve, tmp[j], tmp[j - 1] + 1, tmp[j + 1] - 1);
else
solve(solve, tmp[j], tmp[j], tmp[j + 1] - 1);
}
}
};
solve(solve, 0, 1, n);
int res = 0;
for (int i = 1; i <= n; i++)
res = (res + 1ll * i * ans[i] % P * ans[i] % P) % P;
cout << res << '\n';
}
/*
3
11
1 1 2 1 2 2 3 3 2 3 1
3
2024 5 26
3
1000000000 1000000000 1000000000
*/
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while (t--)
solve();
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 7164kb
input:
3 11 1 1 2 1 2 2 3 3 2 3 1 3 2024 5 26 3 1000000000 1000000000 1000000000
output:
2564 36 20
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 111ms
memory: 19212kb
input:
2522 12 642802746 634074578 642802746 634074578 642802746 634074578 634074578 642802746 740396295 634074578 740396295 634074578 16 305950462 400920468 400920468 305950462 400920468 305950462 400920468 400920468 400920468 400920468 305950462 305950462 400920468 305950462 305950462 305950462 2 4405082...
output:
3610 7545 9 1 50 1006 16170 5972 3117 540 540 4417 12885 336 3185 83 9272 27 1794 2776 1793 196 27 1377 8783 19723 5385 1864 3478 7101 1 431 825 4534 9900 162 21644 6 36 14088 306 9 57 1719 72 9 4637 68 16583 17701 19390 16282 5440 1 6 1716 19541 3823 2033 24 825 429 1911 11787 11388 12255 12175 126...
result:
ok 2522 lines
Test #3:
score: 0
Accepted
time: 149ms
memory: 44860kb
input:
1 400000 860350786 641009859 939887597 54748096 641009859 860350786 710156469 985188306 476927808 641009859 985188306 322595515 322595515 973764525 54748096 939887597 54748096 476927808 588586447 669240390 54748096 476927808 669240390 804928248 669240390 75475634 804928248 669240390 985188306 754756...
output:
300998364
result:
ok single line: '300998364'
Test #4:
score: 0
Accepted
time: 169ms
memory: 43788kb
input:
1 400000 860422965 880311831 389867323 711027909 603801945 977217669 127611088 468302420 100563882 896362064 321065270 937796491 106388135 679974087 799365054 508500258 155801089 72992050 568198964 469117950 605828088 147285088 931759705 335154243 123769214 717250374 123769214 588271814 193910044 58...
output:
642490751
result:
ok single line: '642490751'
Test #5:
score: 0
Accepted
time: 266ms
memory: 46688kb
input:
1 400000 489576972 624268112 792793292 261080167 299965397 570683924 43370033 865049228 160224484 597021302 799302320 154578623 616009875 817736437 422498140 177450324 576706528 701882608 322199948 469659816 265384591 886524303 331787804 922381773 642896492 36870304 922875786 328785523 506357505 778...
output:
728396411
result:
ok single line: '728396411'
Test #6:
score: 0
Accepted
time: 91ms
memory: 44360kb
input:
1 400000 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 79866982 798...
output:
805404149
result:
ok single line: '805404149'
Test #7:
score: 0
Accepted
time: 92ms
memory: 44084kb
input:
1 400000 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 4163012 416...
output:
871688808
result:
ok single line: '871688808'
Test #8:
score: 0
Accepted
time: 102ms
memory: 46260kb
input:
1 400000 7913 7913 7913 7913 7913 7913 7913 7913 7913 7913 7913 7913 7913 7913 7913 7913 7913 7913 7913 7913 7913 19512 844861162 178869991 19512 19512 19512 19512 19512 19512 19512 135989768 19512 19512 19512 19512 19512 19512 19512 19512 220217 220217 220217 220217 220217 220217 220217 220217 2202...
output:
470566238
result:
ok single line: '470566238'
Test #9:
score: 0
Accepted
time: 109ms
memory: 51144kb
input:
1 400000 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 2 2 1 2 1 2 1 1 2 1 2 2 1 2 1 2 2 1 1 1 1 2 1 1 1 2 1 1 2 2 1 1 1 1 2 2 1 1 1 2 1 2 1 2 2 1 2 2 2 1 1 2 2 1 2 2 1 1 1 1 2 2 1 1 1 1 2 1 2 2 1 2 1 1 2 2 1 1 2 2 2 1 2 2 2 2 1 2 1 2 1 1 2 2 2 1 1 1 2 1 1 1 1 2 2 2 1 1 2 2 1 2 2 1 1 1 2 1 2 2 2 1 1 2 1 2 1 1 2 2 2...
output:
188247686
result:
ok single line: '188247686'
Test #10:
score: 0
Accepted
time: 89ms
memory: 51300kb
input:
1 400000 1 1 1 1 1 2 2 1 1 1 2 2 1 2 2 1 2 1 1 2 1 1 2 1 2 2 1 2 2 1 2 2 2 1 2 1 2 2 2 1 1 1 2 2 1 2 2 1 1 1 2 1 2 1 2 2 1 2 1 2 1 1 1 2 2 1 1 2 2 2 1 1 2 2 2 2 2 2 2 1 2 2 1 2 1 1 2 1 2 1 2 1 1 1 1 2 1 1 2 2 1 1 1 2 2 1 2 1 1 1 2 1 1 2 1 1 1 1 1 2 1 1 1 2 2 1 2 2 1 1 1 2 1 1 1 1 2 1 1 1 2 1 2 1 2 2...
output:
534522621
result:
ok single line: '534522621'
Test #11:
score: 0
Accepted
time: 104ms
memory: 51312kb
input:
1 400000 2 2 1 1 1 2 1 1 2 2 1 1 1 1 1 1 1 1 2 1 2 2 1 2 2 2 2 1 1 2 1 2 1 1 2 2 2 2 1 2 1 2 1 1 1 2 2 1 2 1 1 1 2 1 1 2 2 1 1 2 2 2 2 2 2 2 1 2 2 2 1 1 1 2 2 1 2 2 2 2 2 1 1 1 1 2 1 2 1 1 1 1 2 1 1 1 2 1 1 2 2 2 1 2 2 1 2 1 2 2 1 2 2 1 1 2 1 2 1 1 2 1 1 2 1 2 1 2 2 2 1 2 2 1 1 2 1 2 2 2 1 2 1 1 2 1...
output:
315282614
result:
ok single line: '315282614'
Test #12:
score: 0
Accepted
time: 99ms
memory: 59244kb
input:
1 400000 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7...
output:
95707550
result:
ok single line: '95707550'
Test #13:
score: 0
Accepted
time: 116ms
memory: 52820kb
input:
1 400000 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 34618927 346...
output:
9261320
result:
ok single line: '9261320'
Test #14:
score: 0
Accepted
time: 89ms
memory: 52260kb
input:
1 400000 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 356559 3565...
output:
639541126
result:
ok single line: '639541126'
Test #15:
score: 0
Accepted
time: 102ms
memory: 62876kb
input:
1 400000 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 17752 130863 130863 130863 130863 130863 130863 130863 130863 130863 130863 130863 130863 130863 130863 130863 130863 130863 130863 130863 141618 141618 141618...
output:
910375995
result:
ok single line: '910375995'
Test #16:
score: 0
Accepted
time: 170ms
memory: 188720kb
input:
1 400000 2331 2331 18924 21959 27236 27236 30230 36415 36415 46142 53346 53346 61467 63373 63373 74413 75997 77628 79685 79685 85664 85664 85664 85837 87221 89355 89355 101697 101697 104022 104022 107252 107424 109721 116001 116001 116001 116888 117008 119514 121717 123822 123822 123822 128935 13039...
output:
830312990
result:
ok single line: '830312990'
Test #17:
score: 0
Accepted
time: 120ms
memory: 59472kb
input:
1 400000 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777...
output:
951683280
result:
ok single line: '951683280'
Test #18:
score: 0
Accepted
time: 108ms
memory: 59364kb
input:
1 400000 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777...
output:
146950933
result:
ok single line: '146950933'
Test #19:
score: 0
Accepted
time: 125ms
memory: 59132kb
input:
1 400000 777 777 777 228 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 167 777 777 777 777 777 777 777 133 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777 777...
output:
351398572
result:
ok single line: '351398572'
Extra Test:
score: 0
Extra Test Passed