搜索、组合数学

首先 $k$ 因数分解得到的数至多 $O(\log k)$ 个。

考虑搜索，记 $sum_{i,j}$ 为使用 $i$ 个不为 $1$ 的数以固定顺序排列，并且 $i$ 个数的乘积恰好为 $j$ 的方案数。搜索预处理所有 $sum_{i,j}$ 的值。注意由于 $sum_{i,1} = 0$，需要特判 $k=1$ 的情况。

由于 $n$ 不可枚举考虑枚举 $k$，由于乘积为 $k$ 的所有序列长度可能不同（但是规模较小）枚举序列长度记为 $m$ 得到下式。

$$sum_{m,k} \sum_{i=m}^{n} C_{i}^{m}$$

组合数列求和考虑递推式 $C_{i}^{j} = C_{i-1}^{j} + C_{i-1}^{j-1}$，显然有 $C_{m}^{m} = 1 = C_{m+1}^{m+1}$，而 $C_{m+1}^{m} + C_{m+1}^{m+1} = C_{m+2}^{m+1}$，又有 $C_{m+2}^{m} + C_{m+2}^{m+1} = C_{m+3}^{m+1}$，最终化为下式。

$$sum_{m,k} C_{n+1}^{m+1}$$

注意到 $n$ 很大但 $m$ 很小，以 $\dfrac{n^{\underline m}}{m!} = \dfrac{\prod_{i=n-m+1}^{n} i}{\prod_{i=1}^{m} i}$ 形式计算 $C_{n}^{m}$ 的值。

预处理数组 $sum$ 的时间复杂度视为常数，特判 $k=1$ 的情况。预处理阶乘逆元，时间复杂度 $O(k \log^2 k)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int lim=100'000,mod=998'244'353;
int n,k,sum[35][100'005];
Mint<mod> inv[50];
inline Mint<mod> C(int n,int m){
    if(m>n) return Mint<mod>(0);
    Mint<mod> ret=inv[m];
    for(int i=n-m+1;i<=n;i++) ret*=i;
    return ret;
}
Mint<mod> calculate(int x){
    if(x==1) return Mint<mod>(n);
    Mint<mod> ret(0);
    for(int i=1;i<=30;i++) ret+=sum[i][x]*C(n+1,i+1);
    return ret;
}
void solution(){
    cin>>k>>n;
    for(int i=1;i<=k;i++) cout<<calculate(i)<<" \n"[i==k];
}
int T;
void dfs(int x,int mul){
    for(int i=2;i<=lim;i++){
        if(1ll*i*mul>lim) break;
        ++sum[x+1][mul*i];
        dfs(x+1,mul*i);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    dfs(0,1);
    inv[0]=1;
    for(int i=1;i<=35;i++) inv[i]=inv[i-1]*i;
    inv[35]=~inv[35];
    for(int i=35;i>=1;i--) inv[i-1]=inv[i]*i;
    cin>>T;
    while(T--) solution();
    return 0;
}