WC2018集训

发表于

我辣鸡死了。每晚总结一下。
我曹我欠的这一屁股债我自己都嫌弃。
2018-01-01（施工中）
2018-01-02
2018-01-03（施工中）
2018-01-04（施工中）
2018-01-05（施工中）
2018-01-06（施工中）

2018年1月1日（施工中）

上午 DP专题讲课
下午 专题训练
晚上 难题研讨

2018年1月2日

考试

string

Description

给定一个由小写字母组成的字符串 s，每次你可以删去它的一个非回文子串， 求删成空串的最小次数。
$30pt: |s| \le 10$
$60pt: |s| \le 100$
$100pt: |s| \le 10^5$

考场上

首先写完30pt暴力，没什么好说的。

60pt思路：考虑区间DP，$f[i][j]$表示挖掉$[i,j]$所需的最小代价。
再考虑被$[i,j]$包含、长度递减的区间$[l,r]$，$c[l][r]$表示挖掉区间$[l,r]$后剩下的字符串是否是回文串。
如果$[i,j]$不是回文串，$f[i][j] = 1$，否则

时间复杂度$O(n^4)$

随机出的数据答案全是1……
然后就随便手造了两三组数据，硬是构造不出答案为$3$的，想想算了就走了。

结果判回文串（计算$c$）的时候忽略了长度为奇数的回文串，此题爆0。
好气啊
我还是太菜了。

Solution

看来并不是我构造不出答案为$3$的数据，而是答案最多就是$2$。
首先如果字符串不是回文的，答案就是$1$。
考虑无解的情况，其他就都是$2$。
无解的情况，要么是抠完剩下来的东西全是回文的，要么就是满大街的回文串没东西抠。

没东西抠:$aaaaaaaaaa$。
抠完剩下全是回文:$abababababababa$,$aaaaaaabaaaaaaa$

然而还是爆0了……
mmp

Code

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
#include <bits/stdc++.h>
using namespace std ;
const int maxn = 105, zhf = 0x3f3f3f3f ;
int n ;
char s[100005] ;
bool judge ( int l, int r ) {
    for ( ; l < r ; l ++, r -- )
        if (s[l] ^ s[r]) return 0 ;
    return 1 ;
}
int main() {
    freopen ( "string.in", "r", stdin ) ;
    freopen ( "string.out", "w", stdout ) ;
    register int _, i, j, l, r, k, len ;
    scanf ( "%d", &_ ) ;
    while (_--) {
        scanf ( "%d", &n ) ;
        scanf ( "%s", s+1 ) ;
        bool fg = 0 ;
        for ( l = 1, r = n ; l < r ; l ++, r -- )
            if (s[l] ^ s[r]) {
                puts("1") ;
                fg = 1 ;
                break ;
            }
        if (fg) continue ;
        for ( i = 1 ; i < n ; i ++ )
            if (s[i] ^ s[i+1]) {
                fg = 1 ;
                break ;
            }
        if (!fg) {
            puts("-1") ;
            continue ;
        }
        if (n%2 == 0) {
            puts("2") ;
            continue ;
        }
        if (s[1] ^ s[2]) {
            s[n+1] = s[n-1] ;
            for ( i = 3 ; i <= n ; i += 2 )
                if ((s[i] ^ s[i-2]) || (s[i+1] ^ s[i-1])) {
                    fg = 0 ;
                    break ;
                }
        } else {
            for ( l = 2, r = n-1 ; l < r ; l ++, r -- )
                if ((s[l] ^ s[l-1]) || (s[r] ^ s[r+1])) {
                    fg = 0 ;
                    break ;
                }
        }
        if (fg) puts("-1") ;
        else puts("2") ;
    }
    return 0 ;
}

variable

Description

有$n$个变量$w[1] \cdots w[n]$，每个变量可以取$W$或$-W$。
有$p$个式子，形如

有$q$个条件，形如$w[x] \le w[y]$或$w[x]=w[y]$或$w[x] \lt w[y]$。
最小化 。
$30pt: n \le 15, p,q \le 20$
$100pt: t \le 10,n \le 500,p,q \le 1000$
$1 \le W \le 10^6， 0 \le a_i,b_i,c_i,d_i,e_i,f_i \le 1000$

考场上

