题解 P3861 【8月月赛A】

vegetabird · 2017-08-10 17:06:59 · 题解

对于每一个N，我们先求出它的第i小因子fac_{i}, 然后记录下因子j所对应的位置pos_{j}。这里有一个小技巧：

+if j \le \sqrt{N}, 则令pos1_{j}=pos_{j}

+if j > \sqrt{N}, 则令pos2_{\frac{N}{j}}=pos_{j}

这样就可以把空间压缩为O(\sqrt{N})

然后令dp_{ij}为把fac_{i}分解成若干个小于等于fac_{j}的数（包括1）的积的方案总数，则：

dp_{ij}=dp_{i j-1}

if i=j, dp_{ij}++

if fac_{i} \equiv 0,mod( fac_{j}), dp_{ij}+=dp_{pos_{\frac{fac{i}}{fac_{j}}} j-1}

CODE:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<utility>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
#include<map>
using namespace std;
long long T,n;
long long fac[11000];
int dp[11000][11000];
const long long mod=998244353;
int pos1[1000010],pos2[1000010];
map<long long,int>ans;
int main(){
    cin>>T;
    register int i,j,s;long long q;
    while(T--){
        cin>>n;
        if(ans[n]){
            cout<<ans[n]<<endl;
            continue;
        }
        s=0;
        q=sqrt(n);
        if(n%q==0){
            fac[++s]=q;
            if(q*q!=n){
                fac[++s]=n/q;
            }
        }
        for(i=1;i<q;i++){
            if(n%i==0){
                fac[++s]=i;
                fac[++s]=n/i;
            }
        }
        stable_sort(fac+1,fac+s+1);
        for(i=0;i<=s;i++){
            for(j=0;j<=s;j++){
                dp[i][j]=0;
            }
        }
        for(i=1;i<=s;i++){
            dp[i][i]=1;
            if(fac[i]<=q){
                pos1[fac[i]]=i;
            }else{
                pos2[n/fac[i]]=i;
            }
        }
        for(i=1;i<=s;i++){
            for(j=1;j<=s;j++){
                dp[i][j]+=dp[i][j-1];
                if(i<=j){
                    continue;
                }
                if(fac[i]%fac[j]==0){
                    long long tmp=fac[i]/fac[j];
                    if(tmp<=q){
                        dp[i][j]+=dp[pos1[tmp]][j-1];
                    }else{
                        dp[i][j]+=dp[pos2[n/tmp]][j-1];
                    }
                    dp[i][j]%=mod;
                }
            }
        }
        cout<<dp[s][s]-1<<endl;
        ans[n]=dp[s][s]-1;
    }
}