QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#769030 | #9553. The Hermit | Suhy# | TL | 47ms | 23428kb | C++17 | 1.7kb | 2024-11-21 15:50:22 | 2024-11-21 15:50:23 |
Judging History
answer
#include<bits/stdc++.h>
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],*g[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;
}
std::vector <int> fac[100086];
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,D[i]=2;
for(j=0;j<s&&p[j]<=i&&(k=i*p[j],k<=n);++j)
b[k]=1,l[k]=p[j],D[k]=D[i]+1;
}
for(int i = 1; i <= n; i ++)
for(int j = i+i; j <= n; j += i)
fac[j].push_back(i);
D[1]=1;
for(i=1;i<=n;++i){
g[i]=new u64[D[i]+1];
for(j=0;j<D[i];++j)g[i][j+1]=0;
g[i][0]=1;
for(int j : fac[i]){
for(k=0;k<=D[j];++k)(g[i][k+1]+=g[j][k])%=M;
}
}
for(i=1;i<=n;++i)if(d[n/i]<D[i])d[n/i]=D[i];
for(i=n;i;--i)
for(k=2;k<=i&&i/k>=m-d[i];++k)
if(d[i/k]<d[i])d[i/k]=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;
}
}
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+=g[i][j]*u%M*(m-j)%M;
if(j)ans+=g[i][j-1]*u%M*(m-j)%M;
// printf("%d %d\n",i,j);return 0;
}
printf("%llu",ans%M);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 9500kb
input:
4 3
output:
7
result:
ok 1 number(s): "7"
Test #2:
score: 0
Accepted
time: 0ms
memory: 9560kb
input:
11 4
output:
1187
result:
ok 1 number(s): "1187"
Test #3:
score: 0
Accepted
time: 47ms
memory: 23428kb
input:
100000 99999
output:
17356471
result:
ok 1 number(s): "17356471"
Test #4:
score: 0
Accepted
time: 5ms
memory: 10340kb
input:
11451 1919
output:
845616153
result:
ok 1 number(s): "845616153"
Test #5:
score: 0
Accepted
time: 42ms
memory: 23400kb
input:
99998 12345
output:
936396560
result:
ok 1 number(s): "936396560"
Test #6:
score: -100
Time Limit Exceeded
input:
100000 1