QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#774268 | #9553. The Hermit | welikestudying# | WA | 1ms | 3616kb | C++20 | 708b | 2024-11-23 12:46:33 | 2024-11-23 12:46:35 |
Judging History
answer
#include<bits/stdc++.h>
#define up(a,b,c)for(int a=b;a<=c;++a)
#define dn(a,b,c)for(int a=b;a>=c;--a)
const int N=11e4,p=998244353;
using namespace std;
int n,m,fc[N],nf[N],f[N][__lg(N)+1],as;
int pw(int a,int b)
{
int rs=1;
for(;b;a=1ll*a*a%p,b/=2)
if(b&1)rs=1ll*rs*a%p;
return rs;
}
int C(int n,int m)
{
if(m>n)return 0;
return 1ll*fc[n]*nf[m]%p*nf[n-m]%p;
}
int main()
{
cin>>n>>m,fc[0]=1;
up(i,1,n)fc[i]=1ll*fc[i-1]*i%p;
nf[n]=pw(fc[n],p-2);
dn(i,n,1)nf[i-1]=1ll*nf[i]*i%p;
as=1ll*C(n,m)*m%p;
dn(i,n,1)up(j,0,min(m,__lg(i)))
{
f[i][j]=C(n/i,m-j);
up(z,2,n/i)
f[i][j]=(f[i][j]+f[z*i][j+1])%p;
}
up(i,1,n)as=(as+p-f[i][1])%p;
cout<<as;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3616kb
input:
4 3
output:
10
result:
wrong answer 1st numbers differ - expected: '7', found: '10'