QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#32711#2618. Casual DancersSortingAC ✓720ms66384kbC++202.7kb2022-05-23 00:56:452022-05-23 00:56:45

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.
  • [2022-05-23 00:56:45]
  • Judged
  • Verdict: AC
  • Time: 720ms
  • Memory: 66384kb
  • [2022-05-23 00:56:45]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll MOD = 998244353;
const ll N = 8e5 + 10;
const ll root = 62;


ll fast_pow(ll base, ll exp){
    if(!exp) return 1ll;
    if(exp & 1ll) return base * fast_pow(base, exp - 1) % MOD;
    ll t = fast_pow(base, exp >> 1);
    return t * t % MOD;
}

typedef vector<ll> vl;
void ntt(vl &a){
    int n = a.size(), L = 31 - __builtin_clz(n);
    static vl rt(2, 1);
    for(static int k = 2, s = 2; k < n; k *= 2, ++s){
        rt.resize(n);
        ll z[] = {1, fast_pow(root, MOD >> s)};
        for(int i = k; i < 2 * k; ++i)
            rt[i] = rt[i / 2] * z[i & 1] % MOD;
    }

    vector<int> rev(n);
    for(int i = 0; i < n; ++i)
        rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
    for(int i = 0; i < n; ++i)
        if(i < rev[i])
            swap(a[i],  a[rev[i]]);

    for(int k = 1; k < n; k *= 2){
        for(int i = 0; i < n; i += 2 * k){
            for(int j = 0; j < k; ++j){
                ll z = rt[j + k] * a[i + j + k] % MOD, &ai = a[i + j];
                a[i + j + k] = ai - z + (z > ai ? MOD : 0);
                ai += (ai + z >= MOD ? z - MOD : z);
            }
        }
    }
}

vl conv(const vl &a, const vl &b){
    if(a.empty() || b.empty()) return {};
    int s = a.size() + b.size() - 1, B = 32 - __builtin_clz(s), n = 1 << B;
    int inv = fast_pow(n, MOD - 2);
    vl L(a), R(b), out(n);
    L.resize(n), R.resize(n);
    ntt(L), ntt(R);
    for(int i = 0; i < n; ++i)
        out[-i & (n - 1)] = (ll)L[i] * R[i] % MOD * inv % MOD;
    ntt(out);
    return {out.begin(), out.begin() + s};
}

ll f[N], inv_f[N];
ll x1, x2, x3;
ll k, p;

vector<ll> v;

vl pol_pow(vl base, ll exp){
    vl ans{1};
    while(exp){
        if(exp & 1) ans = conv(ans, base);
        exp >>= 1;
        base = conv(base, base);
    }
    return ans;
}

ll comb(ll n, ll k){
    return f[n] * inv_f[k] % MOD * inv_f[n - k] % MOD;
}

ll expected(ll diff){
    ll res = 0;
    for(ll i = diff - k; i <= diff + k; ++i){
        res += abs(i) * v[i - (diff - k)] % MOD;
    }
    res %= MOD;

    res = (res * (fast_pow(fast_pow(3, k), MOD - 2)) % MOD);
    return res;
} 

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> x1 >> x2 >> x3 >> k >> p;

    f[0] = 1;
    for(int i = 1; i < N; ++i)
        f[i] = f[i - 1] * i % MOD;
    inv_f[N - 1] = fast_pow(f[N - 1], MOD - 2);
    for(int i = N - 2; i >= 0; --i)
        inv_f[i] = inv_f[i + 1] * (i + 1) % MOD;

    v = pol_pow({1, 1, 1}, k);

    ll res = expected(abs(x1 - x2)) + expected(abs(x1 - x3)) + expected(abs(x2 - x3));
    res %= MOD;
    res *= inv_f[2];
    res %= MOD;

    cout << res << "\n";
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 16160kb

input:

0 0 0
1
58

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 9ms
memory: 16012kb

input:

1 2 2
1
100

output:

332748119

result:

ok 1 number(s): "332748119"

Test #3:

score: 0
Accepted
time: 8ms
memory: 16052kb

input:

5 2 3
4
50

output:

160212060

result:

ok 1 number(s): "160212060"

Test #4:

score: 0
Accepted
time: 6ms
memory: 16100kb

input:

-2 -1 1
2
71

output:

443664160

result:

ok 1 number(s): "443664160"

