题解：P3861 拆分

· · 题解

很妙的一道计数 dp 题。

根据数学直觉，我们可以感受到就算是一个很大的数，它的因数个数也是较小的。由于 2\le n \le 10^{12}，可以用程序分解质因数，发现在这个范围内的数的最大因数个数也不会超过 10^4。所以数组可以开一个二维的啦。

由于题目让我们计算方案数，可以用 dp 计算方案数。

考虑先将 n 的因数记录下来并排序（因为之后我们是根据位置在前的数的乘积计算出位置在后的因数的值），得到序列 a。

记 dp_{i,j} 表示 n 的第 i 个因数用 n 的前 j 个因数表示出来的方案数，pos_{i} 为数字 i 在因数序列 a 中的位置下标。

当前的第 j 个因数可以选，也可以不选，那么有 dp 方程：

dp_{i,j}=\begin{cases}dp_{i,j-1} ,a_{j}\nmid a_{i} \\ dp_{i,j-1}+dp_{pos_{\frac{a_i}{a_j}},j},a_{j}\mid a_{i}\end{cases}

但是，这里会出现一个问题，由于本题值域很大，pos 数组会溢出，我们可以将值域为 1\sim n 的数分解为 1\sim \sqrt{n} 和 \sqrt{n}+1\sim n 的数，分为两个 pos1 和 pos2 数组存储下标。

由于要排除 1\times n 的情况，所以最后的 dp_{n,n}-1 即是答案。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+20;
const int maxm=2e6+20;
const int mod=998244353;
#define ll long long
ll t,idx;
ll a[maxn],dp[maxn][maxn],x,pos1[maxm],pos2[maxm];
ll n;
inline ll get(ll i,ll j){
    x=a[i]/a[j];
    ll k=(ll)(sqrt(n));
    if(x<=k) return pos1[x];
    else return pos2[n/x];
}
inline void solve(){
    idx=0;
    for(ll i=1;i<=n/i;i++){
        if(n%i==0) {
            a[++idx]=i;
            if(i!=n/i) a[++idx]=n/i;
        }
    }
    sort(a+1,a+idx+1);
    for(ll i=1;i<=(idx+1)/2;i++) pos1[a[i]]=i,pos2[a[i]]=idx-i+1;//记录下标
    for(ll i=1;i<=idx;i++) dp[i][1]=(i==1);//初始状态
    for(ll i=1;i<=idx;i++){
        for(ll j=2;j<=idx;j++){
            dp[i][j]=dp[i][j-1];
            if(a[i]%a[j]==0) dp[i][j]=(dp[i][j]+dp[get(i,j)][j-1])%mod;
        }
    }
    printf("%lld\n",dp[idx][idx]-1);
}
int main(){
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        solve();        
    }
    return 0;
}