QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#788049#9553. The Hermitfrankly6#WA 1495ms19124kbC++171.4kb2024-11-27 15:43:082024-11-27 15:43:10

Judging History

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

  • [2024-11-27 15:43:10]
  • 评测
  • 测评结果:WA
  • 用时:1495ms
  • 内存:19124kb
  • [2024-11-27 15:43:08]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#define int long long
using namespace std;
typedef long long ll;
const int p=998244353;
const int MX=100010;

int N, M, ans;
int fac[MX], invf[MX], dep[MX];
vector<int> e[MX];
int read()
{
    int r=0, f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
    return r*f;
}
int qpow(int x, int pow)
{
    int ans=1;
    while(pow)
    {
        if(pow&1) ans=ans*x%p;
        x=x*x%p;
        pow>>=1;
    }
    return ans;
}
int inv(int x) {return qpow(x,p-2);}
int C(int n, int m)
{
    if(n==0&&m==0) return 1;
    if(m>n) return ll(0);
    if(m<=n) return fac[n]*invf[m]%p*invf[n-m]%p;
}
void norm()
{
    ans=(ans%p+p)%p;
}
void dfs(int x, int f)
{
    dep[x]=dep[f]+1;
    for(int i=1;i<=dep[x];i++)
    {
        ans-=C((M-x)/x,N-i);
    }
    norm();
    for(auto u:e[x])
    {
        dfs(u,x);
    }
}
signed main()
{
    // freopen("testdata.in","r",stdin);
    fac[0]=1;
    for(int i=1;i<=100000;i++) fac[i]=fac[i-1]*i%p;
    for(int i=0;i<=100000;i++) invf[i]=inv(fac[i]);
    M=read(); N=read();
    ans=C(M,N)*N%p;
    // cout << "ans=" << ans << '\n';
    for(int i=1;i<=M;i++)
    {
        for(int j=2*i;j<=M;j+=i)
        {
            e[i].emplace_back(j);
        }
    }
    dfs(1,0);
    norm();
    cout << ans << '\n';
    return (0-0);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 8220kb

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 9ms
memory: 7996kb

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 1495ms
memory: 19124kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: -100
Wrong Answer
time: 45ms
memory: 9312kb

input:

11451 1919

output:

538056267

result:

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