ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#149754 | #286. 集合 | gxy001 | 100 | 9851ms | 116624kb | C++11 | 1.4kb | 2022-07-22 09:22:19 | 2022-07-22 13:31:17 |
answer
#include<iostream>
using std::cin;
using std::cout;
int const mod=998244353;
int n,k,q,fac[10000010],ifac[10000010];
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;
}
void init(int n){
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=pow(fac[n],mod-2);
for(int i=n;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod;
}
int C(int n,int m){
return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main(){
std::ios::sync_with_stdio(false),cin.tie(nullptr);
int T;
cin>>n>>k>>T;
init(k);
q=pow(T,mod-2),--k,--n;
int c=1;
if(q==1){
c=ifac[k];
for(int i=0;i<k;i++) c=1ll*c*(n+1-i)%mod;
c=1ll*c*pow(k+1,mod-2)%mod*(n+1-k)%mod;
}else{
static int C[10000010];
int iv=pow(1-q+mod,mod-2),f=(1ll-pow(q,n+1)+mod)*iv%mod;
C[0]=1;
for(int i=1;i<=k;i++) C[i]=1ll*C[i-1]*(n-i+1)%mod;
for(int i=1;i<=k;i++) C[i]=1ll*C[i]*ifac[i]%mod;
for(int i=k,pw=pow(q,n-k);~i;i--,pw=1ll*pw*q%mod) C[i]=(mod-1ll)*C[i]%mod*pw%mod;
for(int i=1;i<=k;i++){
f=(f+C[i-1]+1ll*q*C[i])%mod*iv%mod;
if(i==k) c=f;
}
}
int a=((mod-1ll)*n%mod*c+(2ll-n+mod)*k%mod*c+1ll*k*(k-1)%mod*c)%mod;
int f=0,ans=0;
f=1ll*a*pow(k-n+mod,mod-2)%mod*pow(k+1,mod-2)%mod;
ans=1ll*pow(q,k)*f%mod;
++n,++k;
ans=1ll*ans*pow(T,n)%mod;
int d=ifac[k];
for(int i=0;i<k;i++) d=1ll*d*(n-i)%mod;
ans=1ll*pow(d,mod-2)*ans%mod;
cout<<ans<<'\n';
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 200ms
memory: 77736kb
input:
974358060 9789202 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 197ms
memory: 77688kb
input:
974374867 9782669 1
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 182ms
memory: 73588kb
input:
974391674 9257635 1
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 184ms
memory: 77300kb
input:
974408481 9732602 1
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 171ms
memory: 73192kb
input:
974425288 9207568 1
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 194ms
memory: 76904kb
input:
974442095 9682535 1
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 193ms
memory: 72804kb
input:
974458902 9157501 1
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 195ms
memory: 76512kb
input:
974475709 9632468 1
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 186ms
memory: 76464kb
input:
974492516 9625935 1
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 189ms
memory: 72360kb
input:
974509323 9100901 1
output:
1
result:
ok 1 number(s): "1"
Subtask #2:
score: 30
Accepted
Test #11:
score: 30
Accepted
time: 33ms
memory: 11292kb
input:
939830 855862 952890428
output:
769580874
result:
ok 1 number(s): "769580874"
Test #12:
score: 0
Accepted
time: 31ms
memory: 12312kb
input:
956637 943184 988243671
output:
729644598
result:
ok 1 number(s): "729644598"
Test #13:
score: 0
Accepted
time: 30ms
memory: 11728kb
input:
973444 893280 974942969
output:
376458332
result:
ok 1 number(s): "376458332"
Test #14:
score: 0
Accepted
time: 41ms
memory: 12024kb
input:
990251 918400 910471776
output:
601893966
result:
ok 1 number(s): "601893966"
Test #15:
score: 0
Accepted
time: 34ms
memory: 11640kb
input:
907057 885478 996995510
output:
279439643
result:
ok 1 number(s): "279439643"
Test #16:
score: 0
Accepted
time: 31ms
memory: 11752kb
input:
923864 894832 932524317
output:
754485259
result:
ok 1 number(s): "754485259"
Test #17:
score: 0
Accepted
time: 36ms
memory: 11336kb
input:
940671 859705 919223615
output:
735360983
result:
ok 1 number(s): "735360983"
Test #18:
score: 0
Accepted
time: 39ms
memory: 11988kb
input:
957478 915557 954576858
output:
846297917
result:
ok 1 number(s): "846297917"
Test #19:
score: 0
Accepted
time: 32ms
memory: 12444kb
input:
974285 954471 941276156
output:
519140979
result:
ok 1 number(s): "519140979"
Test #20:
score: 0
Accepted
time: 37ms
memory: 12516kb
input:
991092 960406 927975454
output:
393800468
result:
ok 1 number(s): "393800468"
Subtask #3:
score: 30
Accepted
Test #21:
score: 30
Accepted
time: 352ms
memory: 116624kb
input:
974694200 9844034 2
output:
717614679
result:
ok 1 number(s): "717614679"
Test #22:
score: 0
Accepted
time: 378ms
memory: 116032kb
input:
974727814 9793967 2
output:
903396834
result:
ok 1 number(s): "903396834"
Test #23:
score: 0
Accepted
time: 358ms
memory: 109880kb
input:
974744621 9268933 2
output:
293082936
result:
ok 1 number(s): "293082936"
Test #24:
score: 0
Accepted
time: 377ms
memory: 109808kb
input:
974761428 9262400 2
output:
568471499
result:
ok 1 number(s): "568471499"
Test #25:
score: 0
Accepted
time: 372ms
memory: 109220kb
input:
974795042 9212333 2
output:
174349571
result:
ok 1 number(s): "174349571"
Test #26:
score: 0
Accepted
time: 386ms
memory: 114784kb
input:
974811849 9687300 2
output:
54692201
result:
ok 1 number(s): "54692201"
Test #27:
score: 0
Accepted
time: 363ms
memory: 108632kb
input:
974828656 9162266 2
output:
178547426
result:
ok 1 number(s): "178547426"
Test #28:
score: 0
Accepted
time: 373ms
memory: 114200kb
input:
974845463 9637233 2
output:
848853881
result:
ok 1 number(s): "848853881"
Test #29:
score: 0
Accepted
time: 337ms
memory: 107968kb
input:
974879077 9105666 2
output:
939782679
result:
ok 1 number(s): "939782679"
Test #30:
score: 0
Accepted
time: 332ms
memory: 113532kb
input:
974895884 9580633 2
output:
341052536
result:
ok 1 number(s): "341052536"
Subtask #4:
score: 20
Accepted
Test #31:
score: 20
Accepted
time: 40ms
memory: 12392kb
input:
974912691 950001 982518805
output:
127609714
result:
ok 1 number(s): "127609714"
Test #32:
score: 0
Accepted
time: 27ms
memory: 12072kb
input:
974929498 922425 969218103
output:
988959503
result:
ok 1 number(s): "988959503"
Test #33:
score: 0
Accepted
time: 34ms
memory: 12920kb
input:
974946305 994850 904746910
output:
652493805
result:
ok 1 number(s): "652493805"
Test #34:
score: 0
Accepted
time: 33ms
memory: 12276kb
input:
974979919 939698 926799451
output:
297254489
result:
ok 1 number(s): "297254489"
Test #35:
score: 0
Accepted
time: 31ms
memory: 11952kb
input:
974996726 912122 913498749
output:
3872843
result:
ok 1 number(s): "3872843"
Test #36:
score: 0
Accepted
time: 39ms
memory: 12072kb
input:
975013533 922374 948851992
output:
824700719
result:
ok 1 number(s): "824700719"
Test #37:
score: 0
Accepted
time: 27ms
memory: 12920kb
input:
975030340 994799 935551290
output:
910283886
result:
ok 1 number(s): "910283886"
Test #38:
score: 0
Accepted
time: 38ms
memory: 12596kb
input:
975047147 967223 970904533
output:
524094901
result:
ok 1 number(s): "524094901"
Test #39:
score: 0
Accepted
time: 39ms
memory: 12276kb
input:
975063954 939647 957603831
output:
976518923
result:
ok 1 number(s): "976518923"
Test #40:
score: 0
Accepted
time: 44ms
memory: 11952kb
input:
975080761 912071 944303129
output:
671474890
result:
ok 1 number(s): "671474890"
Subtask #5:
score: 10
Accepted
Test #41:
score: 10
Accepted
time: 387ms
memory: 116092kb
input:
975097568 9798732 979656372
output:
511951684
result:
ok 1 number(s): "511951684"
Test #42:
score: 0
Accepted
time: 349ms
memory: 109940kb
input:
975114375 9273698 966355670
output:
258620932
result:
ok 1 number(s): "258620932"
Test #43:
score: 0
Accepted
time: 374ms
memory: 115500kb
input:
975131182 9748665 901884477
output:
680834727
result:
ok 1 number(s): "680834727"
Test #44:
score: 0
Accepted
time: 346ms
memory: 109272kb
input:
975164796 9217098 923937018
output:
420034109
result:
ok 1 number(s): "420034109"
Test #45:
score: 0
Accepted
time: 377ms
memory: 114844kb
input:
975181603 9692065 910636316
output:
969346798
result:
ok 1 number(s): "969346798"
Test #46:
score: 0
Accepted
time: 340ms
memory: 108688kb
input:
975198410 9167031 945989559
output:
153740899
result:
ok 1 number(s): "153740899"
Test #47:
score: 0
Accepted
time: 409ms
memory: 114256kb
input:
975215217 9641998 932688857
output:
617915726
result:
ok 1 number(s): "617915726"
Test #48:
score: 0
Accepted
time: 371ms
memory: 113668kb
input:
975248831 9591931 954741398
output:
414830040
result:
ok 1 number(s): "414830040"
Test #49:
score: 0
Accepted
time: 343ms
memory: 113588kb
input:
975265638 9585398 990094641
output:
300778334
result:
ok 1 number(s): "300778334"
Test #50:
score: 0
Accepted
time: 340ms
memory: 107436kb
input:
975282445 9060364 976793939
output:
153955626
result:
ok 1 number(s): "153955626"