UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214446#2718. 8.2t3erican2065ms43364kbC++111.8kb2024-11-18 22:01:352024-11-19 08:36:29

answer

/*  Erica N  */
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn int
#define rd read()
int read(){
    int xx = 0, ff = 1;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')ff = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
// void write(int out) {
// 	if (out < 0)
// 		putchar('-'), out = -out;
// 	if (out > 9)
// 		write(out / 10);
// 	putchar(out % 10 + '0');
// }
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }


const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 998244353;

int f[6][N][3];//向下/上
int n,m,q;
int ban[6][N];

void solve(){

    memset(f,0,sizeof f);
    f[1][0][2]=1;
    for(int j=1;j<=m;j++){

        for(int i=1;i<=n;i++){
            if(ban[i][j])continue;
            f[i][j][0]=(f[i][j-1][2])%MOD;
        }


        for(int i=1;i<=n;i++){
            if(ban[i][j])continue;
            f[i][j][1]=(f[i][j-1][2])%MOD;
        }

        for(int i=1;i<=n;i++){
            if(ban[i][j])continue;
            f[i][j][2]=(f[i-1][j][0]+f[i+1][j][1])%MOD;
        }

    }

    cout<<f[n][m][2]<<endl;
    
}

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
     n=rd,m=rd,q=rd;
    while(q--){
        int x=rd,y=rd;
        ban[x][y]=1;
        solve();
    }

}

详细

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

Test #1:

score: 10
Accepted
time: 34ms
memory: 43364kb

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

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:


Test #3:

score: 10
Accepted
time: 31ms
memory: 43356kb

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

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:


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:

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

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:

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

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:

636299371
215744819
252527760
691521797
334927651
491663361
2328689
543779237
706792728
577050832
33...

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: