BZOJ4911 切树游戏

文章目录

建议在 LOJ 上提交

题解

一开始想用点分治然后DP,结果发现会统计不合法答案,后来去看题解了,发现这题简直神题
算法:动态dp+FWT
虽然题目中表示树是无根的,但是我们还是可以随便选一个点作为根
设 $f(i,k)$ 为以 $i$ 为根节点的子树,异或值为 $k$ 的联通子树个数
发现某个节点的 $f$ 值可以从所有子树的 $f$ 做异或卷积转移得来
具体地说,设 $F_i(z)$ 代表 $i$ 的 $f$ 数组的生成函数,则
$$ F_i(z) = z^{v_i} \prod (F_{son_i}(z)+z^0)$$
其中卷积为异或卷积

有了这个式子,不难想到如何求解总方案数,即
$$ Ans(k) = \sum f(i, k) $$
这样的复杂度还是较高,有 $\mathcal{O(nm\log m)} $,实际上并不需要每次讲一个式子做 $FMT$ 然后再 $FMI$ 回来,对每个点直接保存 $FMT$ 后的数组就行了
于是复杂度稍微好了一点,为 $\mathcal{O((n+\log m) m)} $ ,但是这只是一次操作的复杂度,对于最多有 $30000$ 个询问任然需要很长的时间
此时可以考虑使用动态dp,首先将链进行轻重链剖分,然后可以比较高效的维护重链上的信息,又由于某个点到根节点最多有 $\log(n)$ 条重链,所以问题看似可以解决了
现在只需要考虑如何维护
对于每个重链上的点 $i$ ,只要将它的所有轻儿子的 $F(z)+z^0$ 卷积就得到了所有轻儿子的贡献,设这个卷积结果为 $LF_i(z)$
设 $H_i(z)$ 为 $i$ 代表的重链上所有点的 $F(z)$ 之和
此时只要能快速求出 $F_{重链顶} (z),H_{重链顶}(z)$ 就可以快速算出该链对父亲重链的贡献
继续讲具体的维护方法
对于一条重链,设重链上的点按深度从小到大排序后为 $p_1,p_2,\dots,p_c$ ,那么我们可以得出以下方程:
$$
\begin{align}
&F_{p_c}(z) = H_{p_c}(z) = z^{v_{p_c}} \\
&F_{p_i}(z) = LF_{p_i}(z) \times (F_{p_{i+1}}(z) + z^0) \times {z^{v_{p_i}}} \\
&F_{p_i}(z) = H_{p_{i+1}}(z) + F_{p_{i}}(z)
\end{align}
$$
我们只需要求 $F_{p_1}(z)$ 和 $H_{p_1}(z)$
注意到上面这个式子中向量 $\left (F_{p_{i+1}}(z), H_{p_{i+1}}(z), z^0\right)$ 是通过一个线性变换得到向量 $\left (F_{p_i}(z), H_{p_i}(z), z^0\right)$ 的,具体地说就是乘上一个矩阵:
$$
M_i=\begin{pmatrix} LF_{p_i}{z}\times {z^{v_{p_i}}} & LF_{p_i}{z}\times {z^{v_{p_i}}} & 0 \\ 0 & 1 & 0 \\ LF_{p_i}{z}\times {z^{v_{p_i}}} & LF_{p_i}{z}\times {z^{v_{p_i}}} & 1 \end{pmatrix}
$$
这时,我们只要用线段树维护矩阵的乘积,就可以快速的进行操作,复杂度也是可行的
但是观察到还可以进一步优化,观察到矩阵中有很多位置是不会改变的,于是和那些位置有关的运算也不用进行
具体来说,可以将矩阵看成
$$
\begin {pmatrix} \underline {a} & \underline {b} & 0 \\ 0 & 1 & 0 \\ \underline {c} & \underline {d} & 1 \end {pmatrix}
$$

