rockdu
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 121 Accepted Submission(s): 59
Problem Description
Clarke is a patient with multiple personality disorder. One day, Clarke turned into a CS, did a research on data structure.
Now Clarke has n nodes, he knows the degree of each node no more than ai. He wants to know the number of ways to choose some nodes to compose to a tree of size s(1≤s≤n).
Now Clarke has n nodes, he knows the degree of each node no more than ai. He wants to know the number of ways to choose some nodes to compose to a tree of size s(1≤s≤n).
Input
The first line contains one integer T(1≤T≤10), the number of test cases.
For each test case:
The first line contains an integer n(2≤n≤50).
Then a new line follow with n numbers. The ith number ai(1≤ai<n) denotes the number that the degree of the ith node must no more than ai.
For each test case:
The first line contains an integer n(2≤n≤50).
Then a new line follow with n numbers. The ith number ai(1≤ai<n) denotes the number that the degree of the ith node must no more than ai.
Output
For each test case, print a line with n integers. The ith number denotes the number of trees of size i modulo 109+7.
Sample Input
1 3 2 2 1
Sample Output
3 3 2 Hint: At first we know the degree of node 1 can not more than 2, node 2 can not more than 2, node 3 can not more than 1. So For the trees of size 1, we have tree ways to compose, are 1, 2 and 3. i.e. a tree with one node. For the trees of size 2, we have tree ways to compose, are 1-2, 1-3, 2-3. For the trees of size 3, we have two ways to compose, are 1-2-3, 2-1-3.
Source
题目大意是有 n 个点，第 i 个点的限制为度数不能超过 ai。 现在对于每一个 s(1<=s<=n)，问从这 n 个点中选出 s 个点组成有标号无根 树的方案数。因为要考虑有标号无根树的问题，想到prufer序列。如果用dp[i][j][k]表示现在处理到i节点，已经选了j个节点（在prufer序列中填充），prufer序列长度为k，那么我们就可以枚举当前j在prufer序列中出现的次数组合一下。就可以DP了
#include<cstdio>
#include<cstring>
#include<algorithm>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
#define LL unsigned long long
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e2 + 5;
LL dp[maxn][maxn][maxn], step[maxn], inv[maxn];
int n, a[maxn], t;
LL fpow(LL a, LL b, int p) {
LL ans = 1;
while(b) {
if(b & 1) ans = ans * a % p;
a = a * a % p, b >>= 1;
}
return ans;
}
int main() {
scanf("%d", &t);
step[0] = inv[0] = 1;
For(i, 1, 100) step[i] = step[i - 1] * i % mod, inv[i] = fpow(step[i], mod - 2, mod);
while(t--) {
memset(dp, 0, sizeof(dp));
scanf("%d", &n);
For(i, 1, n) scanf("%d", &a[i]);
dp[0][0][0] = 1;
For(i, 0, n - 1) For(j, 0, i) For(k, 0, n)
if(dp[i][j][k]){
dp[i + 1][j][k] = (dp[i][j][k] + dp[i + 1][j][k]) % mod;
int tmp = min(n - k, a[i + 1] - 1);
For(l, 0, tmp)
dp[i + 1][j + 1][k + l] = (dp[i + 1][j + 1][k + l] + dp[i][j][k] * inv[l]) % mod;
}
printf("%d", n);
For(i, 2, n)
printf(" %lld", (dp[n][i][i - 2] * step[i - 2]) % mod);
putchar('\n');
}
return 0;
}
没有帐号? 立即注册