BZOJ 3167 [Heoi2013] Sao - NekoMio's Blog

题目描述#

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输出。

样例输入#

样例输出#

题解#

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