本文共 3940 字，大约阅读时间需要 13 分钟。
这题真是极好的。
首先，用并查集合并相等的点，并用并查集的根作为代表的点。
然后dfs一次，看一下有没有环，如有环，那么无解，直接输出0。
我们发现图其实是一个由一些有根树组成的森林。为了方便计算，我们新建一个虚拟根，然后所有有根树的根都指向这个根，那么现在原图就变成一棵树了。
用树形DP。
记$f[i][j]$表示以$i$为根的子树，构成长度为$j$的序列的方案数。
那么怎么合并子树呢？
假设点$x$有两个儿子$u$和$v$。
假设子树$u$形成了长度为$j$的序列，子树$v$形成了长度为$k$的序列，两个序列合并后，形成的新的序列的长度为$p$。
我们考虑在子树$u$形成的长度为$j$的序列的基础上，加入$k$个点。
我们发现，有$p-j$个点是插入在$j+1$个缝隙中的（同一个缝隙可插多个），有$C_{j+1+p-j-1}^{p-j}$中方案；有$k-(p-j)$个点是与原序列的$i$个点合并的，有$C_{j}^{k-(p-j)}$种方案。
所以$f[x][p+1]+=C_{j+1+p-j-1}^{p-j}*C_{i}^{k-(p-j)}*f[u][j]*f[v][k]$
注意还要在前面加上$x$这个点，所以序列的长度是$p+1$。
如果有多个儿子，类似做法即可。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include 适用于CF,UOJ，但不适用于poj using namespace std;typedef long long LL;typedef double DB;typedef pair PII;typedef complex CP;#define mmst(a,v) memset(a,v,sizeof(a))#define mmcy(a,b) memcpy(a,b,sizeof(a))#define fill(a,l,r,v) fill(a+l,a+r+1,v)#define re(i,a,b) for(i=(a);i<=(b);i++)#define red(i,a,b) for(i=(a);i>=(b);i--)#define ire(i,x) for(typedef(x.begin()) i=x.begin();i!=x.end();i++)#define fi first#define se second#define m_p(a,b) make_pair(a,b)#define p_b(a) push_back(a)#define SF scanf#define PF printf#define two(k) (1<<(k))template inline T sqr(T x){ return x*x;}template inline void upmin(T &t,T tmp){ if(t>tmp)t=tmp;}template inline void upmax(T &t,T tmp){ if(t 0)?1:-1;}const DB Pi=acos(-1.0);int gint() { int res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; }LL gll() { LL res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; }const int maxn=100;const LL MOD=1000000007;int n,m;int pa[maxn+10];int getrt(int a){ return (pa[a]<0)?a:pa[a]=getrt(pa[a]);}void uni(int a,int b) { int f1=getrt(a),f2=getrt(b); if(f1==f2)return; if(pa[f1]>pa[f2])swap(f1,f2); pa[f1]+=pa[f2]; pa[f2]=f1; }int fa[maxn+10];int now,info[maxn+10];struct Tedge{ int v,next;}edge[maxn+10];int sz[maxn+10];void addedge(int u,int v){edge[++now]=(Tedge){v,info[u]};info[u]=now;}int flag,vis[maxn+10];void dfs(int u) { if(flag)return; vis[u]=1;sz[u]=1; int i,v; for(i=info[u],v=edge[i].v;i!=-1;i=edge[i].next,v=edge[i].v)if(vis[v]){flag=1;return;}else{dfs(v);sz[u]+=sz[v];} }LL C[2*maxn+20][2*maxn+20];LL f[maxn+20][maxn+20],tmpf[maxn+20][maxn+20];LL ans;void dp(int u) { if(info[u]==-1){f[u][1]=1;return;} int i,v,j,k,p,all=0,ty=0; for(i=info[u],v=edge[i].v;i!=-1;i=edge[i].next,v=edge[i].v) { dp(v); if(ty==0){re(j,1,sz[v])f[u][j]=f[v][j];all+=sz[v];ty=1;continue;} re(j,1,all+sz[v])tmpf[u][j]=0; re(j,1,all)if(f[u][j]!=0)re(k,1,sz[v])if(f[v][k]!=0)re(p,j,j+k)(tmpf[u][p]+=C[j+1+p-j-1][p-j]*C[j][k-(p-j)]%MOD*f[u][j]%MOD*f[v][k]%MOD)%=MOD; re(j,1,all+sz[v])f[u][j]=tmpf[u][j]; all+=sz[v]; } red(j,all+1,2)f[u][j]=f[u][j-1];f[u][1]=0; }int x[maxn+10],y[maxn+10];char t[maxn+10];int bak[maxn+10][maxn+10];int main() { freopen("bzoj4013.in","r",stdin); freopen("bzoj4013.out","w",stdout); int i,j,k,l; n=gint();m=gint(); mmst(pa,-1); re(i,1,m) { SF("%d %c %d\n",&x[i],&t[i],&y[i]); if(t[i]=='=')uni(x[i],y[i]); } now=-1;mmst(info,-1); re(i,1,m)if(t[i]=='<') { int u=getrt(x[i]),v=getrt(y[i]); if(!bak[u][v])addedge(u,v),bak[u][v]=1,fa[v]=u; } re(i,1,n)if(i==getrt(i) && !fa[i])addedge(0,i); re(i,0,n)if(i==getrt(i) && !vis[i]) { dfs(i); if(flag){PF("0\n");return 0;} } C[0][0]=1; re(i,1,2*n+10){C[i][0]=1;re(j,1,2*n+10)C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;} dp(0); re(i,1,sz[0])(ans+=f[0][i])%=MOD; cout< <
转载于:https://www.cnblogs.com/maijing/p/4989821.html
