题面传送门 （好像要权限？再放个luogu的传送门）
首先，n-1条限制，n个关卡，两两之间都存在关联，是不是明白了什么?
就是一棵树嘛（跑图论的dalao https://www.cnblogs.com/fanyujun/ orz orz）
好的，可以开始想树形dp了。先看题，相当于求拓扑序方案数，那么，dp[i][j]表示处理到第i个点，它在拓扑序中的位置是j。嗯，完美地表示了出来。该想想怎么转移了。五分钟后。嗯，不可做题，puts("AFO")。
好吧，我们来考虑下他还给了些什么。对于i号节点，设它的子节点为y，那么如果已知边是i<y，即先打过i才能去打y，那么i的拓扑序必在y前，反之则在y之后。
那么，按照树形dp套路，我们可以先处理出子节点信息（比如，子树里的拓扑序方案数）。那么，我们现在要做的就是把子树里的合并到i节点中。如果i在y前，现在求解dp[i][k]（设目前它前面有k-1个，它在第k个），目前处理了这一棵子树，该怎么合并上去？dp[y][l]表示y前有l个数，且l>k（因为j在i前面啊），那么有dp[i][k]=(1<=x<=min(k,size[i]))(k-x+1<=j<=size[y]) dp[i][x]*c[x-1][k-1]*c[size[i]-x][size[i]+size[y]-k]*dp[y][j]种选择（好吧我承认复制粘贴的，摘自一位dalao博客，在下手残，手打容易出锅，，）。意思是i前有k个数，可以从i前有x个数（x<=k且x<=size[i]）转移过来（方案数为dp[i][x]），因为相当于向前面k-1个位置选出原来x-1个位置放原来在i前的（因为它自己原来在第x位，前面有x-1位，现在前面有k-1位），剩下的位置还有size[i]+size[y]-k个（不算i自身，且现在还没有把size[i]加上size[y]），从中选出size[i]-x个位置填上以前的，再乘上y自己在第j位的方案数（就相当于不考虑插进来的数的变化了，看前面填的都是j这棵子树加入前的数的变化），然后就解决了i在y前的问题了。i在y后方案类似，在此不多加赘述。
但是，，好像有什么地方不对？n^4的时间复杂度！！黄花菜都凉了。
不过，，观察方程，好像只有最后的dp[y][j]与j相关诶。那就好办了，乘法分配律一提，就成了dp[i][k]=(1<=x<=min(k,size[i]))dp[i][x]*c[x-1][k-1]*c[size[i]-x][size[i]+size[y]-k]*（dp[y][k-x+1]+...+dp[y][size[y]]）。相信聪明的各位都已经猜到了，预处理出前缀和，就成了dp[i][k]=(1<=x<=min(k,size[i]))dp[i][x]*c[x-1][k-1]*c[size[i]-x][size[i]+size[y]-k]*（sum[y][size[y]]-sum[y][k-x]）。好的，看起来可以卡过了。
在下代码写法有些丑，希望不要在意
//听说本题用long long会超时？反正开unsigned long long 在洛谷上比long long 总共快了1300ms+ （可能是在下代码比较丑的缘故） #include<bits/stdc++.h> #include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #include<deque> #include<list> #include<set> #include<vector> #include<iostream> #define ll long long #define ull unsigned long long #define uint unsigned int #define re register #define inf 0x3f3f3f3f #define inl inline #define sqr(x) (x*x) //#define eps 1e-8 #define debug printf("debug\n"); //#pragma comment(linker, "/STACK:1024000000,1024000000") //#pragma GCC optimize (2) //#pragma G++ optimize (2) using namespace std; const ull mod=1e9+7; const ull MAXN=1e3+10; inl ull read() { re ull x = 0; re int f = 1; char ch = getchar(); while(ch<'0'||ch>'9') { if(ch== '-' ) f = -1; ch = getchar(); } while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x * f; } inl char readc() { char ch=getchar(); while(ch!='>'&&ch!='<') ch=getchar(); return ch; } inl void write(re ull x){ if(x>=10)write(x/10); putchar(x%10+'0'); } inl void writeln(re ull x){ if(x<0) {x=-x;putchar('-');} write(x); puts(""); } inl ull gcd(re ull x,re ull y){while(y^=x^=y^=x%=y);return x;} inl void FR() { freopen(".in","r",stdin); freopen(".out","w",stdout); } inl void FC() { fclose(stdin); fclose(stdout); }//不要在意那么多头文件 struct Node { ull u,v,w,nxt; }e[MAXN<<1]; ull cnt,head[MAXN],size[MAXN]; ull c_fyj[MAXN][MAXN],n;//听说在数组后面加上_dalao名字 有分数加成? ull sum[MAXN][MAXN],dp[MAXN][MAXN]; inl void adde(ull u,ull v,ull w) { e[++cnt].u=u;e[cnt].v=v,e[cnt].w=w; e[cnt].nxt=head[u];head[u]=cnt; } inl void init() { cnt=0; for(re ull i=0;i<=n;i++) { head[i]=size[i]=0; for(re ull j=0;j<=n;j++) { sum[i][j]=dp[i][j]=0; } } } void dfs(re ull x,re ull fa) { dp[x][1]=size[x]=1; for(re ull h=head[x];h;h=e[h].nxt) { if(e[h].v==fa) continue ; dfs(e[h].v,x); if(e[h].w==1) {//如果x在e[h].v前 for(re ull k=size[x]+size[e[h].v];k;k--) { re ull ssum=0; for(re ull i=1;i<=min(k,size[x]);i++) { ull d=(sum[e[h].v][size[e[h].v]]-sum[e[h].v][k-i]+mod)%mod; ull q=(dp[x][i]*d)%mod,p=(c_fyj[i-1][k-1]*c_fyj[size[x]-i][size[x]+size[e[h].v]-k])%mod; ssum=(ssum+(p*q%mod))%mod; } dp[x][k]=ssum; } } else { for(re ull k=size[x]+size[e[h].v];k;k--) { re ull ssum=0; for(re ull i=1;i<=min(k-1,size[x]);i++) { ull d=sum[e[h].v][min(size[e[h].v],k-i)]%mod; ull q=(dp[x][i]*d)%mod,p=(c_fyj[i-1][k-1]*c_fyj[size[x]-i][size[x]+size[e[h].v]-k])%mod; ssum=(ssum+((p*q)%mod))%mod; } dp[x][k]=ssum; } } size[x]+=size[e[h].v]; } for(re ull i=1;i<=size[x];i++) sum[x][i]=(sum[x][i-1]+dp[x][i])%mod;//预处理出前缀和 } int main(){ // FR(); c_fyj[0][0]=1; for(re ull i=1;i<=1005;i++) { c_fyj[0][i]=1; for(re ull j=1;j<=i;j++) { c_fyj[j][i]=(c_fyj[j][i-1]+c_fyj[j-1][i-1])%mod; } }//组合数 re int T=read(); while(T--) { init();//多组数据 n=read(); for(re ull i=1;i<n;i++) { re ull u=read()+1;//处理成从1开始的 char x=readc();//跟FYJ dalao 学的骚操作 re ull v=read()+1; if(x=='<') {adde(u,v,1);adde(v,u,-1);}//双向边，u先于v为1，反之为-1 else if(x=='>') {adde(u,v,-1);adde(v,u,1);} else puts("RE");//单纯地检查一下写错了没 } ull ans=0; dfs(1,-1); for(re ull i=1;i<=size[1];i++) { ans=(ans+dp[1][i])%mod; } writeln(ans); } // FC(); return 0; }
转载于:https://www.cnblogs.com/20020723YJX/p/9351498.html
