不愧是神场,据传Div.2E做出了TC Div.1 1000的赶脚,而这题做到了.

题意

问有多少张符合下列条件的无向图: 1.每个点的度都是固定的,为2或者3. 2.每一个点到1号点的最短路有且只有一条. 3.令i为1->n-1中的任意一个点,必须满足i到1的最短路小于或者等于i+1到1的最短路.
你在路上如果真的能够遇到八九寺真宵,那你可能也是个怪人了.
$n\le 50$,如果考虑dp的话想怎么搞就怎么搞.
因为这场的数据范围小得惊人,据出题人说每题都可能有3种解法.
首先由于图的性质3,我们不妨把该图当成有向图,显然边只可能从编号小的点连向编号大的.
根据到$1$号点的距离,我们把点分成很多层.
考虑开两个dp数组$dp$和$f$.
dp[i][j][k]表示当前层有i个点,前一层有j个点度数为2,k个点度数为3的方法总数.
$dp[0][0][0]=1.$
当$i=0$,$j=0$的时候,显然能够从dp[0][2][k-3]转移过来,连接2个度为$2$的点,有$(k-1)(k-2)$种连法.
当$i=0$的时候,有两种可能,连接两个度为$1$的点或者连接度为$1$和度为$2$的点,分别从dp[0][j-2][k]*(j-1)和dp[0][j][k-1]*k转移过来.
而$i$不为$0$的时候,可以连接当前点和某个度数为$1$或者$2$的点,转移方法就不说了.
f[i][j]表示共n-i+1个点,和第i个点在同一层的点有j个的方法总数.
然后枚举$i,j$,枚举和第$j$个点在同一层的点的个数$k$.
$f[i][j]=f[j+1][k]\times dp[k-j][cnt2][cnt3]$,$cnt2$和$cnt3$分别是到从$n-i+2$到第$j$个点有的度数为$2$和$3$的点的个数.
答案已经出来了.谢谢大家.

#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
template <typename mitsuha>
inline bool read(mitsuha &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return 0&pc(48);
  if (x<0) x=-x,pc('-');
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
const int mod=1e9+7;
ll dp[55][55][55],f[55][55],a[55];

ll dfs(int i,int j,int k){
if (j<0||k<0) return 0;
if (~dp[i][j][k]) return dp[i][j][k];
ll ans;
if (i) ans=j*dfs(i-1,j-1,k)+k*dfs(i-1,j+1,k-1);
else if (j) ans=(j-1)*dfs(0,j-2,k)+k*dfs(0,j,k-1);
else ans=(k-1)*(k-2)/2*dfs(0,2,k-3);
return dp[i][j][k]=ans%mod;
}

int main(){
int n=read(),i,j,k;
for (i=1;i<=n;++i) a[i]=read();
memset(dp,-1,sizeof dp);
f[n+1][n]=dp[0][0][0]=1;
for (i=n;i>1;--i){
  int cnt2=0,cnt3=0;
  for (j=i;j<=n;++j){
    cnt2+=a[j]==2,cnt3+=a[j]==3;
    for (k=j;k<=n;++k) f[i][j]=(f[i][j]+f[j+1][k]*dfs(k-j,cnt2,cnt3))%mod;
    }
  }write(f[2][a[1]+1]);
}