NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. 题目描述
  2. 2. 输入格式
  3. 3. 输出格式
  4. 4. 样例输入
  5. 5. 样例输出
  • 题解
  • 题目描述

    WelcometoSAO(StrangeandAbnormalOnline)。这是一个VRMMORPG,含有n个关卡。但是,挑战不同关卡的顺序是一
    个很大的问题。有n–1个对于挑战关卡的限制,诸如第i个关卡必须在第j个关卡前挑战,或者完成了第k个关卡才
    能挑战第l个关卡。并且,如果不考虑限制的方向性,那么在这n–1个限制的情况下,任何两个关卡都存在某种程
    度的关联性。即,我们不能把所有关卡分成两个非空且不相交的子集,使得这两个子集之间没有任何限制。

    输入格式

    第一行,一个整数T,表示数据组数。对于每组数据,第一行一个整数n,表示关卡数。接下来n–1行,每行为“i
    sign j”,其中$0≤i,j≤n–1$且$i≠j$,sign为“<”或者“>”,表示第i个关卡必须在第j个关卡前/后完成。
    $T≤5, 1≤n≤1000$

    输出格式

    对于每个数据,输出一行一个整数,为攻克关卡的顺序方案个数,mod1,000,000,007输出。

    样例输入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    5
    10
    5 > 8
    5 > 6
    0 < 1
    9 < 4
    2 > 5
    5 < 9
    8 < 1
    9 > 3
    1 < 7
    10
    6 > 7
    2 > 0
    9 < 0
    5 > 9
    7 > 0
    0 > 3
    7 < 8
    1 < 2
    0 < 4
    10
    2 < 0
    1 > 4
    0 > 5
    9 < 0
    9 > 3
    1 < 2
    4 > 6
    9 < 8
    7 > 1
    10
    0 > 9
    5 > 6
    3 > 6
    8 < 7
    8 > 4
    0 > 6
    8 > 5
    8 < 2
    1 > 8
    10
    8 < 3
    8 < 4
    1 > 3
    1 < 9
    3 < 7
    2 < 8
    5 > 2
    5 < 6
    0 < 9

    样例输出

    1
    2
    3
    4
    5
    2580
    3960
    1834
    5208
    3336

    题解

    先做了ALO, 又做了SAO。
    然后就突然想看刀剑了, 虽然看来好几遍了, 不过河北的省选真会玩儿。
    什么时候来个GGO就好了。


    回到这道题:

    首先将本题转化为一个树上问题(这tm的不是显然吗)。
    然后我们发现答案只与每对点的遍历数序有关。
    那么我们定义$f[i][j]$为一$i$为根节点的子树中有$j$个比他小。
    那么假设$i$的子节点$u$要求小于$i$
    那么以$u$为根的子树中有可能有$[0, k - 1]$ 个数比$u$小
    那么在考虑小于他的数的合并顺序,
    由插板法得$C_{j}^{k}$
    同理小于它的为$C_{size[i] + size[u] - j - 1}^{size[u] - k}$
    综上转移方程为
    $$f[i][j + k] = f[i][j] * \sum_{c=0}^{k-1}{f[u][c]} * C_{j + k}^{j} * C_{size[u] + size[i] - k - j - 1}^{size[u] - k}$$
    大于与此类似

    不知道为什么数组越界过来

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    const int MAXN = 1005;
    const int MOD = 1000000007;
    inline int read()
    {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
    }
    struct edge
    {
    int END, next, v;
    }v[MAXN << 1];
    int first[MAXN], p;
    void add(int a, int b, int c)
    {
    v[p].END = b;
    v[p].next = first[a];
    v[p].v = c;
    first[a] = p++;
    }
    long long f[MAXN][MAXN];
    long long g[MAXN];
    long long Sum[MAXN][MAXN];
    long long C[MAXN][MAXN];
    int size[MAXN];
    void dfs(int rt, int fa)
    {
    size[rt] = f[rt][0] = 1;
    for (int i = first[rt]; i != -1; i = v[i].next)
    {
    if (v[i].END == fa) continue;
    dfs(v[i].END, rt);
    for (int j = 0; j < size[rt] + size[v[i].END]; j++) g[j] = 0;
    if (v[i].v == 1)
    for (int j = 0; j < size[rt]; j++)
    for (int k = 0; k <= size[v[i].END]; k++)
    {
    long long tmp = f[rt][j] * Sum[v[i].END][k - 1] % MOD;
    long long rmp = C[j + k][j] * C[size[rt] + size[v[i].END] - k - j - 1][size[v[i].END] - k] % MOD;
    (g[j + k] += tmp * rmp % MOD) %= MOD;
    }
    else
    for (int j = 0; j < size[rt]; j++)
    for (int k = 0; k <= size[v[i].END]; k++)
    {
    long long tmp = f[rt][size[rt] - j - 1] * (Sum[v[i].END][size[v[i].END] - 1] - Sum[v[i].END][size[v[i].END] - k - 1] + MOD) % MOD;
    long long rmp = C[j + k][j] % MOD * C[size[v[i].END] + size[rt] - k - j - 1][size[v[i].END] - k] % MOD;
    (g[size[rt] + size[v[i].END] - j - k - 1] += tmp * rmp % MOD) %= MOD;
    }
    size[rt] += size[v[i].END];
    for (int j = 0; j < size[rt]; j++) f[rt][j] = g[j];
    }
    Sum[rt][0] = f[rt][0];
    for (int i = 1; i < size[rt]; i++)
    Sum[rt][i] = (Sum[rt][i - 1] + f[rt][i]) % MOD;
    }
    int main()
    {
    int t = read();
    C[0][0] = 1;
    for (int i = 1; i <= 1000; i++)
    {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
    C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    }
    while (t--)
    {
    memset (size, 0, sizeof (size));
    memset (Sum, 0, sizeof (Sum));
    memset (f, 0, sizeof (f));
    memset (first, -1, sizeof (first));
    p = 0;
    int n = read(), a, b;
    char c[3];
    for (int i = 1; i < n; i++)
    {
    scanf ("%d%s%d", &a, c, &b);
    a++, b++;
    if (c[0] == '>') add(a, b, 1), add(b, a, -1);
    else add(a, b, -1), add(b, a, 1);
    }
    dfs(1, 0);
    printf ("%lld\n", Sum[1][n - 1]);
    }
    // while (1);
    }

    本文作者 : NekoMio
    知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
    本文链接 : https://www.nekomio.com/2017/10/28/117/

    本文最后更新于 天前,文中所描述的信息可能已发生改变