感觉看到二选一就是往最小割方面想？
然而还是不会做，写完30pt暴力就溜了。
小插曲，一开始题面打错了，值域也没给出，后来更正之后我就只改了$H_i$里的符号。
没有long long，爆10了。
mmp

Solution

果然是最小割。我还是不出意料的不会。
是套路，那天考完粗略看了下pty的最小割论文，新建源点汇点，每个点连边割不割代表选不选。
不妨设$(s,x)$代表$W$，$(x,t)$代表$-W$。

要满足那$q$个条件，依照能否两个点的两个选择能否同时割掉在两点之间连边。

  • $w[x] \le w[y]$，那么$(s,x)$和$(y,t)$不能同时割掉，连边$(y, x, inf)$。
  • $w[x] = w[y]$，那么不能存在你连$s$他连$t$的情况，$x,y$要连同一边，连双向边。$(x,y,inf),(y,x,inf)$
  • $w[x] \lt w[y]$，没得选了，强制割掉的不连边，不能割掉的连$inf$。记得把强制割掉的权值加上。

对于$H$的处理简直巧妙。
对绝对值和括号分开处理。

  • $k \times |w[x] - w[y]|$，$x,y$的选择，使得他们要么相同要么差值为$2W$。两者的选择不同的话，一定会割掉$(x,y)$或者$(y,x)$，那么权值设为$2·W·k$即可，双向边。
  • $w[x] \times \sum k$，开个数组记下$x$的系数，最后统一修改$(s,t),(t,s)$的边权。

对于出现负数的情况，以前的姿势不对啊。

