QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#766781#9553. The HermitDarwinA66WA 340ms19484kbC++201.4kb2024-11-20 18:35:502024-11-20 18:35:53

Judging History

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

  • [2024-11-20 18:35:53]
  • 评测
  • 测评结果:WA
  • 用时:340ms
  • 内存:19484kb
  • [2024-11-20 18:35:50]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100010;
ll mod=998244353;
ll fastpow(ll a,ll n)
{
    ll base=a;
    ll res=1ll;
    while(n)
    {
        if(n&1ll)res=(res*base)%mod;
        base=(base*base)%mod;
        n>>=1;
    }
    return res;
}
ll mod_inverse(ll x)
{
    ll res=fastpow(x,mod-2);
    return res;
}
ll dp[N][20];
int main()
{
    int n,m;
    scanf("%d %d",&m,&n);
    ll ans=0ll;
    ll c=1ll*m;
    for(int i=1;i<=m;i++)dp[i][1]=1ll;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=17;j++)
        {
            for(int k=2;k*i<=m;k++)
            {
                dp[k*i][j+1]=(dp[i][j]+dp[k*i][j+1])%mod;
            }
        }
    }
    for(int i=2;i<=n;i++)
    {
        c=(c*(m+1ll-i*1ll))%mod;
        c=(c*mod_inverse(i))%mod;
        if(i==n)ans=(ans+((i*1ll*c)%mod))%mod;
    }
    for(int i=1;i<=m;i++)
    {
        int b=(m/i)-1;
        int cc=1ll;
        if(n<=19)ans=(((ans-dp[i][n])%mod)+mod)%mod;
        for(int j=1;(j+1<=n)&&(j<=b);j++)
        {
            cc=(cc*(b*1ll+1ll-j*1ll))%mod;
            cc=(cc*mod_inverse(j))%mod;
            ll temp;
            if((n-j<=19)&&n-j>=1)temp=dp[i][n-j];
            else temp=0ll;
            ans=((ans-(((temp*cc)%mod))%mod)+mod)%mod;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3784kb

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 340ms
memory: 19412kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: 0
Accepted
time: 23ms
memory: 7204kb

input:

11451 1919

output:

845616153

result:

ok 1 number(s): "845616153"

Test #5:

score: 0
Accepted
time: 280ms
memory: 19408kb

input:

99998 12345

output:

936396560

result:

ok 1 number(s): "936396560"

Test #6:

score: -100
Wrong Answer
time: 59ms
memory: 19484kb

input:

100000 1

output:

998144353

result:

wrong answer 1st numbers differ - expected: '0', found: '998144353'