Test #5:

score: 0
Accepted
time: 8ms
memory: 16200kb

input:

-1 0 -1
4
8

output:

751764268

result:

ok 1 number(s): "751764268"

Test #6:

score: 0
Accepted
time: 6ms
memory: 16052kb

input:

-2 -2 2
5
54

output:

801060288

result:

ok 1 number(s): "801060288"

Test #7:

score: 0
Accepted
time: 6ms
memory: 16100kb

input:

-2 2 4
8
36

output:

353135983

result:

ok 1 number(s): "353135983"

Test #8:

score: 0
Accepted
time: 12ms
memory: 16116kb

input:

8 -7 1
7
28

output:

15

result:

ok 1 number(s): "15"

Test #9:

score: 0
Accepted
time: 4ms
memory: 16068kb

input:

-7 -8 0
16
54

output:

159363041

result:

ok 1 number(s): "159363041"

Test #10:

score: 0
Accepted
time: 8ms
memory: 16120kb

input:

5 11 -11
9
32

output:

717226646

result:

ok 1 number(s): "717226646"

Test #11:

score: 0
Accepted
time: 8ms
memory: 16124kb

input:

-16 1 -9
32
8

output:

855967855

result:

ok 1 number(s): "855967855"

Test #12:

score: 0
Accepted
time: 6ms
memory: 16012kb

input:

-13 28 28
37
80

output:

116405794

result:

ok 1 number(s): "116405794"

Test #13:

score: 0
Accepted
time: 13ms
memory: 16036kb

input:

6 26 -25
64
21

output:

91053409

result:

ok 1 number(s): "91053409"

Test #14:

score: 0
Accepted
time: 12ms
memory: 16044kb

input:

-39 23 1
31
64

output:

742331784

result:

ok 1 number(s): "742331784"

Test #15:

score: 0
Accepted
time: 12ms
memory: 16172kb

input:

-32 42 43
128
87

output:

57822539

result:

ok 1 number(s): "57822539"

Test #16:

score: 0
Accepted
time: 6ms
memory: 16164kb

input:

-80 55 -106
142
29

output:

435655440

result:

ok 1 number(s): "435655440"

Test #17:

score: 0
Accepted
time: 8ms
memory: 16256kb

input:

0 -83 -106
256
55

output:

120508896

result:

ok 1 number(s): "120508896"

Test #18:

score: 0
Accepted
time: 12ms
memory: 16180kb

input:

-100 -123 -167
91
74

output:

285780715

result:

ok 1 number(s): "285780715"

Test #19:

score: 0
Accepted
time: 9ms
memory: 16248kb

input:

252 -176 -239
512
49

output:

835642397

result:

ok 1 number(s): "835642397"

Test #20:

score: 0
Accepted
time: 15ms
memory: 16192kb

input:

-37 -124 151
867
76

output:

225290884

result:

ok 1 number(s): "225290884"

Test #21:

score: 0
Accepted
time: 12ms
memory: 16340kb

input:

-316 149 -149
1024
87

output:

374987754

result:

ok 1 number(s): "374987754"

Test #22:

score: 0
Accepted
time: 20ms
memory: 16248kb

input:

370 545 81
1073
69

output:

943329809

result:

ok 1 number(s): "943329809"

Test #23:

score: 0
Accepted
time: 13ms
memory: 16572kb

input:

-81 182 532
2048
87

output:

843173062

result:

ok 1 number(s): "843173062"

Test #24:

score: 0
Accepted
time: 8ms
memory: 16108kb

input:

-1229 -1607 319
199
24

output:

1926

result:

ok 1 number(s): "1926"

Test #25:

score: 0
Accepted
time: 29ms
memory: 17168kb

input:

43 -419 -613
4096
46

output:

418220629

result:

ok 1 number(s): "418220629"

Test #26:

score: 0
Accepted
time: 15ms
memory: 16344kb

input:

3434 -3146 -1774
2601
46

output:

705802517

result:

ok 1 number(s): "705802517"

Test #27:

score: 0
Accepted
time: 37ms
memory: 18692kb

input:

2193 -2331 2901
8192
75

output:

728593792

result:

ok 1 number(s): "728593792"

Test #28:

score: 0
Accepted
time: 16ms
memory: 16140kb

input:

233 -4307 -4363
1093
81

output:

303899847

result:

