UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214400#2718. 8.2t3yiwei80922ms21676kbC++111.6kb2024-11-18 19:59:402024-11-19 08:31:03

answer

#include <bits/stdc++.h>
using namespace std;

const int P = 998244353;

int qpow(int a,int b){
    int c = 1;
    for (;b;b >>= 1, a = 1ll * a * a % P)
        if (b & 1)
            c = 1ll * c * a % P;
    return c;
}

int n,m,q;

map<pair<int,int>,bool> op;

int main(){
    cin >> n >> m >> q;
    if (n == 2){
        while (q--) puts("0");
    }
    else if (n == 3){
        int ans = qpow(2,m / 2 - 1), inv2 = qpow(2,P - 2);
        while (q--){
            int x,y; cin >> x >> y;
            if (op[{x,y}]){
                cout << ans << '\n';
                continue;
            }
            op[{x,y}] = 1;
            
            if (m & 1){
                if ((x == 1 && y == m - 1) || (x == 1 && y == m) || (x == 2 && y == m) || (x == 3 && y == 1)){
                    cout << ans << '\n';
                    continue;
                }
            }
            else{
                if ((x == 3 && y == 1) || (x == 1 && y == m)){
                    cout << ans << '\n';
                    continue;
                }
            }

            if (x == 2 || (x == 1 && y == 1) || (x == n && y == m)){
                ans = 0;
            }

            if ((m & 1) && (x == 3 && y == m - 1)){
                ans = 0;
            }

            if (op[{4 - x,y}] || op[{4 - x,y ^ 1}]){
                ans = 0;
            }

            if (op[{x,y ^ 1}]){
                cout << ans << '\n';
                continue;
            }

            ans = 1ll * ans * inv2 % P;

            cout << ans << '\n';
        }
    }
    else{
        while (q--) puts("0");
    }
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1240kb

input:

3 4 5
3 1
1 4
1 2
1 3
2 2

output:

2
2
1
1
0

result:

ok 5 number(s): "2 2 1 1 0"

Test #2:

score: 10
Accepted
time: 0ms
memory: 1168kb

input:

2 99999 100000
2 70567
1 17791
2 77890
2 12623
2 13544
1 18390
2 8888
1 74050
2 67101
1 56764
2 3761...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 numbers

Test #3:

score: 10
Accepted
time: 0ms
memory: 1244kb

input:

3 1000 5
3 805
3 596
3 575
3 58
3 577

output:

154029661
576137007
787190680
393595340
196797670

result:

ok 5 number(s): "154029661 576137007 787190680 393595340 196797670"

Test #4:

score: 10
Accepted
time: 0ms
memory: 1348kb

input:

3 1000 1000
1 45
3 898
1 799
1 48
1 847
3 607
1 760
1 802
3 903
3 836
1 526
3 264
1 96
3 244
3 242
3...

output:

154029661
576137007
787190680
393595340
196797670
98398835
548321594
274160797
636202575
817223464
4...

result:

ok 1000 numbers

Test #5:

score: 10
Accepted
time: 313ms
memory: 12056kb

input:

3 100000 100000
1 74197
3 11259
3 65940
3 1906
3 40328
1 71201
1 50943
1 98978
1 70015
3 43996
1 114...

output:

159434530
79717265
538980809
768612581
883428467
940836410
470418205
734331279
866287816
433143908
2...

result:

ok 100000 numbers

Test #6:

score: 10
Accepted
time: 282ms
memory: 12084kb

input:

3 100000 100000
1 16644
3 29648
3 77047
1 94435
1 43985
1 89629
1 78236
1 93267
3 25517
1 52560
1 89...

output:

159434530
79717265
538980809
768612581
883428467
940836410
470418205
734331279
866287816
433143908
2...

result:

ok 100000 numbers

Test #7:

score: 10
Accepted
time: 0ms
memory: 1260kb

input:

3 1000000000 100
1 574043575
1 413916829
3 96
1 394696238
1 40
3 38
1 69
1 968879034
1 52
1 62558778...

output:

745547840
372773920
186386960
93193480
46596740
23298370
11649185
504946769
751595561
874919957
9365...

result:

ok 100 numbers

Test #8:

score: 10
Accepted
time: 326ms
memory: 21676kb

input:

3 1000000000 100000
3 15019
1 79221
3 22394
1 89278
3 875067515
1 15404
1 615238057
3 89925
3 271777...

output:

745547840
372773920
186386960
93193480
46596740
23298370
11649185
504946769
751595561
874919957
9365...

result:

ok 100000 numbers

Test #9:

score: 0
Wrong Answer
time: 0ms
memory: 1168kb

input:

4 99999 50000
4 66854
4 48295
4 95292
4 86389
4 9961
4 33406
4 96945
4 64418
4 19331
4 71257
4 36656...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 1st numbers differ - expected: '636299371', found: '0'

Test #10:

score: 0
Wrong Answer
time: 1ms
memory: 1164kb

input:

4 999999999 100000
4 908546081
4 885383980
4 37966517
4 191661556
4 107475378
4 699076844
4 58764448...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 1st numbers differ - expected: '991199402', found: '0'