UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#149814#286. 集合JLXBS1003521ms155000kbC++758b2022-07-22 12:42:182022-07-22 13:36:41

answer

#include<bits/stdc++.h>
#define ll long long 
#define M 998244353
using namespace std;
const int N=1e7+10;
ll fac[N],inv[N];
int k,n,t;
ll qpow(ll a,int b){
	ll ans=1;
	while(b){
		if(b&1) ans=ans*a%M;
		b>>=1;a=a*a%M;
	}
	return ans%M;
} 	
inline void init(){
	fac[0]=inv[0]=1;
	for(int i=1;i<=k;i++) fac[i]=fac[i-1]*i%M;
	inv[k]=qpow(fac[k],M-2);
	for(int i=k;i;i--) inv[i-1]=inv[i]*i%M; 
}
int main(){
	scanf("%d%d%d",&n,&k,&t);
	if(t==1){
		printf("1\n");return 0;
	}
	init();
	ll ans=qpow(t,n);ll pw=1,cur=1;
	for(int i=0;i<k;i++){
		(ans-=pw*cur%M*inv[i]+M)%=M;
		cur=cur*(n-i)%M;
		pw=pw*(t-1)%M;
	}
	ans=ans*t%M*qpow(qpow(t-1,k),M-2)%M;
	ans=(ans*qpow(cur*inv[k]%M,M-2)%M+M)%M;
	printf("%lld\n",ans);
	return 0;
}
Source code, Language: C++

Details

小提示：点击横条可展开更详细的信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 1168kb

input:

974358060 9789202 1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 1172kb

input:

974374867 9782669 1

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 1172kb

input:

974391674 9257635 1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 1168kb

input:

974408481 9732602 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 1172kb

input:

974425288 9207568 1

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 0ms
memory: 1172kb

input:

974442095 9682535 1

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 0ms
memory: 1168kb

input:

974458902 9157501 1

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 0ms
memory: 1168kb

input:

974475709 9632468 1

output:

1

result:

ok 1 number(s): "1"

Test #9:

score: 0
Accepted
time: 0ms
memory: 1168kb

input:

974492516 9625935 1

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 0ms
memory: 1168kb

input:

974509323 9100901 1

output:

1

result:

ok 1 number(s): "1"

Subtask #2:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 16ms
memory: 14564kb

input:

939830 855862 952890428

output:

769580874

result:

ok 1 number(s): "769580874"

Test #12:

score: 0
Accepted
time: 11ms
memory: 15928kb

input:

956637 943184 988243671

output:

729644598

result:

ok 1 number(s): "729644598"

Test #13:

score: 0
Accepted
time: 12ms
memory: 15152kb

input:

973444 893280 974942969

output:

376458332

result:

ok 1 number(s): "376458332"

Test #14:

score: 0
Accepted
time: 14ms
memory: 15540kb

input:

990251 918400 910471776

output:

601893966

result:

ok 1 number(s): "601893966"

Test #15:

score: 0
Accepted
time: 12ms
memory: 15024kb

input:

907057 885478 996995510

output:

279439643

result:

ok 1 number(s): "279439643"

Test #16:

score: 0
Accepted
time: 17ms
memory: 15176kb

input:

923864 894832 932524317

output:

754485259

result:

ok 1 number(s): "754485259"

Test #17:

score: 0
Accepted
time: 16ms
memory: 14628kb

input:

940671 859705 919223615

output:

735360983

result:

ok 1 number(s): "735360983"

Test #18:

score: 0
Accepted
time: 22ms
memory: 15496kb

input:

957478 915557 954576858

output:

846297917

result:

ok 1 number(s): "846297917"

Test #19:

score: 0
Accepted
time: 12ms
memory: 16104kb

input:

974285 954471 941276156

output:

519140979

result:

ok 1 number(s): "519140979"

Test #20:

score: 0
Accepted
time: 12ms
memory: 16196kb

input:

991092 960406 927975454

output:

393800468

result:

ok 1 number(s): "393800468"

Subtask #3:

score: 30
Accepted

Test #21:

score: 30
Accepted
time: 195ms
memory: 155000kb

input:

974694200 9844034 2

output:

717614679

result:

ok 1 number(s): "717614679"

Test #22:

score: 0
Accepted
time: 180ms
memory: 154220kb

input:

974727814 9793967 2

output:

903396834

result:

ok 1 number(s): "903396834"

Test #23:

score: 0
Accepted
time: 169ms
memory: 146016kb

input:

974744621 9268933 2

output:

293082936

result:

ok 1 number(s): "293082936"

Test #24:

score: 0
Accepted
time: 181ms
memory: 145916kb

input:

974761428 9262400 2

output:

568471499

result:

ok 1 number(s): "568471499"

