[JZOJ5165] 小W的动漫

Description

小W最近迷上了日本动漫，每天都有无数部动漫的更新等着他去看，所以他必须将所有的动漫排个顺序，当然，虽然有无数部动漫，但除了1号动漫，每部动漫都有且仅有一部动漫是它的前传（父亲），也就是说，所有的动漫形成一个树形结构。而动漫的顺序必须满足以下两个限制：
1、一部动漫的所有后继（子孙）都必须排在它的后面；
2、对于同一部动漫的续集（孩子），小W喜爱度高的须排在前面。
光排序小W还不爽，他想知道一共有多少种排序方案，并且输出它mod 10007的答案。
30%的数据： n<=10
60%的数据： n<=100
100%的数据： n<=1000

Solution

树形DP

设F[i]表示以i为根的子树的方案。

那么考虑合并。
但是仔细想一想就发现如果直接从大到小合并是不行的，因为后面有多少个可以合并的点不确定，如果加一维转移就会T。

解法一

其实可以倒过来做，从小到大合并。
如果从小到大合并，那么新加进来的子树根一定排在最前面，这样合并的点数就是确定的了。

还有一类涉及的经典问题：
M个空位放N个物品，可以一个空位放多个，也可以什么都不放，求方案数。

答案是CNN+M−1

解法二

也可以将兄弟也看成儿子，利用左儿子右兄弟的办法，将其转换成一棵二叉树，就可以直接做了。

Code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define mo 10007
#define N 1005
#define LL long long
using namespace std;
int son[N][N],n,t,ft[N],sz[N];
LL f[N],js[2*N],ny[2*N];
LL ksm(LL k,LL n)
{
    if(n==0) return 1;
    LL s=ksm(k,n/2);
    return (n%2)?s*s%mo*k%mo:s*s%mo;
}
LL zh(LL n,LL m)
{
    return js[n]*ny[m]%mo*ny[n-m]%mo;
}
void trdp(int k)
{
    sz[k]=0;
    f[k]=1;
    fo(i,1,son[k][0])
    {
        int p=son[k][i];    
        trdp(p);
        (f[k]*=f[p]*zh(sz[k]+sz[p]-1,sz[p]-1))%=mo;
        sz[k]+=sz[p];
    }
    sz[k]++;
}
int main()
{
    cin>>t;
    js[0]=ny[0]=1;
    fo(i,1,2000) js[i]=(js[i-1]*i)%mo,ny[i]=ksm(js[i],mo-2);
    while(t--)
    {
        scanf("%d",&n);
        memset(f,0,sizeof(f));
        fo(i,1,n)
        {
            scanf("%d",&son[i][0]);
            fod(j,son[i][0],1) scanf("%d",&son[i][j]),ft[son[i][j]]=i;
        }
        trdp(1);
        printf("%lld\n",f[1]);
    }
}