QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#768817 | #9553. The Hermit | Suhy# | WA | 12ms | 6660kb | C++23 | 1.4kb | 2024-11-21 14:40:31 | 2024-11-21 14:40:31 |
Judging History
answer
#include<cstdio>
typedef unsigned long long u64;
const int M=998244353;
int n,m,i,j,k;
int s,p[10086],l[100086],D[100086];
bool b[100086];
u64 F[100086],G[100086];
u64 *f[100086];
int d[100086];
u64 ans;
u64 pow(u64 u,u64 d){
if(!u)return 1;
u64 r=pow(u>>1,d);
r*=r;
if(u&1)(r%=M)*=d;
return r%M;
}
u64 C(int n,int m){
if(n<m)return 0;
return F[n]*G[m]%M*G[n-m]%M;
}
int main(){
scanf("%d%d",&n,&m);
F[0]=1;
for(i=1;i<=n;++i)F[i]=F[i-1]*i%M;
G[n]=pow(M-2,F[n]);
for(i=n;i;--i)G[i-1]=G[i]*i%M;
for(i=2;i<=n;++i){
if(!b[i])p[s++]=i,l[i]=i;
for(j=0;j<s&&p[j]<=i&&(k=i*p[j],k<=n);++j)
b[k]=1,l[k]=p[j];
}
D[1]=1;
for(i=2;i<=n;++i){
j=1;
D[i]=1;
for(int t=i;t>1;){
if(l[t]!=k)D[i]*=j,k=l[t],j=1;
t/=l[t],++j;
}
D[i]*=j;
}
for(i=1;i<=n;++i)if(d[n/i]<D[i])d[n/i]=D[i];
for(i=1;i<=n;++i)if(d[i]){
f[i]=new u64[d[i]+1];
for(j=0;j<=d[i]&&j<m;++j){
f[i][j]=C(i,m-j);
for(k=2;k<=i&&i/k>=m-j;++k){
(f[i][j]+=M-f[i/k][j])%=M;
// if(d[i/k]<j)puts("A");
}
}
}
for(i=1;i<=n;++i)
for(j=0;j<=D[i]&&j<m;++j){
u64 u=f[n/i][j]+C(n/i-1,m-j)+M-C(n/i,m-j);
ans+=C(D[i],j)*u%M*(m-j)%M;
}
printf("%llu",ans%M);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5788kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5836kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 12ms
memory: 6444kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: 0
Accepted
time: 2ms
memory: 6212kb
input:
11451 1919
output:
845616153
result:
ok 1 number(s): "845616153"
Test #5:
score: -100
Wrong Answer
time: 4ms
memory: 6660kb
input:
99998 12345
output:
525061036
result:
wrong answer 1st numbers differ - expected: '936396560', found: '525061036'