QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#781939#9553. The Hermiteinekleine18WA 69ms31164kbC++201.5kb2024-11-25 18:06:122024-11-25 18:06:12

Judging History

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

  • [2024-11-25 18:06:12]
  • 评测
  • 测评结果:WA
  • 用时:69ms
  • 内存:31164kb
  • [2024-11-25 18:06:12]
  • 提交

answer

#include<bits/stdc++.h>
#include <vector>

#define int long long
using a2=std::array<int,2>;
constexpr int mod=998244353,N=1e5+5;
int fac[N],inv[N];
int fp(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
void init(){
    fac[0]=1;
    for(int i=1;i<N;++i){
        fac[i]=fac[i-1]*i%mod;
    }
    inv[N-1]=fp(fac[N-1],mod-2);
    for(int i=N-2;i>=0;--i){
        inv[i]=inv[i+1]*(i+1)%mod;
    }
}
int C(int a,int b){
    if(a<b) return 0;
    return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
void solve(){
    init();
    int m,n;
    std::cin>>m>>n;
    int res=C(m,n)*n%mod;
    std::vector<std::map<int,int>>mp(m+1);
    for(int i=1;i<=m;++i){
        int nums=m/i;
        for(auto &[len,cnt]:mp[i]){
            res=(res-C(nums-1,len-1)*cnt%mod)%mod;
            res=(res+mod)%mod;
            if(len==1) continue;
            for(int j=i+i;j<=m;j+=i){
                mp[j][len-1]+=1;
            }
        }
        res=(res-C(nums-1,n-1))%mod;
        res=(res+mod)%mod;
        for(int j=i+i;j<=m;j+=i){
            mp[j][n-1]+=1;
        }
    }
    std::cout<<res<<'\n';
}

signed main(){
#ifdef LOCAL
    std::freopen("in.txt","r",stdin);
    std::freopen("out.txt","w",stdout);
#endif
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int _=1;
    // std::cin>>_;
    for(int i=0;i<_;++i){
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5124kb

input:

4 3

output:

7

result:

ok 1 number(s): "7"

Test #2:

score: 0
Accepted
time: 2ms
memory: 5156kb

input:

11 4

output:

1187

result:

ok 1 number(s): "1187"

Test #3:

score: 0
Accepted
time: 61ms
memory: 31164kb

input:

100000 99999

output:

17356471

result:

ok 1 number(s): "17356471"

Test #4:

score: 0
Accepted
time: 7ms
memory: 7572kb

input:

11451 1919

output:

845616153

result:

ok 1 number(s): "845616153"

Test #5:

score: -100
Wrong Answer
time: 69ms
memory: 30692kb

input:

99998 12345

output:

663351750

result:

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