[SDOI2017]切树游戏 [FWT][动态DP]

[SDOI2017]切树游戏

orz rqy。首先可以知道,维护每种值的方案即可。令F_xx为根的子树的集合幂级数,只需要用\prod (F_y+1)更新即可。

那么无脑FWT一下。之后考虑动态化。那么就维护轻儿子和重链。令H_x表示x轻儿子合并后的东西,那么有F_x=H_x(F_y+1)=H_x+H_xH_{xx'}+...,也就是一堆积的和。

就可以知道一条链的答案就是所有子区间的积的和,线段树可以维护。

之后就是一些(很多)细节问题了。列举一二:

FWT直接单点就可以了。考虑贡献发现就是更改正负号。

在修改时,因为不是用矩阵的方式维护的,要直接从某个H中除掉一部分。但是当是倍数的时候,没有逆元。解决方法是手写一个东西,维护每个点轻儿子中,有多少个0,以及剩下的乘积。

代码在洛谷T了两个点,不知道为什么,貌似被卡了,loj过了。。

// orz rqy jiejie
#include <bits/stdc++.h>

using std::cerr;
using std::endl;

inline int rd() {
  int b = 0; char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) b = b * 10 + c - '0', c = getchar();
  return b;
}

inline int get_op() {
  char c = getchar();
  while (!isalpha(c)) c = getchar();
  return c == 'Q' ? 1 : 2;
}

const int N = 3e4 + 233, M = 130, P = 10007;

int n, m, q, val[N], cnt[N], inv[N];
int fa[N], son[N], size[N], top[N], dfn[N], id[N], num, bot[N];
int ans[M];
std::vector<int> G[N];

struct Int {
  int a, p;
  Int(int t = 0) {
    a = (t == 0 ? 1 : t);
    p = (t == 0);
  }
  Int(int _a, int _p) { a = _a, p = _p; }
  operator int() { return !p ? a : 0; }
  Int operator+(int x) {
    if ((x %= P) != 0)
      return Int(p > 0 ? x : (a + x) % P, 0);
    else
      return *this;
  }
  Int& operator*=(int x) {
    if (!(x %= P)) ++p;
    else a = a * x % P;
    return *this;
  }
  Int& operator/=(int x) {
    if (!(x %= P)) --p;
    else a = a * inv[(x + P) % P] % P;
    return *this;
  }
};

Int H[N][M];
int F[N][M];

struct Node {
  int sum[M], pre[M], suf[M], mul[M];
  inline void init() {
    memset(sum, 0, sizeof sum);
    memset(pre, 0, sizeof pre);
    memset(suf, 0, sizeof suf);
    memset(mul, 0, sizeof mul);
    for (int i = 0; i < m; ++i)
      mul[i] = 1;
  }
  Node() { init(); }
  Node(Int H[]) {
    for (int i = 0; i < m; ++i)
      sum[i] = pre[i] = suf[i] = mul[i] = H[i];
  }

  inline friend Node operator*(const Node &l, const Node &r) {
    Node ret;
    for (int i = 0; i < m; ++i) {
      ret.sum[i] = (l.sum[i] + r.sum[i] + l.suf[i] * r.pre[i]) % P;
      ret.pre[i] = (l.pre[i] + l.mul[i] * r.pre[i]) % P;
      ret.suf[i] = (r.suf[i] + r.mul[i] * l.suf[i]) % P;
      ret.mul[i] = l.mul[i] * r.mul[i] % P;
    }
    return ret;
  }

} seg[N * 4], tmp;

#define ls (p << 1)
#define rs (ls | 1)
#define mid ((L + R) >> 1)

inline void pushup(int p, int L, int R) {
  if (L != R)
    seg[p] = seg[ls] * seg[rs];
  else
    seg[p] = Node(H[id[L]]);
}

void build(int p, int L, int R) {
  if (L != R) {
    build(ls, L, mid);
    build(rs, mid + 1, R);
  }
  pushup(p, L, R);
}

void modify(int p, int x, int L, int R) {
  if (L != R)
    x <= mid ? modify(ls, x, L, mid)
      : modify(rs, x, mid + 1, R);
  pushup(p, L, R);
}

