UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#214420#2718. 8.2t3a_sad_soul40641ms13112kbC++11950b2024-11-18 20:53:372024-11-19 08:33:33

answer

#include<bits/stdc++.h>
using namespace std;
//typedef long long ll;
const int mod = 998244353;
const int MAXN =5e5+10;
int f[6][MAXN];
bool is[6][MAXN];
int n,m;
int calc(){
    memset(f,0,sizeof(f));
    if(is[1][1])return 0;
    if(is[2][1])return 0;
    f[2][1]=1;
    for(int j=2;j<=m;++j){
        for(int i=1;i<=n;++i){
            if(is[i][j])continue;
            if(!is[i-1][j])f[i][j]=(f[i][j]+f[i-1][j-1])%mod;
            if(!is[i+1][j])f[i][j]=(f[i][j]+f[i+1][j-1])%mod;
        }
        bool sus=0;
        for(int i=1;i<=n;++i)if(f[i][j])sus=1;
        if(sus==0)return 0;
    }
    return f[n][m];
}
bool fail;
int q;
int main(){
    scanf("%d%d%d",&n,&m,&q);
    while(q--){
        int x,y;scanf("%d%d",&x,&y);
        is[x][y]=1;
        if(fail){
            puts("0");continue;
        }
        int ans=calc();
        if(ans==0)fail=1;
        printf("%d\n",ans);
    }
    return 0;
}

Details

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

Test #1:

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

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: 8ms
memory: 13112kb

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: 3ms
memory: 12916kb

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: 630ms
memory: 12924kb

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: 0
Time Limit Exceeded

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:


result:


Test #6:

score: 0
Time Limit Exceeded

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:


result:


Test #7:

score: 0
Runtime Error

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:


result:


Test #8:

score: 0
Runtime Error

input:

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

output:


result:


Test #9:

score: 0
Time Limit Exceeded

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:


result:


Test #10:

score: 0
Runtime Error

input:

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

output:


result: