QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#769888#9553. The HermitNana7#WA 178ms20108kbC++141.3kb2024-11-21 19:46:352024-11-21 19:46:36

Judging History

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

  • [2024-11-21 19:46:36]
  • 评测
  • 测评结果:WA
  • 用时:178ms
  • 内存:20108kb
  • [2024-11-21 19:46:35]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define I inline
#define int long long
using namespace std;

const int mod = 998244353;
const int N = 100010;
const int LG = 19;
int mul[N],inv[N],f[LG][N];
int n,m,red,ans;


int qpow(int x,int y) {
	if(y==0) return 1;
	if(y==1) return x;
	int mk=qpow(x,y/2);
	return y%2?mk*mk%mod*x%mod:mk*mk%mod;
}
I int C(int x,int y) {
	if(x<y) return 0;
	return mul[x]*inv[y]%mod*inv[x-y]%mod;
}
I void deal(int x) {
	for(int i=1;i*x<=m;++i) {
		int nxt=i*x;
		for(int pre=0;pre<=18;++pre) {
			int nd=n-pre-2,hv1=m/nxt-1,hv2=m/x-(nxt/x);
			if(hv2<nd||nd<0) continue;
			red+=f[pre][x]*(C(hv2,nd)-C(hv1,nd)+mod)%mod*(pre+1)%mod;
			red%=mod;
		}
		if(n<=18) {
			red+=f[n-1][x]*n%mod;
			red%=mod;
		}
	}
	//cout<<red<<endl;
} 
signed main()
{
	{
		mul[0]=inv[0]=1;
		for(int i=1;i<=100000;++i) mul[i]=mul[i-1]*i%mod;
		inv[100000]=qpow(mul[100000],mod-2);
		for(int i=99999;i>=1;--i) inv[i]=inv[i+1]*(i+1)%mod;
	}
//	cout<<C(100000,99999)<<endl;
	for(int i=1;i<=100000;++i) {
		f[0][i]=1;
		for(int j=1;j<=18;++j) {
			for(int k=2;k*i<=100000;++k) {
				f[j][k*i]+=f[j-1][i];
				f[j][k*i]%=mod;
			}
		} 
	} 
	cin>>m>>n;
	if(n==1) {
		cout<<0<<endl;
		return 0;
	}
	for(int i=1;i<=m;++i) {
		deal(i);
	}
	cout<<(C(m,n)*n%mod-red+mod)%mod<<endl;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 58ms
memory: 20048kb

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 66ms
memory: 20064kb

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 79ms
memory: 20052kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: 0
Accepted
time: 72ms
memory: 20056kb

input:

11451 1919

output:

845616153

result:

ok 1 number(s): "845616153"

Test #5:

score: 0
Accepted
time: 99ms
memory: 20104kb

input:

99998 12345

output:

936396560

result:

ok 1 number(s): "936396560"

Test #6:

score: 0
Accepted
time: 67ms
memory: 20108kb

input:

100000 1

output:

0

result:

ok 1 number(s): "0"

Test #7:

score: -100
Wrong Answer
time: 178ms
memory: 20104kb

input:

100000 15

output:

190061165

result:

wrong answer 1st numbers differ - expected: '190067060', found: '190061165'