$$
\begin {pmatrix} \underline {a_1} & \underline {b_1} & 0 \\ 0 & 1 & 0 \\ \underline {c_1} & \underline {d_1} & 1 \end {pmatrix} \times \begin {pmatrix} \underline {a_2} & \underline {b_2} & 0 \\ 0 & 1 & 0 \\ \underline {c_2} & \underline {d_2} & 1 \end {pmatrix} = \begin {pmatrix} \underline {a_1 a_2} & \underline {b_1 + a_1 b_2} & 0 \\ 0 & 1 & 0 \\ \underline {a_2 c_1 + c_2} & \underline {b_2 c_1 + d_1 + d_2} & 1 \end {pmatrix}
$$
所以对每个矩阵只需要维护 $a,b,c,d$ 四个变量就行了,常数大大减小

代码

代码比较长,有很多地方需要解释一下
变量方面,由于名字和题解中的名字一致,所以不过多解释了,需要解释一下的是 data 存的是转移矩阵
代码里大部分公式(转移)可以在题解里找到答案,有几个需要解释一下:
1. LF 是一个 pair<int, int> 类型的,其中第一位记录的与题解中的一致,但是由于可能会有模模数后为0的情况,所以开了第二位几是模数的多少倍
2. 在 cut 函数中,需要对 ans 进行更改,观察矩阵发现某条重链对答案的影响就是重链上所有点的 $F(z)$ 的和,观察矩阵发现实际上就是矩阵的右下角的 $d$ ,于是将重链对应的线段树矩阵乘积求出来然后再用 $d$ 进行更改
3. 某条链对父亲重链的贡献,观察矩阵应该是矩阵中 $c$ 代表,但是我在程序中必须要用 $b$ 来做更改才行,如果有知道为什么的请麻烦告知一下

#define MAX_N 30007
#define MAX_M 140
#define MOD 10007
#define pii std::pair<int, int>

int N, M;
int head[MAX_N], to[MAX_N << 1], nxt[MAX_N << 1], cap;
int sz[MAX_N], mx[MAX_N], mp[MAX_N], id[MAX_N], top[MAX_N], btm[MAX_N], fa[MAX_N];
int inv[MAX_N];
int F[MAX_N][MAX_M], w[MAX_N][MAX_M];
int res[MAX_M], ans[MAX_M];
pii LF[MAX_N][MAX_M];

inline void addEdge (int u, int v) {
    nxt[++cap] = head[u];
    head[u] = cap;
    to[cap] = v;
}

struct data {
    int a[MAX_M], b[MAX_M], c[MAX_M], d[MAX_M];

    inline void init (int x) {
        x = mp[x];
        int v;
        for (int i = 0; i < M; ++i) {
            if (LF[x][i].second) v = 0;
            else v = 1LL * LF[x][i].first * w[x][i] % MOD;
            a[i] = b[i] = c[i] = d[i] = v;
        }
    }

    data operator * (const data &rhs) const {
        data ans;
        for (int i = 0; i < M; ++i) {
            ans.a[i] = 1LL * a[i] * rhs.a[i] % MOD;
            ans.b[i] = (b[i] + 1LL * a[i] * rhs.b[i] % MOD) % MOD;
            ans.c[i] = (1LL * rhs.a[i] * c[i] % MOD + rhs.c[i]) % MOD;
            ans.d[i] = (1LL * rhs.b[i] * c[i] % MOD + d[i] + rhs.d[i]) % MOD;
        }
        return ans;
    }
}t[MAX_N << 2], tmp;

inline void FMT (int *A, int M, int type) {
    for (int l = 1; l < M; l <<= 1) {
        for (int i = 0, L = l << 1; i < M; i += L) {
            for (int j = i, x, y; j < i + l; ++j) {
                x = A[j] % MOD, y = A[j + l] % MOD;
                A[j] = (x + y) % MOD, A[j + l] = (x - y + MOD) % MOD;
                if (type == -1)
                    A[j] = 1LL * A[j] * inv[2] % MOD, A[j + l] = 1LL * A[j + l] * inv[2] % MOD;
            }
        }
    }
}

void dfs (int x) {
    sz[x] = 1;
    for (int i = head[x]; i; i = nxt[i])
        if (to[i] != fa[x]) {
            fa[to[i]] = x;
            dfs(to[i]);
            sz[x] += sz[to[i]];
            if (sz[to[i]] > sz[mx[x]]) mx[x] = to[i];
        }
}