Code

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
#define LL long long
using namespace std ;
void Read ( LL &x, char c = getchar() ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const LL maxn = 605, maxm = 1e5+5, zhf = 1e10 ;
LL n, m, e = 1, V, Begin[maxn], Next[maxm], To[maxm], W[maxm] ;
LL p, q, fr[maxn], gt[maxn], val[maxn], dis[maxn], s, t, flow ;
LL add ( LL x, LL y, LL z ) {
    To[++e] = y ;
    Next[e] = Begin[x] ;
    W[e] = z ;
    return Begin[x] = e ;
}
queue <LL> Q ;
bool fbd[maxn][2] ;
void init() {
    e = 1, flow = 0 ;
    memset ( fbd, 0, sizeof fbd ) ;
    memset ( Begin, 0, sizeof Begin ) ;
}
bool bfs() {
    LL i, u, x = max(t, n) ;
    for ( i = 1 ; i <= x ; i ++ ) dis[i] = zhf ;
    while (!Q.empty()) Q.pop() ;
    dis[s] = 0 ;
    Q.push(s) ;
    while (!Q.empty()) {
        x = Q.front() ;
        Q.pop() ;
        for ( i = Begin[x] ; i ; i = Next[i] ) {
            u = To[i] ;
            if (dis[u] == zhf && W[i] > 0) {
                dis[u] = dis[x]+1 ;
                Q.push(u) ;
            }
        }
    }
    return dis[t] ^ zhf ;
}
LL dfs ( LL x, LL value ) {
    if (x == t|| value == 0) return value ;
    LL i, u, tot = 0, rec ;
    for ( i = Begin[x] ; i ; i = Next[i] ) {
        u = To[i] ;
        if (dis[u] == dis[x]+1 && W[i] > 0) {
            rec = dfs(u, min(value, W[i])) ;
            W[i] -= rec ;
            W[i ^ 1] += rec ;
            tot += rec ;
            value -= rec ;
            if (value == 0) return tot ;
        }
    }
    return tot ;
}
void dinic() { while (bfs()) flow += dfs(s, zhf) ; }
int main() {
    freopen ( "variable.in", "r", stdin ) ;
    freopen ( "variable.out", "w", stdout ) ;
    LL _, i, x, u, v, y, z ;
    LL A, B, C, D, E, F ;
    Read(_) ;
    while (_--) {
        Read(n) ; Read(V) ; Read(p) ; Read(q) ;
        s = n+1, t = s+1 ;
        init() ;
        for ( i = 1 ; i <= n ; i ++ )
            val[i] = 1 ;
        for ( i = 1 ; i <= p ; i ++ ) {
            Read(x) ; Read(y) ; Read(z) ;
            Read(A) ; Read(B) ; Read(C) ;
            Read(D) ; Read(E) ; Read(F) ;
            add(x, y, A*2), add(y, x, A*2) ;
            add(y, z, B*2), add(z, y, B*2) ;
            add(z, x, C*2), add(x, z, C*2) ;
        
            val[x] += D-F ;
            val[y] += E-D ;
            val[z] += F-E ;
        }
        for ( i = 1 ; i <= q ; i ++ ) {
            Read(x) ; Read(u) ; Read(v) ;
            if (v == 0) {
                add(u, x, zhf) ;
                add(x, u, 0) ;
            } else if (v == 1) {
                add(x, u, zhf) ;
                add(u, x, zhf) ;
            } else fbd[x][0] = fbd[u][1] = 1 ;
        }
        for ( i = 1 ; i <= n ; i ++ )
            if (val[i] > 0) {
                if (fbd[i][0]) {
                    add(s, i, zhf) ;
                    add(i, s, 0) ;
                    flow -= val[i] ;
                } else if (fbd[i][1]) {
                    add(i, t, zhf) ;
                    add(t, i, 0) ;
                    flow += val[i] ;
                } else {
                    add(s, i, val[i]*3) ;
                    add(i, s, 0) ;
                    add(i, t, val[i]) ;
                    add(t, i, 0) ;
                    flow -= val[i]*2 ;
                }
            } else {
                if (fbd[i][0]) {
                    add(s, i, zhf) ;
                    add(i, s, 0) ;
                    flow -= val[i] ;
                } else if (fbd[i][1]) {
                    add(i, t, zhf) ;
                    add(t, i, 0) ;
                    flow += val[i] ;
                } else {
                    add(s, i, -val[i]) ;
                    add(i, s, 0) ;
                    add(i, t, -val[i]*3) ;
                    add(t, i, 0) ;
                    flow += val[i]*2 ;
                }
            }
        dinic() ;
        printf ( "%lld\n", flow*V ) ;
    }
    return 0 ;
}

stone

Description

有$n$堆石子，第$i$堆有$x_i$个。 Alice 和 Bob 轮流取石子（先后手未定），Alice 每次从一堆中取走$a$个，Bob 每次从一堆中取走$b$个，无法操作者输。 不难发现只会有四种情况：Alice 必胜；Bob 必胜；先手必胜；后手必胜。 你需要选定若干堆石子（共有$2^n$ 种方案），Alice 和 Bob 只能在你选出的堆 中取，问以上四种情况对应的方案数。
$10pt: n,xi \le 5$
$50pt: n \le 20$
另$10pt: a=b$
另$20pt: a=1$
$100pt: 1 \le n \le 100000，1 \le a,b,xi \le 10^9$

考场上 && Solution

博弈论全白，看见博弈的东西直接弃。
弃他妈的，现在逃不掉了，虽然不会，但是还是想了。
昨天两道博弈的东西，貌似并没有什么要特别学的。
想得东西方向对了，但是还是忽略了一些。
但是还是爆10了。mmp
先bb一下，错的东西也b上来。

$a,b$顺序无关，不妨设$a>b$。
$a$不可能必胜。

对于两堆石子，大力讨论胜负情况的组合，发现二人先后都会在同一堆石子上操作，该输的逃不掉，选别的不会有更优解。
大力讨论的过程就懒得写了。
然后类似归纳法的思想，把多堆的石子情况合并了，最后就是每堆石子对$(a+b)$取模后答案不变。

考虑石头堆

  • $x \in [0,b)$，这堆石头谁都取不了。
  • $x \in [b,a)$，只有$b$能取，必胜。
  • $x \in [a,a+b)$，这时想错了，以为这里是先手必胜，其实不对，还需详细讨论。
    • $x-b \in [a-b,b)$，这时有$x \in [a,2b), x-a \in [0,2b-a) $，假如所有石头只有一堆那么就是先手必胜。其实个数奇偶性相关，设$t$为满足该种石头堆数的奇偶。
    • $x-b \in [b,a)$，这时有$x \in [2b,a+b), x-a \in [0,b)$
      • $存在个数 \le 2$，$b$必胜。
      • $存在个数 = 0$
        • 若$t = 0$，你一下我一下最后无法操作，后手必胜。
        • 若$t = 1$，先手动最后一下，先手必胜。
      • $存在个数 = 1$ ，这个就等于是多给了一次机会。
        • 若$t = 1$，如果$a$先，最后$b$不能动，胜；如果$b$先，最后$a$还可以动一下，$a$必胜。
        • 若$t = 0$，类似讨论得，先手必胜。

计算先手后手必胜的状态数，$2^n$减去即为$b$必胜的状态数。

Code

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
#include <bits/stdc++.h>
#define LL long long
using namespace std ;
void Read ( LL &x, char c = getchar(), bool f = 0 ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) if (c == '-') f = 1 ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
    if (f) x = -x ;
}
const LL maxn = 1e5+5, modd = 1e9+7 ;
LL Qpow ( LL a, LL b ) {
    LL rec = 1 ;
    for ( a %= modd ; b ; b >>= 1, (a *= a) %= modd )
        if (b&1) (rec *= a) %= modd ;
    return rec ;
}
LL n, m, a, b, cnt[4], ans[4] ;
int main() {
    freopen ( "stone.in", "r", stdin ) ;
    freopen ( "stone.out", "w", stdout ) ;
    Read(n) ; Read(a) ; Read(b) ;
    bool fg = 0 ;
    if (a < b) {
        swap(a, b) ;
        fg = 1 ;
    }
    LL i, x ;
    for ( i = 1 ; i <= n ; i ++ ) {
        Read(x) ;
        x %= (a+b) ;
        if (x < b) ++ cnt[0] ;
        else if (x < a) ++ cnt[1] ;
        else if (x < 2*b) ++ cnt[2] ;
        else ++ cnt[3] ;
    }
    if (cnt[2]) {
        x = Qpow(2, cnt[2]-1) ;
        (ans[0] += x) %= modd ;
        (ans[1] += x) %= modd ;
        (ans[0] += x*cnt[3]%modd) %= modd ;
    } else {
        (ans[0] += cnt[3]) %= modd ;
        (ans[1] += 1) %= modd ;
    }
    cnt[0] = Qpow(2, cnt[0]) ;
    (ans[0] *= cnt[0]) %= modd ;
    (ans[1] *= cnt[0]) %= modd ;
    ans[3] = Qpow(2, n) ;
    ans[3] = (ans[3]-ans[0]+modd)%modd ;
    ans[3] = (ans[3]-ans[1]+modd)%modd ;
    if (fg) swap(ans[2], ans[3]) ;
    printf ( "%lld %lld %lld %lld\n", ans[2], ans[3], ans[0], ans[1] ) ;
    return 0 ;
}

