阅读了多遍 @WJiannan 的题解，还是有很多不理解的地方，翻新一下。
新奇 dp 题。
暴力地，令 \(dp_{i,j}\) 为将 \(i\) 拆分为任意个不大于 \(j\) 的因数之积的方案数，则有 \(dp_{i,j}=dp_{i,j-1}+\sum_{k|i}dp_{k,j-1}\)。
发现对于任意对 \(dp_{n,n}\) 有贡献的 \(dp_{k,j-i}\) 都满足 \(k|n\)，考虑舍弃无用状态。
将 \(n\) 升序分解因数得到序列 \(p\)。令 \(dp_{i,j}\) 为将 \(p_i\) 拆分为任意个不大于 \(p_j\) 的因数之积的方案数，则有 \(dp_{i,j}=dp_{i,j-1}+\sum_{p_k | p_i} dp_{k,j-1}\)，相当于只选了一个 \(p_j\) 或者不选的方案数之和。
具体到实现，枚举 \(k\) 和 \(j\)，计算 \(dp_{k,j}\) 对于 \(dp_{i,j+1}\) 的贡献，其中 \(i=p_k \times p_{j+1}\)，发现 \(k\) 不变时，\(i\) 随 \(j\) 增大而增大，在增大 \(j\) 的同时维护 \(i\) 可以节省时间。令 \(m\) 为 \(n\) 的因数个数，时间复杂度 \(O(m^2)\)，\(m \leq 6720\) 足以通过此题。
code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=7000+10,mod=998244353;
int t,n,p[N],dp[N][N],qp;
signed main()
{
scanf("%d",&t);
while(t--)
{
qp=0;
memset(dp,0,sizeof(dp));
scanf("%lld",&n);
for(int i=1;i*i<=n;i++)
{
if(n%i==0)
{
qp++,p[qp]=i;
if(n/i!=i)qp++,p[qp]=n/i;
}
}
sort(p+1,p+1+qp);
p[qp+1]=n*4;
dp[1][1]=1;
for(int k=1;k<=qp;k++)
{
int i=k+1;
for(int j=2;j<=qp;j++)//按照上文，这里代表 j+1
{
if(p[j]*p[k]<=n)
{
while(p[i+1]<=p[j]*p[k])i++;
if(p[i]==p[j]*p[k])dp[i][j]=(dp[i][j]+dp[k][j-1])%mod;
}
dp[k][j]=(dp[k][j]+dp[k][j-1])%mod;
}
}
printf("%lld\n",dp[qp][qp]-1);
}
}