UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#149754#286. 集合gxy0011009851ms116624kbC++111.4kb2022-07-22 09:22:192022-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"