2018年1月3日（施工中）

上午 字符串专题讲课
下午 专题训练
晚上 难题研讨
TMD白天的字符串那么难，晚上长者的题又那么屎
我还是太菜了。

下午

BZOJ4974 [Lydsy八月月赛]字符串大师

Description

给出一个小写字符串每个前缀的最小循环节$ { per_i } (1 \le per_i \le i)$，求一个字典序最小的方案。$|s| \le 10^5$

Solution

要是求一个字符串的最小循环节，就用KMP的Next数组就行了，既然是反过来的操作，还是往这方面想。
既然给出的是最小循环节，那么，对于任意前缀$i$，如果循环次数大于$1$次的话，有$per_i \lt i$；否则$per_i = i$。

  • $per_i \lt i$，那么当前位置肯定与前面位置有对应的，考虑$i \% per_i$，注意整除。
  • $per_i = i$，可以得到$Next[i] = 0$，即不存在公共前后缀。那么就计算$Next[]$呗，强行使它为$0$，把不满足条件的字符标记掉，最后扫一遍字符集取最小。
    时间复杂度$O(|\sum| \times |s|)$，这里$|\sum| = 26$。
    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
    #include <bits/stdc++.h>
    using namespace std ;
    void Read ( int &x, char c = getchar() ) {
        for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
        for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
    }
    const int maxn = 1e5+5 ;
    int n, m, per[maxn], Next[maxn] ;
    char s[maxn] ;
    bool vis[maxn] ;
    int main() {
    #ifndef ONLINE_JUDGE
        freopen ( "BZOJ4976.in", "r", stdin ) ;
        freopen ( "BZOJ4976.out", "w", stdout ) ;
    #endif
        int i, j, x ;
        Read(n) ;
        for ( i = 1 ; i <= n ; i ++ )
            Read(per[i]) ;
        s[1] = 'a' ;
        for ( i = 2 ; i <= n ; i ++ ) {
            if (i ^ per[i]) {
                x = i%per[i] ;
                if (x == 0) s[i] = s[per[i]] ;
                else s[i] = s[x] ;
            } else {
                memset ( vis, 0, sizeof vis ) ;
                for ( ; j ; j = Next[j] )
                    vis[s[j+1]-'a'] = 1 ;
                for ( j = 1 ; j < 26 ; j ++ )
                    if (!vis[j]) {
                        s[i] = j+'a' ;
                        break ;
                    }
                j = 0 ;
            }
            for ( ; j && s[i] != s[j+1] ; j = Next[j] ) ;
            Next[i] = s[i]==s[j+1]? ++j:j ;
        }
        for ( i = 1 ; i <= n ; i ++ )
            putchar(s[i]) ;
        return 0 ;
    }

