About Problem
- The web : http://www.lydsy.com/JudgeOnline/problem.php?id=1005
- The tab : Prufer编码，组合数学
Solve
要完成这道题需要先了解Prufer Sequence。
可以借鉴大牛博客：传送门
大致了解后，题目就变成了：
给你一串数，给出你每个数在Prufer Sequence中出现的次数，-1代表无限制，要你求出所有可能的Prufer Sequence。
于是就变成一道组合数学。
- tot代表所有数的 (d[i] - 1)， cnt代表所有出现次数有限制的数的个数
这个的意思就是把第i个数拆成 d[i] - 1 个相同的数，每个数放进tot个Prufer Sequence里面。
- tot个Prufer Sequence一共有C^tot_(n-2)（看不懂下面有配图）种情况。
C^tot_(n-2)
-
然后第一个Sequence里面有tot个数可以选择，第二个Sequence里面有 tot-1 个数可以选择 …… 以此类推，每个数由于在每个位置上会选择d[i] - 1次，所以会有prod_1^cnt ((d[i-1])!)次重复。
prod_1^cnt ((d[i-1])!) -
所以一共可能的Prufer Sequence有：
然后用高精度，求出答案，就很简单了。
- 代码：
#include <cstdio>
#ifdef _WIN32
#define lld I64d
#endif
typedef long long ll;
const int Maxn = 1010;
int prime[200], num[Maxn][200], d[Maxn], ans[200];
int n, tot = 0, cnt = 0, sum = 0, a[Maxn] = {1, 1};
bool vis[Maxn];
int get_prime()
{
for(int i = 2; i <= 1000; ++i)
{
if(vis[i]) continue;
prime[++prime[0]] = i;
for(int j = 2; i * j <= 1000; ++j) vis[i * j] = true;
}
for(int i = 2; i <= 1000; ++i)
for(int j = 1; j <= prime[0]; ++j)
{
int tmp = i;
while(tmp % prime[j] == 0)
{
++num[i][j];
tmp /= prime[j];
}
}
return prime[0];
}
void add(int x, int k)
{
for(int i = 1; i <= prime[0]; ++i)
ans[i] += x * num[k][i];
return;
}
void cheng(int x)
{
for(int i = 1; i <= a[0]; ++i) a[i] *= x;
for(int i = 1; i <= a[0]; ++i)
if(a[i] >= 10000) a[i + 1] += a[i] / 10000, a[i] %= 10000;
if(a[a[0] + 1]) ++a[0];
return;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("1005.in", "r", stdin);
#endif
scanf("%d", &n);
get_prime();
for(int i = 1; i <= n; ++i)
{
scanf("%d", d + i);
if(d[i] == 0)
{
printf("0\n");
return 0;
}
if(d[i] == -1) ++cnt;
else ++tot, sum += d[i] - 1;
}
// printf("%d\n", sum);
if(sum > n - 2)
{
printf("0\n");
return 0;
}
for(int i = n - 1 - sum; i <= n - 2; ++i) add(1, i);
add(n - 2 - sum, cnt);
for(int i = 1; i <= n; ++i)
if(d[i] != -1)
for(int j = 1; j <= d[i] - 1; ++j) add(-1, j);
for(int i = 1; i <= prime[0]; ++i)
for(int j = 1; j <= ans[i]; ++j) cheng(prime[i]);
printf("%d",a[a[0]]);
for(int i = a[0] - 1; i; --i) printf("%04d",a[i]);
printf("\n");
return 0;
}
