组合计数积累

1

https://codeforces.com/problemset/problem/1358/C

最开始想到了棋盘走法问题，那个答案是C(n+m, m)，于是便想着把这道题区域中过对角线的部分中可能sum重复的走法剪掉，后来发现不可取，

解法很巧妙，先选中sum最小的一种（沿着顶边和右边），接下来如果想扩大，只能把顶点向左下“内缩”，这样sum可以加一，同时我们知道最大的sum，在最小最大的这个区间中，每个sum均可以通过从最小sum缩若干次达到，所以sum不同的方案数就是这个区间的范围。“In order for us to come from the minimum to the maximum way, we must bend the way exactly 1 time per each cell of table (except for the cells of the minimum way). That is, the number of changes equals the number of cells not belonging to the minimum way”这是算最大最小差值的方法。

2

https://codeforces.com/contest/1359/problem/E

打完失眠过程中想出了正确结论。

一个序列是stable的当且仅当其中有一个元素是其余元素的公因数。然后我们就可以从1到大看每个数的倍数总量够k个的话，就可以从i及它的倍数中选k-1个构成稳定序列。求组合数用费马小定理的话是log(mod)复杂度，整体nlog(mod)。

const int mod=998244353;
const int maxn=5e5+2;
ll fact[maxn];
void init(){
    fact[0]=1;
    for(int i=1;i<maxn;i++){
        fact[i]=fact[i-1]*i%mod;
    }
}
ll pow(ll x,int k){
    ll res=1;
    while(k){
        if(k&1)
            res=res*x%mod;
        x=(x*x)%mod;
        k>>=1;
    }
    return res;
}
ll rev(ll x,int p){ //费马小定理求逆元
    return pow(x,p-2)%mod;
}
ll c(int n,int m){  //C(n,m)
    ll res=0;
    try{
        res=fact[n]*rev(fact[m],mod)%mod*rev(fact[n-m],mod)%mod;
    }catch(exception e){
        cout<<n<<endl;
    }
    return res;
}

int main(){
    init();
    int n,k;
    cin>>n>>k;
    ll ans=0;
    for(int i=1;i<=n&&i*k<=n;i++){
        ll num=n/i;
        ans=(ans+c(num-1,k-1))%mod;
    }
    cout<<ans<<endl;
}