QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#766538#9553. The HermitlaonongminWA 26ms8164kbC++201.5kb2024-11-20 17:39:542024-11-20 17:39:54

Judging History

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

  • [2024-11-20 17:39:54]
  • 评测
  • 测评结果:WA
  • 用时:26ms
  • 内存:8164kb
  • [2024-11-20 17:39:54]
  • 提交

answer

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int N = 200005;
const int P = 998244353;
int m,n;
int d[N],g[N];
ll fac[N],ifac[N];
ll qpow(ll x,int b)
{
    ll res = 1;
    while(b)
    {
        if(b&1) res = res*x % P;
        b>>=1;
        x = x*x % P;
    }
    return res;
}
ll inv(ll x) {return qpow(x,P-2);}
ll C(ll x,ll y){return fac[x]*ifac[x-y]%P*ifac[y]%P;}

int cnt=0;
ll b[N];
void dfs(int now)
{
    if(now>0 && m<b[now]*(1<<min(20,n-now))) return;
    if(now==n) {++cnt; return;}
    for(int i=2;i<=m;++i)
    {
        if(b[now]*i > m) break;
        b[now+1] = b[now]*i;
        dfs(now+1);
    }
}
void solve()
{
    cin>>m>>n;
    ll ans = (C(m,n)*n) % P;
    // cout<<C(m,n)<<'\n';
    for(int i=1;i<=m;++i)
    {
        for(int j=i+i;j<=m;j+=i)
        {
            ++d[j]; ++g[i];
        }
    }
    for(int i=1;i<=m;++i)
    {
        for(int j=1;j<=min(g[i],n-1);++j)
        {
            int k = n-1-j;
            if(k>d[i]) continue;  //左k右j
            ans = (ans+P-(C(d[i],k)*C(g[i],j))%P) % P;
        }
    }
    b[0]=1;
    dfs(0);
    b[1]=1;
    dfs(1);
    // cout<<cnt<<'\n';
    ans = (ans+P-cnt) % P;
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T=1;
    // cin>>T;
    fac[0]=ifac[0]=1;
    for(int i=1;i<N;++i)
    {
        fac[i]=i*fac[i-1]%P;
        ifac[i]=inv(i)*ifac[i-1]%P;
    }
    while(T--)
    {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 20ms
memory: 7692kb

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 20ms
memory: 7752kb

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 26ms
memory: 7916kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: 0
Accepted
time: 24ms
memory: 7920kb

input:

11451 1919

output:

845616153

result:

ok 1 number(s): "845616153"

Test #5:

score: -100
Wrong Answer
time: 26ms
memory: 8164kb

input:

99998 12345

output:

195569988

result:

wrong answer 1st numbers differ - expected: '936396560', found: '195569988'