注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4390 Number Sequence  

2013-08-01 21:38:07|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4390
题意:
给出一个n长的b序列,构造一个n长的a序列,使得b序列每项之积等于a序列的每项之积。问能构造出多少种a序列。
题解:
可以把问题化简为,有m种小球,第i种小球有ni个,把球放入n长的槽中,要求每个槽里至少有一个球,问有多少种放法。
容斥原理。m个球放入n个相同的槽中有c(n+m-1, n-1)种。按着一种种球来算,先求出所有球放入槽中的总放法,然后用容斥定理,算出一个槽为空,二个槽为空……如果i个槽为空有f[i]种,最后还应乘上c(n, i)。

/*
* fudq.cpp
*
* Created on: 2013-08-01
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=1010;
const int M=1000010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const double eps=1e-7;
const double PI=acos(-1.0);

LL n,k,f[N],p[N],c[505][505];
//c记录组合数,f记录因子,p记录对应因子数

void Join(LL i,LL t)
{
LL j;
for(j=0;j<k;j++)
if(f[j] == i)
{
p[j]+=t;
break;
}
if(j == k)
{
f[k]=i;
p[k++]=t;
}
}

void fun1(LL a)
{
LL t;
for(LL i=2;i*i<=a;i++)
{
t=0;
while(a%i == 0)
{
a/=i;
t++;
}
if(t > 0)
Join(i,t);
}
if(a > 1)
Join(a,1);
}

void init()
{
for(LL i=0;i<=500;i++)
{
c[i][0]=c[i][i]=1;
for(LL j=1;j<i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
}
}

LL work()
{//容斥原理
LL temp,ans;
ans=0;
for(LL i=0;i<n;i++)
{
temp=c[n][i];
for(LL j=0;j<k;j++)
temp=(temp*c[n-i+p[j]-1][n-i-1])%MOD;
if(i%2 == 0)
ans=(ans+temp)%MOD;
else
ans=((ans-temp)%MOD+MOD)%MOD;;
}
return ans;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
init();
LL a;
while(scanf("%I64d",&n)!=EOF)
{
k=0;
for(LL i=0;i<n;i++)
{
scanf("%I64d",&a);
fun1(a);
}
printf("%I64d\n",work());
}
return 0;
}



  评论这张
 
阅读(157)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017