QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#411562#8147. Math ExamGraphcityAC ✓229ms159984kbC++141.4kb2024-05-15 16:00:152024-05-15 16:00:15

Judging History

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

  • [2024-05-15 16:00:15]
  • 评测
  • 测评结果:AC
  • 用时:229ms
  • 内存:159984kb
  • [2024-05-15 16:00:15]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e7+5,Mod=998244353;

inline int Pow(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=1ll*res*x%Mod;
        x=1ll*x*x%Mod,y>>=1;
    }
    return res;
}

int n,m,fac[Maxn+5],inv[Maxn+5];
inline int C(int x,int y) {return (x<y || y<0)?0:1ll*fac[x]*inv[x-y]%Mod*inv[y]%Mod;}
inline int F1(int x) {return -2-x;}
inline int F2(int x) {return m*2-x;}
inline int Work(int p)
{
    if((n+p&1) || n+p<0 || n+p>n*2) return 0;
    int res=C(n,(n+p)/2);
    for(int k=F1(p),op=-1;;op=-op,k=(op<0?F1(k):F2(k)))
    {
        if(n+k<0 || n+k>n*2) break;
        res=(res+1ll*(op+Mod)*C(n,(n+k)/2))%Mod;
    }
    for(int k=F2(p),op=-1;;op=-op,k=(op>0?F1(k):F2(k)))
    {
        if(n+k<0 || n+k>n*2) break;
        res=(res+1ll*(op+Mod)*C(n,(n+k)/2))%Mod;
    } return res;
}
// (0,0)->(n,k)
// x+y=n x-y=k
// x=(n+k)/2

int main()
{
    // freopen("1.in","r",stdin);

    cin>>n>>m; m=(m+1)/2+1; fac[0]=inv[0]=1;
    For(i,1,Maxn) fac[i]=1ll*fac[i-1]*i%Mod;
    inv[Maxn]=Pow(fac[Maxn],Mod-2);
    Rof(i,Maxn-1,1) inv[i]=1ll*inv[i+1]*(i+1)%Mod;
    int ans=0; For(i,0,m-1) ans=(ans+Work(i))%Mod;
    cout<<ans<<endl;
    return 0;
}

// (0,1) 出发
// 不能碰到 y=-1 和 y=m

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

详细

Test #1:

score: 100
Accepted
time: 160ms
memory: 159812kb

input:

9 13

output:

124

result:

ok answer is '124'

Test #2:

score: 0
Accepted
time: 162ms
memory: 159872kb

input:

500 999

output:

195157058

result:

ok answer is '195157058'

Test #3:

score: 0
Accepted
time: 222ms
memory: 159956kb

input:

10000000 19260817

output:

475124613

result:

ok answer is '475124613'

Test #4:

score: 0
Accepted
time: 173ms
memory: 159824kb

input:

1234567 654321

output:

986926700

result:

ok answer is '986926700'

Test #5:

score: 0
Accepted
time: 185ms
memory: 159828kb

input:

1145141 11451

output:

186897097

result:

ok answer is '186897097'

Test #6:

score: 0
Accepted
time: 173ms
memory: 159916kb

input:

114514 11451

output:

91839230

result:

ok answer is '91839230'

Test #7:

score: 0
Accepted
time: 176ms
memory: 159896kb

input:

1145143 114555

output:

641840034

result:

ok answer is '641840034'

Test #8:

score: 0
Accepted
time: 184ms
memory: 159896kb

input:

2123181 1980523

output:

784155222

result:

ok answer is '784155222'

Test #9:

score: 0
Accepted
time: 197ms
memory: 159980kb

input:

4238693 1876847

output:

169222558

result:

ok answer is '169222558'

Test #10:

score: 0
Accepted
time: 218ms
memory: 159984kb

input:

7804655 10519823

output:

935955279

result:

ok answer is '935955279'

Test #11:

score: 0
Accepted
time: 229ms
memory: 159776kb

input:

9189568 17055313

output:

811181659

result:

ok answer is '811181659'

Test #12:

score: 0
Accepted
time: 163ms
memory: 159952kb

input:

683534 1001003

output:

569208897

result:

ok answer is '569208897'

Test #13:

score: 0
Accepted
time: 179ms
memory: 159944kb

input:

1850342 3700683

output:

852266054

result:

ok answer is '852266054'

Test #14:

score: 0
Accepted
time: 218ms
memory: 159896kb

input:

10000000 1234567

output:

387622638

result:

ok answer is '387622638'

Test #15:

score: 0
Accepted
time: 163ms
memory: 159916kb

input:

1 1

output:

1

result:

ok answer is '1'

Test #16:

score: 0
Accepted
time: 163ms
memory: 159832kb

input:

3 1

output:

1

result:

ok answer is '1'

Test #17:

score: 0
Accepted
time: 201ms
memory: 159780kb

input:

10000000 1

output:

1

result:

ok answer is '1'

Extra Test:

score: 0
Extra Test Passed