QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#764113#9553. The HermitRykonyWA 43ms24372kbC++201.1kb2024-11-20 00:28:282024-11-20 00:28:29

Judging History

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

  • [2024-11-20 00:28:29]
  • 评测
  • 测评结果:WA
  • 用时:43ms
  • 内存:24372kb
  • [2024-11-20 00:28:28]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using LL=long long;
const LL mod=998244353;

LL qpow(LL a,LL n)
{
	LL ans=1;
	while (n){
		if (n&1) ans=ans*a%mod;
		a=a*a%mod;
		n>>=1;
	}
	return ans;
}

int main()
{
	cin.tie(0)->sync_with_stdio(false);
	int _=1;
//	cin>>_;
	while (_--){
		LL n,m;
		cin>>n>>m;
		vector <vector <LL> > s(n+10,vector <LL> (20,0));
		for (LL i=1;i<=n;i++){
			s[i][1]=1;
			for (LL j=2;j<=n;j++){
				if (i*j>n) break;
				int cnt=2;
				for (LL k=i*j;k<=n;k*=j){
					s[k][cnt]++;
					s[k][cnt++]%=mod;
				}
			}
		}
		
		vector <LL> fp(n+10,1),dfp(n+10,1);
		for (int i=1;i<=n;i++){
			fp[i]=fp[i-1]*i%mod;
			dfp[i]=qpow(fp[i],mod-2);
		}
	
		auto C=[&](int a,int b) -> LL
		{
			if (a<b or a<0 or b<0) return 0ll;
			return fp[a]*dfp[b]%mod*dfp[a-b]%mod;
		};	//C(n,m)
		
		LL ans=C(n,m)*m%mod;
		ans=((ans-C(n-1,m-1))%mod+mod)%mod;
		for (int i=2;i<=n;i++){
			int t=n/i;
			for (int j=0;j<20;j++){
				ans=((ans-C(t-1,m-j)*s[i][j]%mod)%mod+mod)%mod;
			}
		}
		cout<<ans<<'\n';
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3828kb

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

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

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 43ms
memory: 24372kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: 0
Accepted
time: 5ms
memory: 5884kb

input:

11451 1919

output:

845616153

result:

ok 1 number(s): "845616153"

Test #5:

score: -100
Wrong Answer
time: 34ms
memory: 24216kb

input:

99998 12345

output:

868880582

result:

wrong answer 1st numbers differ - expected: '936396560', found: '868880582'