int tot;
void dfs1 (int x, int tp) {
    top[x] = tp;
    mp[id[x] = ++tot] = x;
    btm[x] = x;
    for (int i = head[x]; i; i = nxt[i])
        if (to[i] == mx[x])
            dfs1(to[i], tp), btm[x] = btm[to[i]];
    for (int i = 0; i < M; ++i)
        LF[x][i].first = 1;
    for (int i = head[x]; i; i = nxt[i])
        if (to[i] != fa[x] && to[i] != mx[x]) {
            dfs1(to[i], to[i]);
            for (int j = 0; j < M; ++j)
                if (F[to[i]][j] + 1 == MOD)
                    LF[x][j].second++;
                else
                    LF[x][j].first = 1LL * LF[x][j].first * (F[to[i]][j] + 1) % MOD;
        }
    for (int i = 0; i < M; ++i) {
        if (LF[x][i].second)
            F[x][i] = 0;
        else
            F[x][i] = 1LL * LF[x][i].first * (F[mx[x]][i] + 1) % MOD * w[x][i] % MOD;
        ans[i] = (ans[i] + F[x][i]) % MOD;
    }
}

void build (int x, int l, int r) {
    if (l == r) {
        t[x].init(l);
        return;
    }
    int mid = l + r >> 1;
    build(x << 1, l, mid);
    build(x << 1 | 1, mid + 1, r);
    t[x] = t[x << 1] * t[x << 1 | 1];
}

void query (int x, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        if (l == ql) tmp = t[x];
        else tmp = tmp * t[x];
        return;
    }
    int mid = l + r >> 1;
    if (ql <= mid) query(x << 1, l, mid, ql, qr);
    if (mid < qr) query(x << 1 | 1, mid + 1, r, ql, qr);
}

inline void cut (int x, int v) {
    query(1, 1, N, id[x], id[btm[x]]);
    for (int i = 0; i < M; ++i) ans[i] = 1LL * (ans[i] + v * tmp.d[i] + MOD) % MOD;
    if (!fa[x]) return;
    for (int i = 0; i < M; ++i) {
        int val = (tmp.b[i] + 1) % MOD;
        if (val == 0)
            LF[fa[x]][i].second += v;
        else
            LF[fa[x]][i].first = 1LL * LF[fa[x]][i].first * (v > 0 ? val : inv[val]) % MOD;
    }
}

void modify (int x, int l, int r, int pos) {
    if (l == r) {
        t[x].init(l);
        return;
    }
    int mid = l + r >> 1;
    if (pos <= mid)
        modify(x << 1, l, mid, pos);
    else
        modify(x << 1 | 1, mid + 1, r, pos);
    t[x] = t[x << 1] * t[x << 1 | 1];
}

inline void change (int x) {
    for (; x; x = fa[top[x]]) {
        cut(top[x], -1);
        modify(1, 1, N, id[x]);
        cut(top[x], 1);
    }
}

int main () {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
#endif
    read(N), read(M);
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= N; ++i)
        inv[i] = 1LL * (MOD - MOD / i) * inv[MOD % i] % MOD;
    int l = 0;
    while ((1 << l) < M) ++l;
    M = 1 << l;
    int u, v;
    for (int i = 1; i <= N; ++i) {
        read(v);
        w[i][v] = 1, FMT(w[i], M, 1);
    }
    for (int i = 1; i < N; ++i) {
        read(u), read(v);
        addEdge(u, v);
        addEdge(v, u);
    }
    dfs(1);
    dfs1(1, 1);
    build(1, 1, N);
    int T;
    read(T);
    char op[10];
    while (T--) {
        scanf("%s", op);
        if (op[0] == 'C') {
            read(u); read(v);
            memset(w[u], 0, sizeof(w[u]));
            w[u][v] = 1;
            FMT(w[u], M, 1);
            change(u);
        } else {
            read(u);
            memcpy(res, ans, M << 2);
            FMT(res, M, -1);
            printf("%d\n", res[u]);
        }
    }
    return 0;
}

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注