ok 1 number(s): "303899847"

Test #29:

score: 0
Accepted
time: 78ms
memory: 21708kb

input:

-4522 762 8059
16384
34

output:

190696426

result:

ok 1 number(s): "190696426"

Test #30:

score: 0
Accepted
time: 88ms
memory: 21692kb

input:

-5155 -3639 15798
24822
55

output:

808461103

result:

ok 1 number(s): "808461103"

Test #31:

score: 0
Accepted
time: 146ms
memory: 27584kb

input:

15234 4368 12248
32768
19

output:

115861480

result:

ok 1 number(s): "115861480"

Test #32:

score: 0
Accepted
time: 160ms
memory: 28496kb

input:

820 30492 3951
42789
76

output:

826647308

result:

ok 1 number(s): "826647308"

Test #33:

score: 0
Accepted
time: 317ms
memory: 39156kb

input:

1372 -24835 -24597
65536
65

output:

355997764

result:

ok 1 number(s): "355997764"

Test #34:

score: 0
Accepted
time: 323ms
memory: 41452kb

input:

-59726 17559 -45875
87143
58

output:

326130350

result:

ok 1 number(s): "326130350"

Test #35:

score: 0
Accepted
time: 631ms
memory: 62788kb

input:

-27584 51950 23030
131072
74

output:

325794325

result:

ok 1 number(s): "325794325"

Test #36:

score: 0
Accepted
time: 666ms
memory: 66384kb

input:

61155 52006 74974
164861
5

output:

160748350

result:

ok 1 number(s): "160748350"

Test #37:

score: 0
Accepted
time: 716ms
memory: 63872kb

input:

41344 -81596 -95774
200000
59

output:

965482998

result:

ok 1 number(s): "965482998"

Test #38:

score: 0
Accepted
time: 81ms
memory: 22036kb

input:

42056 -90767 -54649
24350
63

output:

132823

result:

ok 1 number(s): "132823"

Test #39:

score: 0
Accepted
time: 715ms
memory: 63992kb

input:

-74335 43393 57021
199994
67

output:

310210583

result:

ok 1 number(s): "310210583"

Test #40:

score: 0
Accepted
time: 650ms
memory: 64964kb

input:

-80838 73772 -18618
134415
57

output:

346157175

result:

ok 1 number(s): "346157175"

Test #41:

score: 0
Accepted
time: 713ms
memory: 63976kb

input:

37457 74497 -81166
199997
59

output:

26667908

result:

ok 1 number(s): "26667908"

Test #42:

score: 0
Accepted
time: 670ms
memory: 65728kb

input:

31109 -65140 -77085
162412
46

output:

12858959

result:

ok 1 number(s): "12858959"

Test #43:

score: 0
Accepted
time: 719ms
memory: 63816kb

input:

-58550 -97769 66373
199995
86

output:

789346262

result:

ok 1 number(s): "789346262"

Test #44:

score: 0
Accepted
time: 352ms
memory: 42688kb

input:

7739 58831 72332
124270
16

output:

167162440

result:

ok 1 number(s): "167162440"

Test #45:

score: 0
Accepted
time: 700ms
memory: 63944kb

input:

-97901 25173 -99145
199999
52

output:

797290311

result:

ok 1 number(s): "797290311"

Test #46:

score: 0
Accepted
time: 369ms
memory: 40460kb

input:

-87118 -60882 -86669
126103
23

output:

487838027

result:

ok 1 number(s): "487838027"

Test #47:

score: 0
Accepted
time: 711ms
memory: 63884kb

input:

-71646 69885 70206
200000
27

output:

285981891

result:

ok 1 number(s): "285981891"

Test #48:

score: 0
Accepted
time: 356ms
memory: 39584kb

input:

14475 -77173 -5177
117777
51

output:

251933976

result:

ok 1 number(s): "251933976"

Test #49:

score: 0
Accepted
time: 711ms
memory: 63812kb

input:

-35780 37165 54712
199996
14

output:

763964192

result:

ok 1 number(s): "763964192"

Test #50:

score: 0
Accepted
time: 350ms
memory: 39840kb

input:

15709 -72676 -22298
101968
17

output:

406652317

result:

ok 1 number(s): "406652317"

Test #51:

score: 0
Accepted
time: 704ms
memory: 63780kb

input:

74572 -98701 -56974
199991
62

