当前位置:码农谷 > 算法与程序 > HDU 4955 Tree:题目解答源码

HDU 4955 Tree:题目解答源码

所属学科:C语言 - 函数 难度: 关注度:373

Teacher Mai has a directed graph with n nodes and n edges. This graph is special: Out degree of each node is 1, and there is no self loop.      
For every node Teacher Mai wrote down a set of nodes which directly links to this node.      
For example, the graph contains 4 edges: {1->2,2->4,3->1,4->1}, the set of each node is {3,4},{1},{},{2}      
But Teacher Mai found that he forgot writing which node the set belonged to.      
Teacher Mai wanted to recover it, but he found there are many graphs with the same node sets.      
You should count the number of different graphs have the same node sets as the given one.      
The number can be very large, just output the number modulo 1000000007 (10^9+7).      
If there is no solution, the answer is 0.

输入描述

There are multiple test cases, terminated by a line "0".        For each test case, the first line contains a integer n (1<=n<=1000).        The following are n lines representing the set of each node. For every line,  there is a integer p first, indicating the size of the set. Then there are p integers,  indicating the node with index from 1 to n in this set.

输出描述

For each test case, output one line "Case #k: ans", where k is the case number, counting from 1, ans is the number module 10^9+7.

程序源码

完整的源代码如下

using namespace std;
typedef long long ll;
const int maxn=1005;
const int mod=1000000007;

int a[maxn],n;
bool vis[maxn];
ll c[maxn][maxn],b[maxn][maxn];
ll f[maxn][maxn];

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

关注微信,获得更多免费资源
关于我们   |   免责声明   |   联系我们   |   网站地图   |   HR交流群   |   学生交流群   |   教师交流群

码农谷   版权所有 © 2015-2017   湘ICP备16018319号-1