Codeforces396A - On Number of Decompositions into Multipliers


Portal

Description

给出\(n(n\leq500)\)\([1,10^9]\)的数,令\(m=\prod_{i=1}^n a_i\)。求有多少个有序排列\(\{a_n\}\),使得\(\prod_{i=1}^n a_i=m\)。答案\(mod \ 10^9+7\);两个有序排列不同当且仅当\(\exists i,a_i \neq b_i\)

Solution

\(m\)分解质因数,即\(m=\prod_{i=1}^t p_i^{k_i}\)
\(m\)分配到\(n\)个数上,相当于依次\(k_i\)\(p_i\)分配到\(n\)个数上。因为\(p_i\)均不相同,所以不会出现重复的计算。即:
\[ans=\prod_{i=1}^t C(n+k_i-1,n-1)\] 因为\(k_i\)不超过\(nlog_210^9< 15000\),所以可以开数组C[15000][500]

时间复杂度\(O(?)\),分解质因数复杂度怎么算呀...

Code

//On Number of Decompositions into Multipliers
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
typedef long long lint;
int const N0=1e5+10;
lint const H=1e9+7;
map<int,int>::iterator it;
map<int,int> cnt;
bool isP[N0]; int cntP,P[N0];
lint C[15000][510];
void init()
{
    memset(isP,true,sizeof isP);
    for(int i=2;i<=1e5;i++)
    {
        if(isP[i]) P[++cntP]=i;
        for(int j=1;j<=cntP;j++)
        {
            if(i*P[j]>1e5) break;
            isP[i*P[j]]=false;
            if(i%P[j]==0) break;
        }
    }
    for(int i=0;i<15e3;i++) C[i][0]=1;
    for(int i=1;i<15e3;i++)
        for(int j=1;j<=i&&j<=500;j++) C[i][j]=(C[i-1][j-1]+C[i-1][j])%H;
}
int n;
int main()
{
    init();
    scanf("%d",&n);
    for(int owo=1;owo<=n;owo++)
    {
        int x; scanf("%d",&x);
        for(int i=1;i<=cntP;i++)
            while(x%P[i]==0) cnt[P[i]]++,x/=P[i];
        if(x!=1) cnt[x]++;
    }
    lint ans=1;
    for(it=cnt.begin();it!=cnt.end();it++) ans*=C[it->second+n-1][n-1],ans%=H;
    printf("%lld\n",ans);
    return 0;
}

P.S.

我VisJiao就是打死,也不吃STL一口饭!
...真香

优质内容筛选与推荐>>
1、企业销售渠道开拓的秘诀
2、MySQL常见面试题索引、表设计
3、ASP.NET操作数据库
4、265656555
5、Oracle打印日历功能


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号