QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#411562 | #8147. Math Exam | Graphcity | AC ✓ | 229ms | 159984kb | C++14 | 1.4kb | 2024-05-15 16:00:15 | 2024-05-15 16:00:15 |
Judging History
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