临淄网站建设,哈尔滨软件开发公司排名,企业网站建设的目标,wordpress生产海报图题目 小W最近迷上了日本动漫#xff0c;每天都有无数部动漫的更新等着他去看#xff0c;所以他必须将所有的动漫排个顺序#xff0c;当然#xff0c;虽然有无数部动漫#xff0c;但除了1号动漫#xff0c;每部动漫都有且仅有一部动漫是它的前传#xff08;父亲#xff… 题目 小W最近迷上了日本动漫每天都有无数部动漫的更新等着他去看所以他必须将所有的动漫排个顺序当然虽然有无数部动漫但除了1号动漫每部动漫都有且仅有一部动漫是它的前传父亲也就是说所有的动漫形成一个树形结构。而动漫的顺序必须满足以下两个限制 1、一部动漫的所有后继子孙都必须排在它的后面 2、对于同一部动漫的续集孩子小W喜爱度高的须排在前面。 光排序小W还不爽他想知道一共有多少种排序方案并且输出它mod 10007的答案。 分析 这个题目有两个限制 1、先父亲后儿子2、先大儿子后小儿子。 这个处理起来就很麻烦 于是我们可以转化一下模型 对于限制2因为大儿子一定比小儿子先遍历那么我们可以将小儿子当做前一个比它大的儿子的儿子。 如样例 现在限制就只剩下“先父亲后儿子”即求遍历一棵树当父亲被走过才可以走儿子的方案数。 显然这是一棵二叉树。 设\(f[x]\)表示遍历以x为根的子树的方案数。 转移 设两个儿子分别为ij只有一个儿子的话f[x]就等于儿子的f值以i为根的子树大小为s1j的为s2\[f[x]f[i]*f[j]*C^{min(s1,s2)}_{s1s2}\]C组合求的是插板问题 其实就是当前有s1个点按顺序插入s2个点中。 #include cmath
#include iostream
#include cstdio
#include cstdlib
#include cstring
#include algorithm
#include queue
const int maxlongint2147483647;
const long long mo10007;
const int N1005;
using namespace std;
long long son[N][2],size[N],f[N],jc[N*3],ny[N*3],n,m,T;
long long mi(long long x,long long y)
{long long sum1;while(y) {if(y1) sumsum*x%mo;xx*x%mo;y1;}return sum;
}
long long C(long long mm,long long nn)
{if(nnmm) swap(nn,mm);return jc[mm]*ny[nn]%mo*ny[mm-nn];
}
void dg(int x)
{size[x]1;int json[x][0],kson[x][1];if(j) dg(j);if(k) dg(k);int s1size[j],s2size[k];size[x]s1s2;if(j k) f[x]f[j]%mo*f[k]%mo*C(s1s2,min(s1,s2))%mo;elseif(j) f[x]f[j];else f[x]1;
}
int main()
{jc[0]ny[0]1;for(int i1;i3000;i){jc[i]jc[i-1]*i%mo;ny[i]mi(jc[i],mo-2);}scanf(%lld,T);for(;T--;){memset(son,0,sizeof(son));memset(size,0,sizeof(size));memset(f,0,sizeof(f));f[0]1;scanf(%lld,n);for(int i1;in;i){int lasti,x,k;scanf(%d,k);for(int i1;ik;i){scanf(%d,x);if(!son[last][0]) son[last][0]x;else son[last][1]x;lastx;}}dg(1);printf(%lld\n,f[1]);}
} 转载于:https://www.cnblogs.com/chen1352/p/9071421.html
