解题：HEOI 2013 SAO

不好讲，直接上式子吧=。=

设$dp[i][j]$表示考虑完$i$的子树后$i$的排名为$j$的方案数，然后转移类似树形背包，具体来说是(这里假设子树在$i$后选，其实反过来还用这个式子答案也是一样的，因为全反了)

$ans+=dp[nde][k]*dp[g][min(j-k,siz[g])]*C_{j-1}^{k-1}*C_{siz[nde]+siz[g]-j}^{siz[nde]-k}$

其中$j$是枚举的当前点加入$i$这个子树之后$i$前面总共有几个数，$k$是枚举的当前点加入这个子树之后$i$前面还有几个原来是$i$的，$g$是子树，解释一下

前两个是已有的信息，不解释了，$C_{j-1}^{k-1}$表示$i$已经有的这$k$个点随便排(原有顺序还要保持不变，所以是C)，后面那个$C_{siz[nde]+siz[g]-j}^{siz[nde]-k}$同理

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,mod=1e9+;

 int fac[N],inv[N],siz[N],f[N][N];

 int p[N],noww[*N],goal[*N],val[*N];

 int T,n,t1,t2,cnt; char rd[];

 void Link(int f,int t,int v)

 {

     noww[++cnt]=p[f],p[f]=cnt;

     goal[cnt]=t,val[cnt]=v;

 }

 int Qpow(int x,int k)

 {

     if(k==) return x;

     int tmp=Qpow(x,k/);

     return k%?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod;

 }

 int C(int a,int b)

 {

     if(a<b) return ;

     return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;

 }

 void Prework()

 {

     fac[]=inv[]=;

     for(int i=;i<=;i++)

         fac[i]=1ll*fac[i-]*i%mod;

     inv[]=Qpow(fac[],mod-);

     for(int i=;i;i--)

         inv[i]=1ll*inv[i+]*(i+)%mod;

     scanf("%d",&T);

 }

 void Init()

 {

     memset(p,,sizeof p);

     memset(f,,sizeof f);

     cnt=,scanf("%d",&n);

     for(int i=;i<n;i++)

     {

         scanf("%d%s%d",&t1,rd,&t2),t1++,t2++;

         Link(t1,t2,rd[]=='<'),Link(t2,t1,rd[]=='>');

     }

     for(int i=;i<=n;i++) f[i][]=;

 }

 void DFS(int nde,int fth)

 {

     siz[nde]=;

     for(int i=p[nde];i;i=noww[i])

     {

         int g=goal[i];

         if(g!=fth)

         {

             DFS(g,nde);

             if(val[i])

             {

                 for(int j=siz[nde]+siz[g];j;j--)

                 {

                     int tmp=;

                     for(int k=;k<=min(j,siz[nde]);k++)

                         if(j-k+<=siz[g])

                             tmp+=1ll*f[nde][k]*(f[g][siz[g]]-f[g][j-k]+mod)%mod*C(j-,k-)%mod*C(siz[nde]+siz[g]-j,siz[nde]-k)%mod,tmp%=mod;

                     f[nde][j]=tmp;

                 }

             }

             else

             {

                 for(int j=siz[nde]+siz[g];j;j--)

                 {

                     int tmp=;

                     for(int k=;k<=min(j,siz[nde]);k++)

                         if(min(j-k,siz[g])>=)

                             tmp+=1ll*f[nde][k]*f[g][min(j-k,siz[g])]%mod*C(j-,k-)%mod*C(siz[nde]+siz[g]-j,siz[nde]-k)%mod,tmp%=mod;

                     f[nde][j]=tmp;

                 }

             }

             siz[nde]+=siz[g];

         }

     }

     for(int i=;i<=siz[nde];i++)

         f[nde][i]=(f[nde][i]+f[nde][i-])%mod;

 }

 int main()

 {

     Prework();

     while(T--)

         Init(),DFS(,),printf("%d\n",f[][n]);

     return ;

 }

巴特西

解题：HEOI 2013 SAO

最新文章

热门文章