QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#119782#2618. Casual DancersScarlett_boyAC ✓201ms20296kbC++174.9kb2023-07-05 19:03:462023-07-05 19:03:49

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-05 19:03:49]
  • Judged
  • Verdict: AC
  • Time: 201ms
  • Memory: 20296kb
  • [2023-07-05 19:03:46]
  • Submitted

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"