晚上

清橙A1210. 光棱坦克

Description

一个平面直角坐标系上，有$N$个点，标号为$1$到$N$，其中第$i$个点的坐标为$(x[i], y[i])$。
求满足以下两个条件的点列${p[i]}$的数目（假设${p[i]}$的长度为$M$）：

  • 对任意$1 \le i \lt j \le M$，必有$y[p[i]] \gt y[p[j]]$；
  • 对任意$3 \le i \le M$，必有$x[p[i-1]] \lt x[p[i]] \le x[p[i-2]]$或者$x[p[i-2]] \le x[p[i]] \le x[p[i-1]]$。
    求满足条件的非空序列${p[i]}$的数目，结果对一个整数$Q$取模。
    $n \le 7000$

Solution

长者都用他一年前做的题虐我
我还是太菜了，讲完了又要去问。
还是bb一下自己的理解。
问题转化一下，选一个点开始，每次从高处往低处跳，而且必须左跳一下右跳一下。
显然是个DAG关系，更显然的是$y$要满足的顺序。
那么就把不那么显然的$x$排序吧。

DAG上DP，$f[x]$表示以$x$为起点的方案数。
还要考虑初始的方向，添一维$[0/1]$表示左/右。
考虑每次新加入一个点$i$，再从右往左考虑前面$i - 1$个点$j$。
为什么是从右往左？即横坐标递减。
因为每个点向左的答案在该点加入的时候就已经算好了，而……

  • 若点$i$在点$j$上方，更新$i$向左的答案。
  • 否则，更新$j$向右的答案。

向右的答案是类似于一个后缀和之类的长相，所以要控制方向。

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
#include <bits/stdc++.h>
using namespace std ;
void Read ( int &x, char c = getchar() ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const int maxn = 7005 ;
int n, m, f[2][maxn][2], modd ;
struct node {
    int x, y ;
    friend bool operator < ( node a, node b ) {
        return a.x < b.x ;
    }
} s[maxn] ;
int main() {
#ifndef ONLINE_JUDGE
    freopen ( "A1210.in", "r", stdin ) ;
    freopen ( "A1210.out", "w", stdout ) ;
#endif
    int i, j, k ;
    Read(n) ; Read(modd) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        Read(s[i].x) ;
        Read(s[i].y) ;
    }
    sort(s+1, s+n+1) ;
    bool t = 0 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        t ^= 1 ;
        memcpy(f[t], f[t ^ 1], sizeof f[t]) ;
        f[t][i][0] = f[t][i][1] = 1 ;
        for ( j = i-1 ; j ; j -- )
            if (s[i].y > s[j].y) (f[t][i][0] += f[t][j][1]) %= modd ;
            else (f[t][j][1] += f[t][i][0]) %= modd ;
    }
    k = 0 ;
    for ( i = 1 ; i <= n ; i ++ )
        (k += ((f[t][i][0]+f[t][i][1])%modd+modd-1)%modd) %= modd ;
        //如果路径上只有一个点，不能算重
    printf ( "%d\n", k ) ;
    return 0 ;
}

2018年1月6日（施工中）

考试。
难度开始WC了？

送你一个 DAG (xmasdag.cpp/in/out, 1s, 512MB)

Description

送你一个$n$个点$m$条边的 DAG 和参数$k$, 定义一条经过$l$条边的路径的权值为$l^k$.
对于$i = 1 \cdots n$, 求出所有$1$到$i$的路径的权值之和, 对 $998244353$ 取模.
对于前 $20\%$ 的数据, $n \le 2000$, $m \le 5000$;
对于另 $10\%$ 的数据, $k = 1$;
对于另 $20\%$ 的数据, $k ≤ 30$;
对于 $100\%$ 的数据, $1 \le n \le 100000$, $1 \le m \le 200000$, $0 \le k \le 500$, 保证从$1$出发可以到达每个点, 可能会有重边.

