Article From:https://www.cnblogs.com/twilight-sx/p/9216853.html

  I suggest that we should not read this article, because I feel that my solution is not efficient and graceful. Just want to record, after all, apart from Chinese chess, I made the first question of composition DP.

  First of all, if you do a lot of work and be more proficient, you should be able to see that the information given in this question is exactly the size of a father and son on a two fork tree. So we establish a state (f[u][i]\) in the subtree of (u\) and (u\) (u\).) the total number of plans for ranking I. (this state should still be well thought, I thought at that time that this state felt that I could do it and insisted on this state). Then consider how to transfer it through (f[ch1][j], f[ch2][k]\), that is, its two sons.The current state.

  We can notice that from the son to the father, the two sons are not interrelated, so long as they are satisfied with the size of the father. When j\ is the son and father, it means that the father has at least reserved (j\) vacancies in front of him.When the son of j\ is larger than his father, it shows that his father’s rankings should not exceed the limit so that the gap is less than (size2 – j + 1\). Let (S\) be the number of ranks (&lt, I…) in the right son tree.One way of thinking is to get the size of S\.

  There is a combinatorial number transfer equation: (ANS = f[ch1][j] * f[ch2][k] * C[i – 1][S] * C[size[u]][size[ch2] – S]\); the code is too smelly to bear in mind.

#include <bits/stdc++.h>
using namespace std;
#define maxn 400
#define int long long
#define mod 1000000007
int n, f[maxn][maxn], size[maxn];
int C[maxn][maxn], a[maxn]; 

int read()
{
    int x = 0, k = 1;
    char c;
    c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

void Get_C()
{
    for(int i = 0;i < maxn; i++)
            C[i][0] = 1, C[i][i] = 1;
    for(int i = 1; i < maxn; i++)
        for(int j = 1; j < i; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}

void DP(int u)
{
    int ch1 = u * 2, ch2 = u * 2 + 1;
    for(int i = 1; i <= size[u]; i ++)
        for(int j = 1; j <= size[ch1]; j ++)
            for(int k = 1; k <= size[ch2]; k ++)
            {
                int tem = f[ch1][j] * f[ch2][k] % mod;
                int l1 = size[ch1] - j + 1, l2 = size[ch2] - k + 1;
                if(a[ch1] && a[ch2])
                {
                    if(i <= j + k) continue;
                    int minn = max(k, max(size[ch2] - (size[u] - i), i - size[ch1] - 1));
                    int maxx = min(i - j - 1, size[ch2]);
                    for(int S = minn; S <= maxx; S ++)
                    {
                        int tt = tem * C[i - 1][S] % mod * C[size[u] - i][size[ch2] - S] % mod;
                        f[u][i] = (f[u][i] + tt) % mod;
                    }
                }
                else if(a[ch1] || a[ch2])
                {
                    int x = j, y = k, p = ch1, q = ch2;
                    if(a[ch2]) swap(j, k), swap(ch1, ch2);
                    int l1 = size[ch1] - j + 1, l2 = size[ch2] - k + 1;
                    if(i <= j || i > size[u] - l2) { j = x, k = y, ch1 = p, ch2 = q; continue; }
                    int minn = max(i - 1 - size[ch1], 0ll);
                    int maxx = min(i - 1 - j, size[ch2] - l2);
                    for(int S = minn; S <= maxx; S ++)
                    {
                        int tt = tem * C[i - 1][S] % mod * C[size[u] - i][size[ch2] - S] % mod;
                        f[u][i] = (f[u][i] + tt) % mod;
                    }
                    j = x, k = y, ch1 = p, ch2 = q;
                }
                else
                {
                    int z = size[u] - i;
                    if(i > size[u] - l1 - l2) continue;
                    int minn = max(size[ch2] - (z - l1), 0ll);
                    int maxx = min(size[ch2] - l2, size[u] - z + l2 - 1);
                    for(int S = minn; S <= maxx; S ++)
                    {
                        int tt = tem * C[i - 1][S] % mod * C[size[u] - i][size[ch2] - S] % mod;
                        f[u][i] = (f[u][i] + tt) % mod;
                    }
                }
            } 
}

void dfs(int u)
{
    if(u > n) return;
    dfs(u * 2); dfs(u * 2 + 1);
    if(u * 2 > n && u * 2 + 1 > n)
    {
        f[u][1] = 1; size[u] = 1;
        return; 
    }
    int ch1 = u * 2, ch2 = u * 2 + 1;
    size[u] = size[ch1] + size[ch2] + 1;
    if(ch2 <= n) DP(u);
    else 
    {
        for(int i = 1; i <= size[u]; i ++)
            for(int j = 1; j <= size[ch1]; j ++)
            {
                if(a[ch1])
                {
                    if(j >= i) continue;
                    f[u][i] = (f[u][i] + f[ch1][j]) % mod; 
                }
                else 
                {
                    int p = size[ch1] - j + 1, z = size[u] - i;
                    if(z < p) continue;
                    f[u][i] = (f[u][i] + f[ch1][j]) % mod;
                }
            }
    } 
}

signed main()
{
    Get_C();
    n = read();
    for(int i = 2; i <= n; i ++)
    {
        char c; cin >> c;
        if(c == '>') a[i] = 1; 
    } 
    dfs(1); int ans = 0;
    for(int i = 1; i <= n; i ++) 
        ans = (ans + f[1][i]) % mod;
    printf("%lld\n", ans);
    return 0;
}

 

Link of this Article: The keyboard of CQOI2017 old C

Leave a Reply

Your email address will not be published. Required fields are marked *