HDU4390Number Sequence(容斥原理)

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4390

题意：

有一个长度为n的序列，b1,b2,b3,,,,,bn;

寻找一个长度也为n的序列 使得满足以下条件

1） a1*a2*...*an=b1*b2*...*bn;

2)ai>1;

分析：

很明显就是把bi的所有素因子统计以下，然后重新组合分成n份。

我们先回顾以下一个子问题。

把m个相同的球分到n个不相同的容器里，每个容器能为空。

挡板法：

  ans = C(n+m-1,n-1);

然后我们就来了思路了 因为ai大于1，说明不能为空。我们可以从反面

来考虑，先求出一共所有的方案数num1，然后再通过容斥原理来求出，至少

存在一个为空的方案数num2。

ans = num1 - num2.

代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;

const int maxn=1005;
const int MOD=1000000007;
int p[maxn];
int a[maxn];
LL c[maxn][maxn];

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

int getnum(int m,int n){
	return c[m+n-1][n-1];
}

LL solve(int cnt,int n){
	int i,j;
	LL ans=1;
	for(i=0;i<=cnt;i++)
		ans=(ans*getnum(a[i],n))%MOD;
	for(i=1;i<n;i++)
	{
		LL tmp=c[n][i];
		for(j=0;j<=cnt;j++)
			tmp=(tmp*getnum(a[j],n-i))%MOD;
		if(i&1)
			ans=((ans-tmp)%MOD+MOD)%MOD;
		else
			ans=(ans+tmp)%MOD;
	}
	return ans;
}

int main()
{
	init();
	int n;
	while(~scanf("%d",&n))
	{
		int t,i,j;
		int cnt=0;
		for(i=0;i<n;i++){
			scanf("%d",&t);
			for(j=2;j*j<=t;j++){
				while(t%j==0){
					p[cnt++]=j;
					t/=j;
				}
			}
			if(t>1)
				p[cnt++]=t;
		}
		sort(p,p+cnt);
		a[0]=1;
		i=0;
		for(j=1;j<cnt;j++){
			if(p[j]==p[j-1])
				a[i]++;
			else
				a[++i]=1;
		}
		cnt=i;
		printf("%I64d\n",solve(cnt,n));
	}
	return 0;
}

HDU4390Number Sequence(容斥原理)

原文：http://blog.csdn.net/bigbigship/article/details/44567445