QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1196#710444#9553. The HermitImakfucup-team1196Success!2024-11-18 19:43:272024-11-18 19:43:34

詳細信息

Extra Test:

Time Limit Exceeded

input:

100000 9

output:


result:


ID题目提交者结果用时内存语言文件大小提交时间测评时间
#710444#9553. The Hermitucup-team1196#TL 1712ms19460kbC++201.6kb2024-11-04 19:52:512024-11-18 19:43:52

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long

using i64 = long long;
const int N=1e5+8;
vector<int>bs[N];
    const int MAXN = 1e5 + 10;
    const int MOD = 998244353;
    const int mod=MOD;

void solve() {
    int n,m;
    cin>>m>>n;
    std::vector<int> fac( m + 1), inv(m + 1);
    auto qpow = [&](int x, int y)->int{
        int ans = 1;
        while (y) {
            if (y & 1) {
                ans *= x;
                ans %= MOD;
            }
            x *= x;
            x %= MOD;
            y /= 2;
        }
        return ans;
    };
    fac[0] = 1;
    for (int i = 1; i <= m; i++) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    inv[m] = qpow(fac[m], MOD - 2);
    for (int i = m; i >= 1; i--) {
        inv[i - 1] = inv[i] * i % MOD;
    }

    auto C = [&](int x, int y)->int {
        if(x<y) return 0;
        return fac[x] * inv[x - y] % MOD* inv[y] % MOD;
    };
    for(int i=1;i<=m;++i){
        for(int j=i+i;j<=m;j+=i){
            bs[i].push_back(j);
        }
    }

    int res=0;
    auto dfs=[&](auto dfs,int u,int t,int cnt)->void{
        if(t<=0) return;
        if(cnt<t) return;
        int ans=(C(cnt,t)-C(bs[u].size(),t)+mod)%mod*(t+1)%mod;
        for(auto v:bs[u]){
            dfs(dfs,v,t-1,m/u-v/u);
        }
        res+=ans;
        if(res>=mod) res-=mod;
    };
    int lst=0;
    for(int i=1;i<=m;++i){
        dfs(dfs,i,n-1,m-i);
    }
    cout<<res<<"\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
}