QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#119782 | #2618. Casual Dancers | Scarlett_boy | AC ✓ | 201ms | 20296kb | C++17 | 4.9kb | 2023-07-05 19:03:46 | 2023-07-05 19:03:49 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize(3, "Ofast", "inline")
using namespace std;
typedef long long ll;
template<const int Mod>
struct ntt {
inline void add(int &a, int b) {
a += b;
if (a >= Mod) a -= Mod;
}
inline void sub(int &a, int b) {
a -= b;
if (a < 0) a += Mod;
}
inline int add2(int a, int b) {
a += b;
if (a >= Mod) a -= Mod;
return a;
}
inline int sub2(int a, int b) {
a -= b;
if (a < 0) a += Mod;
return a;
}
inline int mul(int a, int b) { return (1ll * a * b % Mod); }
inline int powmod(int a, long long b) {
int res = 1;
while (b > 0) {
if (b & 1) res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
inline int inv(int a) {
a %= Mod;
if (a < 0) a += Mod;
int b = Mod, u = 0, v = 1;
while (a) {
int t = b / a;
b -= t * a;
swap(a, b);
u -= t * v;
swap(u, v);
}
assert(b == 1);
if (u < 0) u += Mod;
return u;
}
int limit, root;
vector<int> A, B;
ntt() {
int tmp = Mod - 1;
limit = 0;
while (tmp % 2 == 0) {
tmp /= 2;
limit++;
}
root = 2;
while (powmod(root, (Mod - 1) >> 1) == 1) root++;
A.resize(limit);
B.resize(limit);
for (int i = 0; i < limit; ++i) {
sub(A[i], powmod(root, (Mod - 1) >> (i + 2)));
B[i] = inv(A[i]);
}
}
void fft(vector<int> &a, bool inv) {
const int n = a.size();
assert((n & (n - 1)) == 0);
assert(__builtin_ctz(n) <= limit);
if (!inv) {
for (int m = n; m >>= 1;) {
int w = 1;
for (int s = 0, k = 0; s < n; s += 2 * m) {
for (int i = s, j = s + m; i < s + m; ++i, ++j) {
int x = a[i], y = mul(a[j], w);
a[j] = (x >= y ? x - y : x + Mod - y);
a[i] = (x + y >= Mod ? x + y - Mod : x + y);
}
w = mul(w, A[__builtin_ctz(++k)]);
}
}
} else {
for (int m = 1; m < n; m *= 2) {
int w = 1;
for (int s = 0, k = 0; s < n; s += 2 * m) {
for (int i = s, j = s + m; i < s + m; ++i, ++j) {
int x = a[i], y = a[j];
a[j] = (x >= y ? x - y : x + Mod - y);
a[j] = mul(a[j], w);
a[i] = (x + y >= Mod ? x + y - Mod : x + y);
}
w = mul(w, B[__builtin_ctz(++k)]);
}
}
}
}
vector<int> multiply(vector<int> a, vector<int> b, int eq = 0) {
int need = a.size() + b.size() - 1;
int nbase = 0;
while ((1 << nbase) < need) nbase++;
int sz = 1 << nbase;
a.resize(sz);
b.resize(sz);
fft(a, 0);
if (eq) b = a; else fft(b, 0);
int inv_sz = inv(sz);
for (int i = 0; i < sz; i++) {
a[i] = mul(mul(a[i], b[i]), inv_sz);
}
fft(a, 1);
a.resize(need);
return a;
}
vector<int> square(vector<int> a) {
return multiply(a, a, 1);
}
};
const int mod = 998244353;
int x[4];
int k, p;
#define Poly vector<int>
inline int powmod(int a, long long b) {
int res = 1;
while (b > 0) {
if (b & 1) res = 1ll * res * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return res;
}
void solve() {
for (int i = 1; i <= 3; i++) cin >> x[i];
cin >> k >> p;
ntt<mod> t;// mod为对应的模数
Poly A, res;
A.resize(3);
A[0] = A[1] = A[2] = powmod(3, mod - 2);
res.resize(1);
res[0] = 1;
int b = k;
while (b) {
if (b & 1) res = t.multiply(res, A);
b >>= 1;
A = t.multiply(A, A);
}
ll L1 = x[1] - x[2], L2 = x[1] - x[3], L3 = x[2] - x[3];
ll Ans = 0;
for (int i = 0; i < res.size(); i++) {
ll d = i - k;
Ans = (Ans + (abs(L1 + d) + abs(L2 + d) + abs(L3 + d)) % mod * res[i] % mod) % mod;
}
cout << Ans * powmod(2, mod - 2) % mod << "\n";
// max( a , b , c ) - min( a , b , c ) = 0.5 * ( | a - b | + | b - c | + | c - a |)
// 每一次我会随机在(a,b,c) 中选择一个
// 有 p 的概率 + 1
// 有 1-p 的概率 - 1
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _ = 1;
// cin >> _;
for (int o = 1; o <= _; o++) {
// cout << "Case #<<" << o << ": ";
solve();
}
return 0;
}
/*
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3400kb
input:
0 0 0 1 58
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
1 2 2 1 100
output:
332748119
result:
ok 1 number(s): "332748119"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3440kb
input:
5 2 3 4 50
output:
160212060
result:
ok 1 number(s): "160212060"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3416kb
input:
-2 -1 1 2 71
output:
443664160
result:
ok 1 number(s): "443664160"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
-1 0 -1 4 8
output:
751764268
result:
ok 1 number(s): "751764268"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3412kb
input:
-2 -2 2 5 54
output:
801060288
result:
ok 1 number(s): "801060288"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3404kb
input:
-2 2 4 8 36
output:
353135983
result:
ok 1 number(s): "353135983"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
8 -7 1 7 28
output:
15
result:
ok 1 number(s): "15"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
-7 -8 0 16 54
output:
159363041
result:
ok 1 number(s): "159363041"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
5 11 -11 9 32
output:
717226646
result:
ok 1 number(s): "717226646"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3472kb
input:
-16 1 -9 32 8
output:
855967855
result:
ok 1 number(s): "855967855"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3468kb
input:
-13 28 28 37 80
output:
116405794
result:
ok 1 number(s): "116405794"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
6 26 -25 64 21
output:
91053409
result:
ok 1 number(s): "91053409"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3404kb
input:
-39 23 1 31 64
output:
742331784
result:
ok 1 number(s): "742331784"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
-32 42 43 128 87
output:
57822539
result:
ok 1 number(s): "57822539"
Test #16:
score: 0
Accepted
time: 1ms
memory: 3444kb
input:
-80 55 -106 142 29
output:
435655440
result:
ok 1 number(s): "435655440"
Test #17:
score: 0
Accepted
time: 1ms
memory: 3464kb
input:
0 -83 -106 256 55
output:
120508896
result:
ok 1 number(s): "120508896"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
-100 -123 -167 91 74
output:
285780715
result:
ok 1 number(s): "285780715"
Test #19:
score: 0
Accepted
time: 1ms
memory: 3512kb
input:
252 -176 -239 512 49
output:
835642397
result:
ok 1 number(s): "835642397"
Test #20:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
-37 -124 151 867 76
output:
225290884
result:
ok 1 number(s): "225290884"
Test #21:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
-316 149 -149 1024 87
output:
374987754
result:
ok 1 number(s): "374987754"
Test #22:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
370 545 81 1073 69
output:
943329809
result:
ok 1 number(s): "943329809"
Test #23:
score: 0
Accepted
time: 3ms
memory: 3604kb
input:
-81 182 532 2048 87
output:
843173062
result:
ok 1 number(s): "843173062"
Test #24:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
-1229 -1607 319 199 24
output:
1926
result:
ok 1 number(s): "1926"
Test #25:
score: 0
Accepted
time: 5ms
memory: 3560kb
input:
43 -419 -613 4096 46
output:
418220629
result:
ok 1 number(s): "418220629"
Test #26:
score: 0
Accepted
time: 3ms
memory: 3540kb
input:
3434 -3146 -1774 2601 46
output:
705802517
result:
ok 1 number(s): "705802517"
Test #27:
score: 0
Accepted
time: 7ms
memory: 4060kb
input:
2193 -2331 2901 8192 75
output:
728593792
result:
ok 1 number(s): "728593792"
Test #28:
score: 0
Accepted
time: 2ms
memory: 3524kb
input:
233 -4307 -4363 1093 81
output:
303899847
result:
ok 1 number(s): "303899847"
Test #29:
score: 0
Accepted
time: 17ms
memory: 4952kb
input:
-4522 762 8059 16384 34
output:
190696426
result:
ok 1 number(s): "190696426"
Test #30:
score: 0
Accepted
time: 22ms
memory: 5080kb
input:
-5155 -3639 15798 24822 55
output:
808461103
result:
ok 1 number(s): "808461103"
Test #31:
score: 0
Accepted
time: 39ms
memory: 6860kb
input:
15234 4368 12248 32768 19
output:
115861480
result:
ok 1 number(s): "115861480"
Test #32:
score: 0
Accepted
time: 41ms
memory: 7092kb
input:
820 30492 3951 42789 76
output:
826647308
result:
ok 1 number(s): "826647308"
Test #33:
score: 0
Accepted
time: 83ms
memory: 10736kb
input:
1372 -24835 -24597 65536 65
output:
355997764
result:
ok 1 number(s): "355997764"
Test #34:
score: 0
Accepted
time: 88ms
memory: 11404kb
input:
-59726 17559 -45875 87143 58
output:
326130350
result:
ok 1 number(s): "326130350"
Test #35:
score: 0
Accepted
time: 171ms
memory: 18364kb
input:
-27584 51950 23030 131072 74
output:
325794325
result:
ok 1 number(s): "325794325"
Test #36:
score: 0
Accepted
time: 180ms
memory: 19296kb
input:
61155 52006 74974 164861 5
output:
160748350
result:
ok 1 number(s): "160748350"
Test #37:
score: 0
Accepted
time: 187ms
memory: 20240kb
input:
41344 -81596 -95774 200000 59
output:
965482998
result:
ok 1 number(s): "965482998"
Test #38:
score: 0
Accepted
time: 18ms
memory: 5108kb
input:
42056 -90767 -54649 24350 63
output:
132823
result:
ok 1 number(s): "132823"
Test #39:
score: 0
Accepted
time: 191ms
memory: 20168kb
input:
-74335 43393 57021 199994 67
output:
310210583
result:
ok 1 number(s): "310210583"
Test #40:
score: 0
Accepted
time: 166ms
memory: 18628kb
input:
-80838 73772 -18618 134415 57
output:
346157175
result:
ok 1 number(s): "346157175"
Test #41:
score: 0
Accepted
time: 188ms
memory: 20172kb
input:
37457 74497 -81166 199997 59
output:
26667908
result:
ok 1 number(s): "26667908"
Test #42:
score: 0
Accepted
time: 186ms
memory: 19300kb
input:
31109 -65140 -77085 162412 46
output:
12858959
result:
ok 1 number(s): "12858959"
Test #43:
score: 0
Accepted
time: 198ms
memory: 20020kb
input:
-58550 -97769 66373 199995 86
output:
789346262
result:
ok 1 number(s): "789346262"
Test #44:
score: 0
Accepted
time: 89ms
memory: 12192kb
input:
7739 58831 72332 124270 16
output:
167162440
result:
ok 1 number(s): "167162440"
Test #45:
score: 0
Accepted
time: 194ms
memory: 20248kb
input:
-97901 25173 -99145 199999 52
output:
797290311
result:
ok 1 number(s): "797290311"
Test #46:
score: 0
Accepted
time: 94ms
memory: 12196kb
input:
-87118 -60882 -86669 126103 23
output:
487838027
result:
ok 1 number(s): "487838027"
Test #47:
score: 0
Accepted
time: 190ms
memory: 20296kb
input:
-71646 69885 70206 200000 27
output:
285981891
result:
ok 1 number(s): "285981891"
Test #48:
score: 0
Accepted
time: 96ms
memory: 11800kb
input:
14475 -77173 -5177 117777 51
output:
251933976
result:
ok 1 number(s): "251933976"
Test #49:
score: 0
Accepted
time: 187ms
memory: 20240kb
input:
-35780 37165 54712 199996 14
output:
763964192
result:
ok 1 number(s): "763964192"
Test #50:
score: 0
Accepted
time: 97ms
memory: 11676kb
input:
15709 -72676 -22298 101968 17
output:
406652317
result:
ok 1 number(s): "406652317"
Test #51:
score: 0
Accepted
time: 179ms
memory: 20180kb
input:
74572 -98701 -56974 199991 62
output:
55467556
result:
ok 1 number(s): "55467556"
Test #52:
score: 0
Accepted
time: 181ms
memory: 19568kb
input:
-14644 -10031 -50353 168383 43
output:
376814948
result:
ok 1 number(s): "376814948"
Test #53:
score: 0
Accepted
time: 194ms
memory: 20172kb
input:
22388 51898 80903 199995 89
output:
832434478
result:
ok 1 number(s): "832434478"
Test #54:
score: 0
Accepted
time: 98ms
memory: 12308kb
input:
34062 -76211 -25545 127193 91
output:
234760702
result:
ok 1 number(s): "234760702"
Test #55:
score: 0
Accepted
time: 193ms
memory: 20292kb
input:
-19645 -45450 -16512 200000 77
output:
759439547
result:
ok 1 number(s): "759439547"
Test #56:
score: 0
Accepted
time: 21ms
memory: 5140kb
input:
98957 80512 -24606 20311 30
output:
985804570
result:
ok 1 number(s): "985804570"
Test #57:
score: 0
Accepted
time: 201ms
memory: 20228kb
input:
-87259 -11505 14596 199994 83
output:
160520754
result:
ok 1 number(s): "160520754"
Test #58:
score: 0
Accepted
time: 187ms
memory: 20168kb
input:
0 0 0 200000 0
output:
393458944
result:
ok 1 number(s): "393458944"
Test #59:
score: 0
Accepted
time: 184ms
memory: 20160kb
input:
0 0 0 200000 100
output:
393458944
result:
ok 1 number(s): "393458944"
Test #60:
score: 0
Accepted
time: 194ms
memory: 20216kb
input:
-100000 -100000 -100000 200000 75
output:
393458944
result:
ok 1 number(s): "393458944"
Test #61:
score: 0
Accepted
time: 190ms
memory: 20244kb
input:
100000 100000 100000 200000 63
output:
393458944
result:
ok 1 number(s): "393458944"
Test #62:
score: 0
Accepted
time: 193ms
memory: 20156kb
input:
100000 0 -100000 200000 56
output:
678255914
result:
ok 1 number(s): "678255914"
Test #63:
score: 0
Accepted
time: 190ms
memory: 20156kb
input:
0 1 2 200000 22
output:
630634769
result:
ok 1 number(s): "630634769"
Test #64:
score: 0
Accepted
time: 1ms
memory: 3432kb
input:
100000 0 -100000 1 32
output:
200000
result:
ok 1 number(s): "200000"
Test #65:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
100000 100000 100000 1 33
output:
1
result:
ok 1 number(s): "1"
Test #66:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
-100000 -100000 -100000 1 6
output:
1
result:
ok 1 number(s): "1"
Test #67:
score: 0
Accepted
time: 1ms
memory: 3400kb
input:
100000 100000 -100000 1 7
output:
332948118
result:
ok 1 number(s): "332948118"
Test #68:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
-100000 -100000 100000 1 40
output:
332948118
result:
ok 1 number(s): "332948118"
Test #69:
score: 0
Accepted
time: 1ms
memory: 3416kb
input:
100000 -100000 -100000 100 63
output:
764105630
result:
ok 1 number(s): "764105630"
Test #70:
score: 0
Accepted
time: 1ms
memory: 3412kb
input:
-100000 100000 100000 100 13
output:
764105630
result:
ok 1 number(s): "764105630"
Test #71:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
-100000 100000 0 100 10
output:
200000
result:
ok 1 number(s): "200000"
Test #72:
score: 0
Accepted
time: 91ms
memory: 11660kb
input:
-100000 100000 0 99999 77
output:
200000
result:
ok 1 number(s): "200000"
Test #73:
score: 0
Accepted
time: 83ms
memory: 11600kb
input:
-100000 100000 0 100000 80
output:
200000
result:
ok 1 number(s): "200000"
Test #74:
score: 0
Accepted
time: 87ms
memory: 11644kb
input:
-100000 100000 0 100001 5
output:
50125708
result:
ok 1 number(s): "50125708"