QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#289314	#5817. 小学生数学题	Michstabe	100 ✓	481ms	325960kb	C++14	723b	2023-12-23 16:51:44	2023-12-23 16:51:44

Judging History

你现在查看的是最新测评结果

[2023-12-23 16:51:44]
评测

测评结果：100
用时：481ms
内存：325960kb

查看

[2023-12-23 16:51:44]
提交

answer

#pragma once


#include<bits/stdc++.h>
#define maxn 150000
#define mod 998244353
#define FOR(x,y) for(int i=x;i<=y;i++)
using namespace std;
const int N = 2*1e7 + 10;
typedef long long ll;

ll n,k,cnt,ans,sum=1;
ll a[N],b[N],c[N];
inline ll ksm(ll x,ll y){ 
    ll z=1;
    while(y){
        if(y&1) z=z*x%mod;
        x=x*x%mod;y>>=1;
    }return z;
}inline void ny(){
	FOR(2,n){
		if(!c[i]){
			c[i]=b[++cnt]=i;a[i]=ksm(ksm(i,mod-2),k);
		}for(int j=1;b[j]*i<=n&&j<=cnt&&b[j]<=c[i];j++){
			c[b[j]*i]=b[j];
			a[b[j]*i]=(a[b[j]]*a[i])%mod;
		}
	}
}
int main(){
	cin>>n>>k;
	a[1]=1; //逆元
	ny();
	FOR(1,n){
		ans=(ans+sum*a[i]%mod),ans%=mod;
		sum=sum*(i+1),sum%=mod;
	}cout<<ans;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10

Accepted

time: 187ms

memory: 162540kb

input:

9450395 1

output:

688545438

result:

ok single line: '688545438'

Test #2:

score: 10

Accepted

time: 181ms

memory: 152932kb

input:

8978812 1

output:

334565356

result:

ok single line: '334565356'

Test #3:

score: 10

Accepted

time: 180ms

memory: 154204kb

input:

8944235 1

output:

982802915

result:

ok single line: '982802915'

Test #4:

score: 10

Accepted

time: 143ms

memory: 122756kb

input:

7081118 3

output:

599009773

result:

ok single line: '599009773'

Test #5:

score: 10

Accepted

time: 164ms

memory: 135900kb

input:

7904241 3

output:

871243720

result:

ok single line: '871243720'

Test #6:

score: 10

Accepted

time: 201ms

memory: 168680kb

input:

9921275 3

output:

549818101

result:

ok single line: '549818101'

Test #7:

score: 10

Accepted

time: 443ms

memory: 293120kb

input:

17575748 14135489

output:

69236780

result:

ok single line: '69236780'

Test #8:

score: 10

Accepted

time: 481ms

memory: 325960kb

input:

19858362 14822524

output:

239890381

result:

ok single line: '239890381'

Test #9:

score: 10

Accepted

time: 470ms

memory: 314188kb

input:

18848696 15530895

output:

88125041

result:

ok single line: '88125041'

Test #10:

score: 10

Accepted

time: 445ms

memory: 297224kb

input:

17787945 13890407

output:

989967864

result:

ok single line: '989967864'

Extra Test:

score: 0

Extra Test Passed