QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#875531 | #10020. Heroes and Illusions | rotcar07 | AC ✓ | 24ms | 4480kb | C++23 | 867b | 2025-01-29 22:32:31 | 2025-01-29 22:32:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998244353,N=1e5+5;
inline int qpow(int a,int b){
int ans=1;
while(b){
if(b&1) ans=ans*1ll*a%mod;
a=a*1ll*a%mod,b>>=1;
}
return ans;
}
int fac[N],inv[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;cin>>T;
for(int i=fac[0]=1;i<=N-4;i++)fac[i]=fac[i-1]*1ll*i%mod;
inv[N-4]=qpow(fac[N-4],mod-2);
for(int i=N-4;i>=1;i--) inv[i-1]=inv[i]*1ll*i%mod;
while(T--){
int n;long long k;
cin>>n>>k;
int l=0,r=(n+1)/2;
while(l<r){
int mid=l+r+1>>1;
if(mid*1ll*(n+1-mid)<=k)l=mid;
else r=mid-1;
}
if(l*1ll*(n+1-l)==k) cout<<fac[n+1]*1ll*inv[l]%mod*inv[n+1-l]%mod*(l==n+1-l?inv[2]:1)%mod<<'\n';
else cout<<"0\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4480kb
input:
1 5 9
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: 0
Accepted
time: 0ms
memory: 4480kb
input:
4 3 4 6 12 6 11 12 30
output:
3 35 0 286
result:
ok 4 number(s): "3 35 0 286"
Test #3:
score: 0
Accepted
time: 10ms
memory: 4480kb
input:
100000 1 0 1 1 2 0 2 1 2 2 2 3 3 0 3 1 3 2 3 3 3 4 3 5 3 6 4 0 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 5 0 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 5 10 5 11 5 12 5 13 5 14 5 15 6 0 6 1 6 2 6 3 6 4 6 5 6 6 6 7 6 8 6 9 6 10 6 11 6 12 6 13 6 14 6 15 6 16 6 17 6 18 6 19 6 20 6 21 7 0 7 1 7 2 7 3 7 4 7 5 7 ...
output:
1 1 1 0 3 0 1 0 0 4 3 0 0 1 0 0 0 5 0 10 0 0 0 0 1 0 0 0 0 6 0 0 15 10 0 0 0 0 0 0 1 0 0 0 0 0 7 0 0 0 21 0 35 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 8 0 0 0 0 28 0 0 56 35 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 9 0 0 0 0 0 36 0 0 0 84 0 126 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 11ms
memory: 4352kb
input:
100000 100000 5000050000 100000 5000049999 100000 5000049998 100000 5000049997 100000 5000049996 100000 5000049995 100000 5000049994 100000 5000049993 100000 5000049992 100000 5000049991 100000 5000049990 100000 5000049989 100000 5000049988 100000 5000049987 100000 5000049986 100000 5000049985 10000...
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 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 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 #5:
score: 0
Accepted
time: 15ms
memory: 4480kb
input:
100000 46912 365706917 49182 636258965 77290 2556664705 27786 73422397 93508 1694402104 59871 579442880 42716 228729495 42155 305721575 67614 1758952011 35681 602674542 28171 4246849 21467 227279631 28617 179294021 56165 1202621853 40544 492812833 81297 928180007 26222 30010919 67438 2160182443 4454...
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 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 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 #6:
score: 0
Accepted
time: 24ms
memory: 4352kb
input:
100000 15262 57528300 62491 976131040 54198 721202370 14947 13285051 35979 129539476 33157 6591600 97608 2279535648 63771 1013167540 80286 613035390 40491 257328612 96616 971104690 59030 423144018 14957 51278477 9889 23074749 85771 1277471595 96655 1082364783 25549 163184241 33545 233239304 35991 31...
output:
742932853 190167927 260561626 390862864 464981422 402844072 772271022 365685850 165699148 397484575 482364024 189862811 933305973 425340046 356443337 917745820 638656736 507033863 175102571 436677557 207650366 696036563 940831612 929085839 847065587 144267450 727449080 119955447 606112759 735025207 ...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 19ms
memory: 4480kb
input:
100000 46189 90697425 6981 9167376 34637 148165361 93503 974526522 50327 977792484 74483 706465827 33750 105209100 35893 574360354 20854 189160499 52296 717109399 11543 18119034 10279 23929516 33431 183463040 67353 1992958750 10691 24831620 19922 85729532 15526 75643457 60067 1762302707 41402 365928...
output:
518483518 0 864441320 0 0 0 814050510 0 0 0 0 874605187 925561634 0 168310931 118679687 0 0 753648129 491879315 253827115 0 0 0 160588530 702100102 277017152 896156531 0 0 0 0 794860415 0 239611601 852086994 148725046 280480357 888124643 930168541 565449948 0 0 0 414396351 0 0 78007343 0 0 669507568...
result:
ok 100000 numbers