Description

Input

Output

Sample Input

5 4
1 < 2
1 < 3
2 < 4
1 = 5

Sample Output

5

Data Constraint

?

首先對于給出的等于條件，我們可以直接把點合并。對于合并后的圖，我們發現要么是環，要么是樹，環則直接無解，樹我們可以用樹形DP處理一下。

我們發現每個序列都被“<”分成了若干塊，我們設f[i][j]為以i為根的樹被分成j塊的方案。每次我們合并兩棵子樹，假設A子樹原有i快，B子樹有j塊，合并后有K快，我們先將A的序列放入，方案數C(k,i)，如果i+j>k那么表示j中有些塊要以等于形式和A合并，方案數C(i,i+j-k)，所以對新答案貢獻為f[A][i]*f[B][j]*C(k,i)*C(i,i+j-k)，這樣轉移即可

?

#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #include<vector> using namespace std; typedef long long ll;vector<int> v[111];int mo=1000000007; int c[111][111],f[111],g[111],next[111],y[111]; int F[111][111],size[111],du[111]; bool vis[111],pz; int n,i,tt,x,z,kn,m,ans,j;void Read() {char c;while(c=getchar(),c!='<'&&c!='=');if(c=='=')kn=1;else kn=0; }int find(int r) {if(f[r]==r)return r;else f[r]=find(f[r]);return f[r]; }void star(int i,int j) {tt++;next[tt]=g[i];g[i]=tt;y[tt]=j; }void dfs(int x) {int j,k;size[x]=1;vis[x]=true;j=g[x];while(j!=0){k=y[j];if(!vis[k]){dfs(k);size[x]+=size[k];}j=next[j];} }void dp(int x) {int j,k,mx[3],i,l,ni,nj,nk,ad;int h[111][3];bool pf;pf=false;memset(mx,0,sizeof(mx));memset(h,0,sizeof(h));j=g[x];while(j!=0){k=y[j];dp(k);j=next[j];if(!pf){pf=true;for(i=0;i<=size[k];i++)h[i][0]=F[k][i];mx[0]=size[k];}else{for(i=0;i<=size[k];i++)h[i][1]=F[k][i];mx[1]=size[k];mx[2]=mx[0]+mx[1];for(i=0;i<=mx[2];i++)h[i][2]=0;for(ni=0;ni<=mx[0];ni++)if(h[ni][0])for(nj=0;nj<=mx[1];nj++)if(h[nj][1])for(nk=min(ni,nj);nk<=ni+nj;nk++){ad=(ll)c[nk][ni]*c[ni][ni+nj-nk]%mo;ad=(ll)ad*h[ni][0]%mo*h[nj][1]%mo;h[nk][2]=(h[nk][2]+ad)%mo;}for(i=0;i<=mx[2];i++)h[i][0]=h[i][2];mx[0]=mx[2];}}if(!g[x])F[x][1]=1;else{for(ni=0;ni<=mx[0];ni++)F[x][ni+1]=h[ni][0];} }int main() {scanf("%d%d",&n,&m);for(i=0;i<=100;i++){c[i][0]=1;c[i][i]=1;}for(i=2;i<=100;i++)for(j=1;j<i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mo;for(i=1;i<=n;i++)f[i]=i;for(i=1;i<=m;i++){scanf("%d",&x);Read();scanf("%d",&z);if(kn==0)v[x].push_back(z);else{x=find(f[x]);z=find(f[z]);f[z]=x;}}for(i=1;i<=n;i++)f[i]=find(f[i]);for(i=1;i<=n;i++){x=i;x=find(f[x]);for(j=0;j<v[i].size();j++){z=find(f[v[i][j]]);star(x,z);du[z]++;}}pz=true;size[n+1]=1;for(i=1;i<=n;i++){if(f[i]==i&&du[i]==0){dfs(i);star(n+1,i);size[n+1]+=size[i];}}for(i=1;i<=n;i++)if(f[i]==i&&!vis[i])pz=false;if(pz==false)printf("0\n");else{dp(n+1);for(i=1;i<=size[n+1]+1;i++)ans=(ans+F[n+1][i])%mo;printf("%d\n",ans);} }

?

轉載于:https://www.cnblogs.com/applejxt/p/4466911.html

總結

以上是生活随笔為你收集整理的HNOI2015 实验比较的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。