Luogu P4099 [HEOI2013]SAO solution

Luogu P4099 [HEOI2013]SAO solution

Title Link: P4099 [HEOI2013]SAO

Meaning:

Welcome to Sao (strange and abnormal online). This is a VR MMORPG containing n n n levels. However, the order of challenging different levels is a big problem.

A game has n − 1 n-1 n − 1 limit for challenge level, such as i i i level must be at j j Challenge before j levels, or complete the k k k levels to challenge the l l 1 level. And, if the directionality of the restriction is not considered, then n − 1 n-1 In the case of n − 1 limit, any two levels have some degree of correlation. That is, we cannot divide all levels into two non empty and disjoint subsets, so that there is no restriction between the two subsets.

High quality questions 👍 Did me all afternoon + evening

First, the meaning of this problem: given a tree with direction, find the total number of topological orders

Noticing this special property, we can solve this problem from the perspective of tree dp

set up d p [ u ] [ i ] dp[u][i] dp[u][i] indicates a node u u u is in the topological order of its subtree i i Number of i-bit schemes

For each u u Son of u v v v. Will v v v constantly merge into u u On u, there are two cases

  • In the new topology order v v v in u u Before u

    Consider enumerating one j j j means v v The subtree of v has j j j nodes merged into u u In front of u

    The new status is d p [ u ] [ i + j ] dp[u][i+j] dp[u][i+j]

    • After consolidation u u u front i + j − 1 i+j-1 i+j − 1 element,

      among j j j yes v v v, so i + j − 1 i+j-1 i+j − 1 grid j j j, then ( i + j − 1 j ) \dbinom{i+j-1}{j} (ji+j−1​)

    • Similarly, u u u there is sz [ u ] + sz [ v ] − i − j \text{sz}[u]+\text{sz}[v]-i-j sz[u]+sz[v] − i − j elements,

      among sz [ v ] − j \text{sz}[v]-j sz[v] − j yes v v v, then ( sz [ u ] + sz [ v ] − i − j sz [ v ] − j ) \dbinom{\text{sz}[u]+\text{sz}[v]-i-j}{\text{sz}[v]-j} (sz[v]−jsz[u]+sz[v]−i−j​)

    So the transfer equation is
    d p [ u ] [ i + j ] = d p [ u ] [ i + j ] + ( i + j − 1 j ) × ( sz [ u ] + sz [ v ] − i − j sz [ v ] − j ) × d p [ u ] [ i ] × d p [ v ] [ k ] dp[u][i+j]=dp[u][i+j]+\dbinom{i+j-1}{j}\times \dbinom{\text{sz}[u]+\text{sz}[v]-i-j}{\text{sz}[v]-j} \times dp[u][i]\times dp[v][k] dp[u][i+j]=dp[u][i+j]+(ji+j−1​)×(sz[v]−jsz[u]+sz[v]−i−j​)×dp[u][i]×dp[v][k]
    that is

    for (int i=1;i<=sz[u];++i)
        for (int k=1;j<=sz[v];++k)
            for (int j=k;j<=sz[v];++j)
                dp[u][i+j]+=dp[u][i]*dp[v][k]*C[i+j-1][i-1]*C[sz[u]+sz[v]-i-j][sz[u]-i]);
    

    Consider a change j , k j,k j. Enumeration order of K

    for (int i=1;i<=sz[u];++i)
        for (int j=1;j<=sz[v];++j)
            for (int k=1;k<=j;++k)
                dp[u][i+j]+=dp[u][i]*dp[v][k]*C[i+j-1][i-1]*C[sz[u]+sz[v]-i-j][sz[u]-i];
    

    Then you can enjoy prefix and optimization!

  • In the new topology order v v v in u u After u

    Similar to the previous case

    for (int i=1;i<=sz[u];++i)
        for (int j=0;j<=sz[v];++j)
            for (int k=i+1;k<=sz[v];++k)
                dp[u][i+j]+=dp[u][i]*dp[v][k]*C[i+j-1][i-1]*C[sz[u]+sz[v]-i-j][sz[u]-i];
    

    You can also prefix and optimize

Then combine numbers O ( n 2 ) O(n^2) O(n2) pretreatment

Note that due to the update of dp[u][i+j], we need to record the old dp[u][i]

So the total time complexity is O ( n 2 ) O(n^2) O(n2) (similar to the complexity proof of knapsack on tree, omitted here)

Don't forget multiple sets of data! qwq

Code:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)
const int p=1e9+7;
struct Edge
{
    int u,v,w,next;
}e[N<<1];
int pos=1,head[N],C[N][N];
int n,sz[N],dp[N][N],tmp[N];
void addEdge(int u,int v,int w)
{
    e[++pos]={u,v,w,head[u]};
    head[u]=pos;
}
void clear()
{
    pos=1;
    for(int i=1; i<=n; i++)
    {
        head[i]=sz[i]=0;
        for(int j=1; j<=n; j++)
            dp[i][j]=0;
    }
}
void dfs(int u,int f)
{
    sz[u]=1;dp[u][1]=1;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==f)continue;
        dfs(v,u);
        for(int i=1; i<=sz[u]; i++)
            tmp[i]=dp[u][i],dp[u][i]=0;
        if(e[i].w)
        {
            for(int i=1; i<=sz[u]; i++)
                for(int j=0; j<sz[v]; j++)
                {
                    dp[u][i+j]=(dp[u][i+j]+C[sz[u]+sz[v]-i-j][sz[v]-j]*
                    C[i+j-1][j]%p*tmp[i]%p*(dp[v][sz[v]]-dp[v][j]+p)%p)%p;
                }
        }else
        {
            for(int i=1; i<=sz[u]; i++)
                for(int j=1; j<=sz[v]; j++)
                {
                    dp[u][i+j]=(dp[u][i+j]+C[sz[u]+sz[v]-i-j][sz[v]-j]*
                    C[i+j-1][j]%p*tmp[i]%p*dp[v][j]%p)%p;
                }
        }
        sz[u]+=sz[v];
    }
    for (int i=1; i<=sz[u]; i++)
        dp[u][i]=(dp[u][i]+dp[u][i-1])%p;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    C[0][0]=1;
    for(int i=1; i<=N-10; i++)
    {
        C[i][0]=1;
        for(int j=1; j<=i; j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
    }
    int Q;cin >> Q;
    while(Q--)
    {
        clear();
        cin >> n;
        for(int i=1,u,v; i<n; i++)
        {
            char ch;cin >> u >> ch >> v;
            ++u;++v;
            addEdge(u,v,ch=='<');
            addEdge(v,u,ch=='>');
        }
        dfs(1,1);
        cout << dp[1][n] << endl;
    }
    return 0;
}

References

[1] https://www.luogu.com.cn/blog/i-am-zhiyangfan/solution-p4099

[2] https://www.luogu.com.cn/blog/ShadowassIIXVIIIIV/solution-p4099

[3] https://m-sea.blog.luogu.org/solution-p4099

Please specify the source for reprint

Tags: Algorithm Dynamic Programming OI

Posted by wizardry on Tue, 31 May 2022 06:32:54 +0530