void query(int p, int l, int r, int L, int R) {
  if (l <= L && r >= R)
    return tmp = tmp * seg[p], void();
  if (l <= mid) query(ls, l, r, L, mid);
  if (r > mid) query(rs, l, r, mid + 1, R);
}

void dfs1(int x, int dad) {
  fa[x] = dad, size[x] = 1;
  for (int y : G[x]) if (y != dad) {
    dfs1(y, x);
    size[x] += size[y];
    if (size[son[x]] < size[y])
      son[x] = y;
    /*
    // what the fuck ??
    if (!son[x] || size[son[x]] + 50 < size[y])
      son[x] = y;
    */
  }
}

void dfs2(int x, int topf) {

  top[x] = topf, id[dfn[x] = ++num] = x;

  if (!son[x]) {
    bot[x] = x;
  } else {
    dfs2(son[x], topf);
    bot[x] = bot[son[x]];
  }

  for (int i = 0; i < m; ++i)
    H[x][i] = 1;

  for (int y : G[x])
    if (y != fa[x] && y != son[x]) {
      dfs2(y, y);
      for (int i = 0; i < m; ++i)
        H[x][i] *= F[y][i] + 1;
    }

  for (int i = 0; i < m; ++i)
    if (cnt[i & val[x]] & 1)
      H[x][i] *= -1;

  for (int i = 0; i < m; ++i)
    F[x][i] = H[x][i];

  if (son[x])
    for (int i = 0; i < m; ++i)
      F[x][i] = F[x][i] * (F[son[x]][i] + 1) % P;

  for (int i = 0; i < m; ++i)
    ans[i] = (ans[i] + F[x][i]) % P;

}

void cut(int x) {
  if (!x) return;
  modify(1, dfn[x], 1, n);
  int y = top[x];
  cut(fa[y]);
  tmp.init();
  query(1, dfn[y], dfn[bot[y]], 1, n);
  for (int i = 0; i < m; ++i)
    ans[i] = (ans[i] - tmp.sum[i] + P) % P;
  for (int i = 0; i < m; ++i)
    H[fa[y]][i] /= tmp.pre[i] + 1;
}

void link(int x) {
  if (!x) return;
  modify(1, dfn[x], 1, n);
  int y = top[x];
  tmp.init();
  query(1, dfn[y], dfn[bot[y]], 1, n);
  for (int i = 0; i < m; ++i)
    ans[i] = (ans[i] + tmp.sum[i]) % P;
  for (int i = 0; i < m; ++i)
    H[fa[y]][i] *= tmp.pre[i] + 1;
  link(fa[y]);
}

inline void modify(int x, int y) {
  cut(x);
  for (int i = 0; i < m; ++i)
    if (cnt[i & val[x]] & 1)
      H[x][i] *= -1;
  val[x] = y;
  for (int i = 0; i < m; ++i)
    if (cnt[i & val[x]] & 1)
      H[x][i] *= -1;

  link(x);
}

int main() {
  n = rd(), m = rd();
  inv[1] = cnt[1] = 1;
  for (int i = 2; i < P; ++i) {
    inv[i] = P - P / i * inv[P % i] % P;
    cnt[i] = cnt[i >> 1] + (i & 1);
  }
  for (int i = 1; i <= n; ++i) {
    val[i] = rd();
  }
  for (int i = 1; i < n; ++i) {
    int x = rd(), y = rd();
    G[x].push_back(y);
    G[y].push_back(x);
  }
  dfs1(1, 0);
  dfs2(1, 1);
  build(1, 1, n);
  q = rd();
  while (q--) {
    int op = get_op(), x = rd(), y = op == 2 ? rd() : 0;
    if (op == 1) {
      int sum = 0;
      for (int i = 0; i < m; ++i)
        sum = (sum + (cnt[i & x] & 1 ? P - 1 : 1) * ans[i]) % P;
      sum = (sum * inv[m] % P + P) % P;
      printf("%d\n", sum);
    } else {
      modify(x, y);
    }
  }
  tmp.init();
  query(1, 1, n, 1, n);
  return 0;
}

发表评论

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