考场上

先写了20pt暴力，然后推了个$O(nk^2)$的做法，那晓得竟然第2个点TLE了，只有40pt。
暴力就是不说了，先bb一下$O(nk^2)$的。

先把边都翻过来，总感觉终点确定的DAG好搞一点，我写DAG上DP还是不喜欢拓扑序，喜欢记忆化。
一开始看错题了，以为是$k^l$，我说这不进制$k$的运算吗，结果是看反了，我才是傻逼。

看错题也给我带来了思路，如果是那样的话，$l$每次增加的贡献是可求的。现在也考虑每次 增加的变化。
二项式展开一下

移项，得到

令$f[x][j]$代表从$x$点出发经过$j$条边的方案数，$g[x][i]$代表从$x$点出发,$p$条边的路径贡献为$p^i$的答案.最终求的就是$g[x][k]$.
那么有

再开个数组$sg[][]$存下后面那一坨.

由于最多只有一个点才会走满$m$条边，而它又不会更新别的点，所以上面的式子里$j$的上界无所谓。
设而不求是个好东西。
对于每个点,状态数$O(k)$,转移$sg$的复杂度是$O(k)$.
总状态数$O(nk)$,转移复杂度$O(k)$,时间复杂度$O(nk^2)$.

Solution

竟然是第二类斯特林数?把$N$个元素划分为$M$个有区别的集合。
还有巧妙至极的集合/整体思想?
说不来是什么,只好自己造名词.

首先是一个式子,百度百科上都有,但我都不知道.
我真是垃圾死了.

考虑把$k$个元素放进$l$个有区别的集合,注意是放进,允许存在空集.
枚举空集个数$i$,划分的方案数就是第二类斯特林数,空集还有排列.

然后设$(P, x)$这个东西代表一条从$x$出发到终点的路径$P$,其中$P$长度为$p$.
$F(x)$代表从$x$出发的答案.

前面的斯特林数好算,现在考虑如何计算后面那一坨.
下面的$u$都代表$x$可达的点.