Test #25:

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

input:

974795042 9212333 2

output:

174349571

result:

ok 1 number(s): "174349571"

Test #26:

score: 0
Accepted
time: 144ms
memory: 152556kb

input:

974811849 9687300 2

output:

54692201

result:

ok 1 number(s): "54692201"

Test #27:

score: 0
Accepted
time: 172ms
memory: 144352kb

input:

974828656 9162266 2

output:

178547426

result:

ok 1 number(s): "178547426"

Test #28:

score: 0
Accepted
time: 158ms
memory: 151772kb

input:

974845463 9637233 2

output:

848853881

result:

ok 1 number(s): "848853881"

Test #29:

score: 0
Accepted
time: 141ms
memory: 143468kb

input:

974879077 9105666 2

output:

939782679

result:

ok 1 number(s): "939782679"

Test #30:

score: 0
Accepted
time: 156ms
memory: 150888kb

input:

974895884 9580633 2

output:

341052536

result:

ok 1 number(s): "341052536"

Subtask #4:

score: 20
Accepted

Test #31:

score: 20
Accepted
time: 14ms
memory: 16032kb

input:

974912691 950001 982518805

output:

127609714

result:

ok 1 number(s): "127609714"

Test #32:

score: 0
Accepted
time: 19ms
memory: 15600kb

input:

974929498 922425 969218103

output:

988959503

result:

ok 1 number(s): "988959503"

Test #33:

score: 0
Accepted
time: 19ms
memory: 16736kb

input:

974946305 994850 904746910

output:

652493805

result:

ok 1 number(s): "652493805"

Test #34:

score: 0
Accepted
time: 16ms
memory: 15876kb

input:

974979919 939698 926799451

output:

297254489

result:

ok 1 number(s): "297254489"

Test #35:

score: 0
Accepted
time: 19ms
memory: 15440kb

input:

974996726 912122 913498749

output:

3872843

result:

ok 1 number(s): "3872843"

Test #36:

score: 0
Accepted
time: 11ms
memory: 15600kb

input:

975013533 922374 948851992

output:

824700719

result:

ok 1 number(s): "824700719"

Test #37:

score: 0
Accepted
time: 22ms
memory: 16736kb

input:

975030340 994799 935551290

output:

910283886

result:

ok 1 number(s): "910283886"

Test #38:

score: 0
Accepted
time: 16ms
memory: 16308kb

input:

975047147 967223 970904533

output:

524094901

result:

ok 1 number(s): "524094901"

Test #39:

score: 0
Accepted
time: 20ms
memory: 15872kb

input:

975063954 939647 957603831

output:

976518923

result:

ok 1 number(s): "976518923"

Test #40:

score: 0
Accepted
time: 22ms
memory: 15440kb

input:

975080761 912071 944303129

output:

671474890

result:

ok 1 number(s): "671474890"

Subtask #5:

score: 10
Accepted

Test #41:

score: 10
Accepted
time: 155ms
memory: 154300kb

input:

975097568 9798732 979656372

output:

511951684

result:

ok 1 number(s): "511951684"

Test #42:

score: 0
Accepted
time: 135ms
memory: 146092kb

input:

975114375 9273698 966355670

output:

258620932

result:

ok 1 number(s): "258620932"

Test #43:

score: 0
Accepted
time: 142ms
memory: 153512kb

input:

975131182 9748665 901884477

output:

680834727

result:

ok 1 number(s): "680834727"

Test #44:

score: 0
Accepted
time: 159ms
memory: 145212kb

input:

975164796 9217098 923937018

output:

420034109

result:

ok 1 number(s): "420034109"

Test #45:

score: 0
Accepted
time: 168ms
memory: 152632kb

input:

975181603 9692065 910636316

output:

969346798

result:

ok 1 number(s): "969346798"

Test #46:

score: 0
Accepted
time: 149ms
memory: 144424kb

input:

975198410 9167031 945989559

output:

153740899

result:

ok 1 number(s): "153740899"

Test #47:

score: 0
Accepted
time: 165ms
memory: 151852kb

input:

975215217 9641998 932688857

output:

617915726

result:

ok 1 number(s): "617915726"

Test #48:

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

input:

975248831 9591931 954741398

output:

414830040

result:

ok 1 number(s): "414830040"

Test #49:

score: 0
Accepted
time: 146ms
memory: 150960kb

input:

975265638 9585398 990094641

output:

300778334

result:

ok 1 number(s): "300778334"

Test #50:

score: 0
Accepted
time: 137ms
memory: 142760kb

input:

975282445 9060364 976793939

output:

153955626

result:

ok 1 number(s): "153955626"

中文 English

Server time: 2025-02-23 06:50:54 | 开源项目