output:

55467556

result:

ok 1 number(s): "55467556"

Test #52:

score: 0
Accepted
time: 663ms
memory: 61516kb

input:

-14644 -10031 -50353
168383
43

output:

376814948

result:

ok 1 number(s): "376814948"

Test #53:

score: 0
Accepted
time: 708ms
memory: 63900kb

input:

22388 51898 80903
199995
89

output:

832434478

result:

ok 1 number(s): "832434478"

Test #54:

score: 0
Accepted
time: 362ms
memory: 42656kb

input:

34062 -76211 -25545
127193
91

output:

234760702

result:

ok 1 number(s): "234760702"

Test #55:

score: 0
Accepted
time: 718ms
memory: 63780kb

input:

-19645 -45450 -16512
200000
77

output:

759439547

result:

ok 1 number(s): "759439547"

Test #56:

score: 0
Accepted
time: 72ms
memory: 21952kb

input:

98957 80512 -24606
20311
30

output:

985804570

result:

ok 1 number(s): "985804570"

Test #57:

score: 0
Accepted
time: 701ms
memory: 63780kb

input:

-87259 -11505 14596
199994
83

output:

160520754

result:

ok 1 number(s): "160520754"

Test #58:

score: 0
Accepted
time: 705ms
memory: 63812kb

input:

0 0 0
200000
0

output:

393458944

result:

ok 1 number(s): "393458944"

Test #59:

score: 0
Accepted
time: 706ms
memory: 63804kb

input:

0 0 0
200000
100

output:

393458944

result:

ok 1 number(s): "393458944"

Test #60:

score: 0
Accepted
time: 696ms
memory: 63828kb

input:

-100000 -100000 -100000
200000
75

output:

393458944

result:

ok 1 number(s): "393458944"

Test #61:

score: 0
Accepted
time: 704ms
memory: 63692kb

input:

100000 100000 100000
200000
63

output:

393458944

result:

ok 1 number(s): "393458944"

Test #62:

score: 0
Accepted
time: 720ms
memory: 63972kb

input:

100000 0 -100000
200000
56

output:

678255914

result:

ok 1 number(s): "678255914"

Test #63:

score: 0
Accepted
time: 707ms
memory: 63884kb

input:

0 1 2
200000
22

output:

630634769

result:

ok 1 number(s): "630634769"

Test #64:

score: 0
Accepted
time: 6ms
memory: 16100kb

input:

100000 0 -100000
1
32

output:

200000

result:

ok 1 number(s): "200000"

Test #65:

score: 0
Accepted
time: 2ms
memory: 16088kb

input:

100000 100000 100000
1
33

output:

1

result:

ok 1 number(s): "1"

Test #66:

score: 0
Accepted
time: 4ms
memory: 16044kb

input:

-100000 -100000 -100000
1
6

output:

1

result:

ok 1 number(s): "1"

Test #67:

score: 0
Accepted
time: 4ms
memory: 16084kb

input:

100000 100000 -100000
1
7

output:

332948118

result:

ok 1 number(s): "332948118"

Test #68:

score: 0
Accepted
time: 4ms
memory: 16200kb

input:

-100000 -100000 100000
1
40

output:

332948118

result:

ok 1 number(s): "332948118"

Test #69:

score: 0
Accepted
time: 3ms
memory: 16180kb

input:

100000 -100000 -100000
100
63

output:

764105630

result:

ok 1 number(s): "764105630"

Test #70:

score: 0
Accepted
time: 9ms
memory: 16232kb

input:

-100000 100000 100000
100
13

output:

764105630

result:

ok 1 number(s): "764105630"

Test #71:

score: 0
Accepted
time: 9ms
memory: 16232kb

input:

-100000 100000 0
100
10

output:

200000

result:

ok 1 number(s): "200000"

Test #72:

score: 0
Accepted
time: 325ms
memory: 39748kb

input:

-100000 100000 0
99999
77

output:

200000

result:

ok 1 number(s): "200000"

Test #73:

score: 0
Accepted
time: 338ms
memory: 39892kb

input:

-100000 100000 0
100000
80

output:

200000

result:

ok 1 number(s): "200000"

Test #74:

score: 0
Accepted
time: 328ms
memory: 39824kb

input:

-100000 100000 0
100001
5

output:

50125708

result:

ok 1 number(s): "50125708"