QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#764084#9553. The HermitRykonyWA 12ms10216kbC++20972b2024-11-20 00:04:192024-11-20 00:04:19

Judging History

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

  • [2024-11-20 00:04:19]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:10216kb
  • [2024-11-20 00:04:19]
  • 提交

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 <LL> s[n+10];
		for (LL i=2;i<=n;i++){
			int cnt=2;
			s[i].push_back(1);
			for (LL j=i;j<=n;j*=i){
				s[j].push_back(cnt);
				cnt++;
			}
		}
		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:s[i]){
				ans=((ans-C(t-1,m-j))%mod+mod)%mod;
			}
		}
		cout<<ans<<'\n';
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3628kb

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

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

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

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

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: -100
Wrong Answer
time: 3ms
memory: 4312kb

input:

11451 1919

output:

11212185

result:

wrong answer 1st numbers differ - expected: '845616153', found: '11212185'