直接把路径集合看做一个整体，$(P, x)$的长度是$(P, u)$的长度$+1$。巧妙。

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
#include <bits/stdc++.h>
#define LL long long
using namespace std ;
void Read ( int &x, char c = getchar() ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const int maxn = 1e5+5, maxm = 2e5+5, maxk = 505, modd = 998244353 ;
int n, m, f[maxn][maxk], k, deg[maxn], S[maxk][maxk] ;
int e, Begin[maxn], Next[maxm], To[maxm] ;
void add ( int x, int y ) {
    To[++e] = y ;
    Next[e] = Begin[x] ;
    Begin[x] = e ;
}
bool vis[maxn] ;
void init() {
    S[0][0] = 1 ;
    int i, j ;
    for ( i = 1 ; i <= k ; i ++ ) {
        S[i][0] = 0 ;
        for ( j = 1 ; j <= i ; j ++ )
            S[i][j] = ((LL)S[i - 1][j]*j%modd + S[i - 1][j - 1])%modd ;
    }
}
void dfs ( int x ) {
    if (vis[x]) return ;
    vis[x] = 1 ;
    int i, j, u ;
    for ( i = Begin[x] ; i ; i = Next[i] ) {
        u = To[i] ;
        dfs(u) ;
        (f[x][0] += f[u][0]) %= modd ;
        for ( j = 1 ; j <= k ; j ++ )
            (f[x][j] += ((LL)f[u][j-1]*j%modd + f[u][j])%modd) %= modd ;
    }
}
int main() {
    freopen ( "xmasdag.in", "r", stdin ) ;
    freopen ( "xmasdag.out", "w", stdout ) ;
    
    int i, j, x, u ;
    Read(n) ; Read(m) ; Read(k) ;
    init() ;
    for ( i = 1 ; i <= m ; i ++ ) {
        Read(u) ; Read(x) ;
        add(x, u) ;
        ++ deg[u] ;
    }
    vis[1] = 1 ;
    f[1][0] = 1 ;
    for ( i = 2 ; i <= n ; i ++ )
        if (!deg[i]) dfs(i) ;
    puts("0") ;
    int ans ;
    for ( i = 2 ; i <= n ; i ++ ) {
        ans = 0 ;
        for ( j = 0 ; j <= k ; j ++ )
            (ans += (LL)S[k][j]*f[i][j]%modd) %= modd ;
        printf ( "%d\n", ans ) ;
    }
    return 0 ;
}

送你一棵圣诞树 (xmastree1.cpp/in/out, 2s, 512MB)

Description

送你一棵$n$个点的树, 树根为$1$.一开始每个点上有一个$1 \cdots n$的颜色$c_i$,不同点颜色可以相同.
现在有 $q$ 次操作, 分为两种类型:

  • $1 u l r$: 询问子树$u$中有多少种在$l$到$r$之间的颜色至少出现了一次
  • $2 u c$: 将$u$的颜色修改为$c$
    部分测试点要求强制在线.

Solution

考场上写完暴力就溜了。
树状数组套线段树。
BIT的下标代表颜色，线段树下标代表dfs序的。
显然询问都是连着的。
对于一种颜色，按dfs序排一下，每个点的贡献+1，相邻两个点的LCA处贡献-1.求和。
第一次写“套”的数据结构，找时间把洛谷树套树的模板写了，别懒。
注释也不删了。

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include <bits/stdc++.h>
using namespace std ;
void Read ( int &x, char c = getchar() ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
}
const int maxn = 1e5+5 ;
int n, m, c[maxn], Begin[maxn], Next[maxn<<1], To[maxn<<1], e ;
void add ( int x, int y ) {
    To[++e] = y ;
    Next[e] = Begin[x] ;
    Begin[x] = e ;
}
int rt[maxn], tot, ch[maxn*300][2], t[maxn*300] ;
int clk, rdn[maxn], id[maxn], od[maxn], sz[maxn] ;
int top[maxn], fa[maxn], son[maxn], dep[maxn] ;
#define L ch][0
#define R ch][1
set <int> st[maxn] ;
int dfs1 ( int x ) {
    int i, u ;
    sz[x] = 1 ;
    for ( i = Begin[x] ; i ; i = Next[i] ) {
        u = To[i] ;
        if (u == fa[x]) continue ;
        fa[u] = x ;
        dep[u] = dep[x]+1 ;
        sz[x] += dfs1(u) ;
        if (sz[u] > sz[son[x]]) son[x] = u ;
    }
    return sz[x] ;
}
void dfs2 ( int x ) {
    int i, u ;
    id[x] = ++ clk ;
    rdn[clk] = x ;
    if (son[x]) {
        top[son[x]] = top[x] ;
        dfs2(son[x]) ;
    }
    for ( i = Begin[x] ; i ; i = Next[i] ) {
        u = To[i] ;
        if (u == fa[x] || u == son[x]) continue ;
        top[u] = u ;
        dfs2(u) ;
    }
    od[x] = clk ;
}
int LCA ( int u, int v ) {
    while (top[u] ^ top[v]) {
        if (dep[top[u]] > dep[top[v]]) swap(u, v) ;
        v = fa[top[v]] ;
    }
    if (dep[u] > dep[v]) swap(u, v) ;
    return u ;
}
set <int> :: iterator it ;
void push_up ( int x ) {
    t[x] = 0 ;
    if (x[L]) t[x] += x[L][t] ;
    if (x[R]) t[x] += x[R][t] ;
}
int insert ( int l, int r, int p, int v ) {
    int x = ++tot, mid = (l+r)>>1 ;
    if (l == r) {
        t[x] = v ;
        return x ;
    }
    if (p <= mid) x[L] = insert(l, mid, p, v) ;
    else x[R] = insert(mid+1, r, p, v) ;
    push_up(x) ;
    return x ;
}
int update ( int x, int l, int r, int p, int v ) {
    if (!x) return insert(l, r, p, v) ;
    int mid = (l+r)>>1 ;
    if (l == r) {
        t[x] += v ;
        return x ;
    }
    if (p <= mid) x[L] = update(x[L], l, mid, p, v) ;
    else x[R] = update(x[R], mid+1, r, p, v) ;
    push_up(x) ;
    return x ;
}
void Update ( int i, int d, int value ) {
    int l, r, x, u, v ;
    l = r = x = u = v = 0 ;
    it = st[i].lower_bound(id[d]) ;
    r = *it ;
    -- it ;
    l = *it ;
    if (r < 1 || r > n) r = 0 ;
    if (l < 1 || r > n) l = 0 ;
    l = rdn[l] ;
    r = rdn[r] ;
    if (l) x = LCA(l, d) ;
    if (r) u = LCA(d, r) ;
    if (l && r) v = LCA(l, r) ;
    //printf ( "Update %d %d %d\n", i, d, value ) ;
    //printf ( "LCA(%d,%d)=%d LCA(%d,%d)=%d LCA(%d,%d)=%d\n", l, d, x, d, r, u, x, u, v ) ;
    for ( ; i <= n ; i += i&(-i) ) {
        if (!rt[i]) rt[i] = insert(1, n, id[d], value) ;
        else update(rt[i], 1, n, id[d], value) ;
        if (x) update(rt[i], 1, n, id[x], -value) ;
        if (u) update(rt[i], 1, n, id[u], -value) ;
        if (v) update(rt[i], 1, n, id[v], value) ;
    }
}
int query ( int h, int l, int r, int x, int y ) {
    if (x <= l && r <= y) return t[h] ;
    int rec = 0, mid = (l+r)>>1 ;
    if (y <= mid) {
        if (h[L]) return query(h[L], l, mid, x, y) ;
        return 0 ;
    } else if (x > mid) {
        if (h[R]) return query(h[R], mid+1, r, x, y) ;
        return 0 ;
    }
    if (h[L]) rec += query(h[L], l, mid, x, mid) ;
    if (h[R]) rec += query(h[R], mid+1, r, mid+1, y) ;
    return rec ;
}
int Query ( int i, int x ) {
    int rec = 0 ;
    //printf ( "Query %d %d\n", i, x ) ;
    for ( ; i ; i -= i&(-i) ) {
        if (rt[i]) rec += query(rt[i], 1, n, id[x], od[x]) ;
        //printf ( "bit %d = %d\n", i, rec ) ;
    }
    //printf ( "rec = %d\n", rec ) ;
    return rec ;
}
void output ( int x, int l, int r ) {
    printf ( "t[%d]=%d [%d,%d]\n", x, t[x], l, r ) ;
    int mid = (l+r)>>1 ;
    if (x[L]) output(x[L], l, mid) ;
    if (x[R]) output(x[R], mid+1, r) ;
}
void check() {
    for ( int i = 1 ; i <= n ; i ++ )
        if (st[i].size() > 2) {
            printf ( "set %d : ", i ) ;
            for ( it = st[i].begin() ; it != st[i].end() ; it ++ ) {
                if (*it > 0 && *it <= n)
                    printf ( "%d ", *it ) ;
            }
            puts("") ;
        }
    for ( int i = 1 ; i <= n ; i ++ )
        if (rt[i]) {
            printf ( "rt[%d] = %d\n", i, rt[i] ) ;
            output(rt[i], 1, n) ;
        }
    puts("") ;
}
int main() {
    freopen ( "xmastree1.in", "r", stdin ) ;
    freopen ( "xmastree1.out", "w", stdout ) ;
    int i, _, op, tp, x, u ;
    int ans = 0 ;
    Read(n) ; Read(_) ; Read(tp) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        Read(c[i]) ;
        st[i].insert(0) ;
        st[i].insert(n+1) ;
    }
    for ( i = 1 ; i < n ; i ++ ) {
        Read(x) ; Read(u) ;
        add(x, u) ;
        add(u, x) ;
    }
    dfs1(1) ;
    top[1] = 1 ;
    dfs2(1) ;
    for ( i = 1 ; i <= n ; i ++ ) {
        Update(c[i], i, 1) ;
        st[c[i]].insert(id[i]) ;
        //check() ;
    }
    //check() ;
    int l, r ;
    while (_--) {
        Read(op) ;
        if (op == 1) {
            Read(x) ; Read(l) ; Read(r) ;
            if (tp) x ^= ans, l ^= ans, r ^= ans ;
            printf ( "%d\n", ans = Query(r, x)-Query(l-1, x) ) ;
        } else {
            Read(x) ; Read(u) ;
            if (tp) x ^= ans, u ^= ans ;
            st[c[x]].erase(id[x]) ;
            Update(c[x], x, -1) ;
            c[x] = u ;
            Update(c[x], x, 1) ;
            st[c[x]].insert(id[x]) ;
            //check() ;
        }
    }
    return 0 ;
}