QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#669792#8147. Math Exambright_mlAC ✓237ms238076kbC++201.4kb2024-10-23 19:41:052024-10-23 19:41:06

Judging History

你现在查看的是最新测评结果

  • [2024-10-23 19:41:06]
  • 评测
  • 测评结果:AC
  • 用时:237ms
  • 内存:238076kb
  • [2024-10-23 19:41:05]
  • 提交

answer

//
// Created by 35395 on 2024/10/23.
//
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7 + 100, mod = 998244353;
int f[N],f_inv[N],inv[N];

void init(){
    inv[1] = f[0] = f_inv[0] = 1;
    for(int i=2;i<N;i++) inv[i] = 1ll*(mod - mod / i) * inv[mod % i] % mod;
    for(int i=1;i<N;i++) f[i] = 1ll*f[i-1] * i % mod;
    for(int i=1;i<N;i++) f_inv[i] = 1ll*f_inv[i-1] * inv[i] % mod;
}

int C(int a,int b){
    if(a < 0 || b < 0 || a < b) return 0;
    return 1ll*f[a] * f_inv[b] % mod * f_inv[a-b] % mod;
}

int n,m,c;

pair<int,int> get(int x,int y,int c){
    return {y-c,x+c};
}

void to(int &x,int &y,int c){
    auto [x_,y_] = get(x,y,c);
    x = x_, y = y_;
}

int get(int x,int y){
    int res = C(x+y,x);
    int nx = x, ny = y;
    while(nx >= 0 && ny >= 0){
        to(nx,ny,c); res = (res - C(nx+ny,nx) + mod) % mod;
        to(nx,ny,1); res = (res + C(nx+ny,nx)) % mod;
    }
    nx = x, ny = y;
    while(nx >= 0 && ny >= 0){
        to(nx,ny,1); res = (res - C(nx+ny,nx) + mod) % mod;
        to(nx,ny,c); res = (res + C(nx+ny,nx)) % mod;
    }
    return res;
}

signed main(){
    init();
    cin >> n >> m;
    int down = (n + 1) / 2;
    int ans = 0;
    c = -(m+1)/2 - 1;
    int cnt = 0;
    for(int i=down;i<=n && i <= n-i+(m+1)/2;i++){
        int j = n - i;
        ans = (ans + get(i,j)) % mod;
    }
    cout << ans << '\n';
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 178ms
memory: 237868kb

input:

9 13

output:

124

result:

ok answer is '124'

Test #2:

score: 0
Accepted
time: 158ms
memory: 238004kb

input:

500 999

output:

195157058

result:

ok answer is '195157058'

Test #3:

score: 0
Accepted
time: 237ms
memory: 237980kb

input:

10000000 19260817

output:

475124613

result:

ok answer is '475124613'

Test #4:

score: 0
Accepted
time: 174ms
memory: 237872kb

input:

1234567 654321

output:

986926700

result:

ok answer is '986926700'

Test #5:

score: 0
Accepted
time: 166ms
memory: 237988kb

input:

1145141 11451

output:

186897097

result:

ok answer is '186897097'

Test #6:

score: 0
Accepted
time: 169ms
memory: 238068kb

input:

114514 11451

output:

91839230

result:

ok answer is '91839230'

Test #7:

score: 0
Accepted
time: 153ms
memory: 238064kb

input:

1145143 114555

output:

641840034

result:

ok answer is '641840034'

Test #8:

score: 0
Accepted
time: 182ms
memory: 238076kb

input:

2123181 1980523

output:

784155222

result:

ok answer is '784155222'

Test #9:

score: 0
Accepted
time: 180ms
memory: 238064kb

input:

4238693 1876847

output:

169222558

result:

ok answer is '169222558'

Test #10:

score: 0
Accepted
time: 211ms
memory: 237872kb

input:

7804655 10519823

output:

935955279

result:

ok answer is '935955279'

Test #11:

score: 0
Accepted
time: 215ms
memory: 238064kb

input:

9189568 17055313

output:

811181659

result:

ok answer is '811181659'

Test #12:

score: 0
Accepted
time: 182ms
memory: 238068kb

input:

683534 1001003

output:

569208897

result:

ok answer is '569208897'

Test #13:

score: 0
Accepted
time: 170ms
memory: 238004kb

input:

1850342 3700683

output:

852266054

result:

ok answer is '852266054'

Test #14:

score: 0
Accepted
time: 206ms
memory: 237916kb

input:

10000000 1234567

output:

387622638

result:

ok answer is '387622638'

Test #15:

score: 0
Accepted
time: 169ms
memory: 237908kb

input:

1 1

output:

1

result:

ok answer is '1'

Test #16:

score: 0
Accepted
time: 159ms
memory: 237976kb

input:

3 1

output:

1

result:

ok answer is '1'

Test #17:

score: 0
Accepted
time: 171ms
memory: 237984kb

input:

10000000 1

output:

1

result:

ok answer is '1'

Extra Test:

score: 0
Extra Test Passed