Loading...

洛谷P3861 8月月赛A (因子分解升级版)

check评论:0 条 remove_red_eye浏览量:380 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-05-20

一句话题意

给定一个整数n求将n分解为互不相同的不小于2的数的乘积的方案数,答案模998244353。

动态规划:
首先定义一个数组$f[i][j]$,表示当前乘积为 $i$ ,包含的最大的因数为 $j$ 时,方案数时多少。
这样可能可以得到 $20$ 分。
然后我们考虑优化,首先 $i$ 一定是 $n$ 的一个因数, $j$ 也同理。
于是我们可以把所有的因数预处理出来,有多少个呢?
可以先来考虑一下另一道题,给定一个数 $n$ 求 $n$ 以内的数因数最多的数的因数是多少?
这个问题可以用搜索,开一个 $60$ 以内的质数表,就解决了。
于是我们知道了,当$n \le 10^{12}$时,因数的个数最多为 $67206720$。
那这也太简单了吧!
转移的时候就只有 $6720 \times 6720 $个状态了,你可以写一个 $Hash$ 也可以根据单调性来扫(如下面的程序)。
复杂度$O(45158400)$
code:

#include <bits/stdc++.h>
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;
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名