[LibreOJ 2185][SDOI2015]约数个数和

首先我们有这样一个式子:

\[d(ij) = \sum_{a | i}\sum_{b | j} [\gcd(\frac{i}{a}, b) = 1]\]

怎样理解这一结论呢?我们知道\(ij\)的约数\(d\)一定可以被分解为\(ab\)使得\(a | i, b | j\),但这种划分可能会非常的多,我们要保证每个约数\(d\)只有一种划分被统计过。

那么考虑上述划分方法。对于\(i\)和\(j\)中一个有一个没有的质因子,是一定会划分到\(a\)和\(b\)中固定的一个的。那么考虑一个在\(i\)和\(j\)中都出现的质因子\(p\),假设\(p\)在\(d\)中出现的次数超过了\(i\)和\(j\)中任何一个的话,那么\(p\)在\(a\)中一定会尽可能多的出现(否则\(\frac{i}{a}\)中会出现\(p\),而这样无论如何一定有\(p | b\),因此会不满足\(\gcd(\frac{i}{a}, b) = 1\))。如果没超过呢?那么一定会全部划分到\(a\)中(其他情况下有\(p | b\)并且会出现\(p | \frac{i}{a}\))。

下面考虑应用这个结论(为了方便,使用等价的\(d(ij) = \sum_{a | i}\sum_{b | j} [\gcd(a, b) = 1]\),假设\(n\le m\)):

\[
\begin{aligned}
\quad&\sum_{i = 1}^n\sum_{j = 1}^m \sum_{a | i}\sum_{b | j}\sum_{d | i, d | j}\mu(d)\\
=&\sum_{d = 1}^n\mu(d)\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{ad}\rfloor\sum_{b = 1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{bd}\rfloor\\
=&\sum_{d = 1}^n\mu(d)\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor}d(a)\sum_{b = 1}^{\lfloor\frac{m}{d}\rfloor}d(b)
\end{aligned}
\]

后面两个和式可以随便\(O(n)\)欲处理一下(然后我当初写了个\(O(n\sqrt{n})\)的神必预处理……),然后这个题做完力,,,

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <queue>
#include <utility>
typedef long long int_t;
const int maxn = 50005;
int_t miu[maxn], miu_s[maxn], f[maxn];
void process() {
  static bool vis[maxn];
  static int prm[maxn]; int cnt = 0;
  const int N = 50000;
  miu[1] = 1LL;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      miu[i] = -1LL; prm[cnt ++] = i;
    }
    for(int j = 0; j < cnt && prm[j] * i <= N; j ++) {
      int v = prm[j] * i;
      vis[v] = true;
      if(i % prm[j] == 0) {
        miu[v] = 0; break;
      } else {
        miu[v] = miu[i] * -1;
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    miu_s[i] = miu_s[i - 1] + miu[i];
  }
  for(int i = 1; i <= N; i ++) {
    for(int j = 1; j <= i;) {
      int nx = i / (i / j);
      f[i] += (int_t(nx - j + 1)) * (int_t(i / j));
      j = nx + 1;
    }
  }
}

int_t solve(int n, int m) {
  int_t ans = 0;
  for(int i = 1; i <= std::min(n, m);) {
    int nx = std::min(m / (m / i), n / (n / i));
    ans += (miu_s[nx] - miu_s[i - 1]) * f[m / i] * f[n / i];
    i = nx + 1;
  }
  return ans;
}
#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
  process(); int T;
  scanf("%d", &T);
  while(T --) {
    int n, m; scanf("%d%d", &n, &m);
    printf(LO, solve(n, m)); puts("");
  }
  return 0;
}

[LibreOJ 2100][TJOI2015]线性代数

颓一波式子可以发现答案就是\(ABA^T-CA^T\)。然后发现对于一个\(B\)中的元素\(B_{i, j}\)要对答案做出贡献要求\(A_i\)和\(A_j\)都为1,而\(A_i\)为1会导致答案减去一个\(C_i\)。

因此我们可以分别对\(B\)中元素和\(A\)中元素建点。\(B\)中元素会带来收益,但是要求依赖两个\(A\)中元素。而\(A\)中元素会带来一定的笋丝。这个就已经事很明显的最大权闭合子图力,,,

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
const int maxn = 505;
const int maxno = 500 * 500 + 500 + 5;
const int maxm = 2 * (500 * 500 * 3 + 500 + 5);
int first[maxno];
int next[maxm], to[maxm], flow[maxm], cap[maxm];
int gcnt = 0;
void add_edge(int u, int v, int c) {
  gcnt ++;
  next[gcnt] = first[u]; first[u] = gcnt;
  to[gcnt] = v; cap[gcnt] = c; flow[gcnt] = 0;
}
void ins_edge(int u, int v, int c) {
  add_edge(u, v, c); add_edge(v, u, 0);
}
int rev(int i) {
  if(1 & i) {
    return i + 1;
  } else {
    return i - 1;
  }
}

int d[maxno];
int s, t, num;
bool bfs() {
  static bool vis[maxno];
  std::fill(vis, vis + num + 1, false);
  std::fill(d, d + num + 1, 0);
  std::queue<int> Q; Q.push(s);
  d[s] = 1; vis[s] = true;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(!vis[v] && cap[i] > flow[i]) {
        d[v] = d[u] + 1;
        Q.push(v); vis[v] = true;
      }
    }
  }
  return vis[t];
}
int cur[maxno];
int dfs(int x, int a) {
  if(a == 0 || x == t) return a;
  int ret = 0;
  for(int &i = cur[x]; i; i = next[i]) {
    int v = to[i], f;
    if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
      ret += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[x] = -1;
  return ret;
}
int dinic() {
  int ret = 0;
  while(bfs()) {
    for(int i = 0; i <= num; i ++) cur[i] = first[i];
    ret += dfs(s, 0x7f7f7f7f);
  }
  return ret;
}

int n;
int main() {
  int ans = 0;
  scanf("%d", &n);
  s = 0, t = n * n + n + 1;
  num = t;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n; j ++) {
      int u = (i - 1) * n + j; int val; scanf("%d", &val);
      ans += val; ins_edge(s, u, val);
      ins_edge(u, n * n + i, 0x7f7f7f7f);
      ins_edge(u, n * n + j, 0x7f7f7f7f);
    }
  }
  for(int i = 1; i <= n; i ++) {
    int val; scanf("%d", &val);
    ins_edge(n * n + i, t, val);
  }
  ans -= dinic();
  printf("%d\n", ans);
  return 0;
}

[LibreOJ 2472][九省联考2018]IIIDX

一直没有填的坑……今天乱写了写跑过了然后厚颜无耻凑一篇题解

还有样例过于草(出题人钦点淫梦运营

考虑从小到大枚举序列的每一位置\(p\),然后我们发现每一位置的值的合法性事单调的(小的合法,大了就不合法),这样可以对每一个位置二分答案。

然后我们考虑二分完了答案\(x\)怎么判定。把值离散化一下然后用一个线段树来维护\(T_i\)(表示当前还没有被预定的大于等于\(i\)的数有多少个),然后判定答案就看到\(x\)的前缀区间是否都不小于\(p\)所在子树的大小。同时注意顺次枚举每个点的时候要去除他对他父亲的影响,然后每次一个点确定是什么值了也要修改对应的前缀区间。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
using R = long double;
const int maxn = 500005;
const int maxno = maxn << 2;
int n; R k;
int minv[maxno], addv[maxno];
void maintain(int o) {
  int lc = o << 1, rc = o << 1 | 1;
  minv[o] = std::min(minv[lc], minv[rc]);
}
void paint(int o, int v) {
  addv[o] += v; minv[o] += v;
}
void pushdown(int o) {
  if(addv[o] != 0) {
    int lc = o << 1, rc = o << 1 | 1;
    paint(lc, addv[o]); paint(rc, addv[o]);
    addv[o] = 0;
  }
}

int left[maxn];
void build_tree(int o, int L, int R) {
  // addv[o] = 0;
  if(L == R) {
    minv[o] = left[L];
  } else {
    int M = (L + R) / 2;
    build_tree(o << 1, L, M);
    build_tree(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
void update(int o, int L, int R, int ql, int qr, int v) {
  if(ql <= L && R <= qr) {
    paint(o, v);
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    if(ql <= M) update(o << 1, L, M, ql, qr, v);
    if(qr > M) update(o << 1 | 1, M + 1, R, ql, qr, v);
    maintain(o);
  }
}
const int INF = 0x7f7f7f7f;
int query_min(int o, int L, int R, int ql, int qr) {
  if(ql <= L && R <= qr) {
    return minv[o];
  } else {
    pushdown(o);
    int M = (L + R) / 2, ans = INF;
    if(ql <= M) ans = std::min(ans, query_min(o << 1, L, M, ql, qr));
    if(qr > M) ans = std::min(ans, query_min(o << 1 | 1, M + 1, R, ql, qr));
    return ans;
  }
}

int d[maxn], d2[maxn];
int lsiz;
void process() {
  std::sort(d + 1, d + 1 + n);
  std::sort(d2 + 1, d2 + 1 + n);
  lsiz = std::unique(d2 + 1, d2 + 1 + n) - d2 - 1;
  for(int i = 1; i <= n; i ++) {
    d[i] = std::lower_bound(d2 + 1, d2 + 1 + lsiz, d[i]) - d2;
    left[d[i]] ++;
  }
  for(int i = lsiz - 1; i >= 1; i --) {
    left[i] += left[i + 1];
  }
  build_tree(1, 1, lsiz);
}
int A[maxn], siz[maxn];
void solve() {
  for(int i = n; i >= 1; i --) {
    siz[i] ++;
    int f = (int)floor((R(i)) / k);
    siz[f] += siz[i];
  }
  for(int i = 1; i <= n; i ++) {
    int f = (int)floor((R(i)) / k);
    if(f > 0) {
      update(1, 1, lsiz, 1, A[f], siz[i]);
    }
    int L = (f == 0) ? 1 : A[f], R = lsiz, ret;
    while(true) {
      if(R - L <= 3) {
        for(int j = R; j >= L; j --) {
          if(query_min(1, 1, lsiz, 1, j) >= siz[i]) {
            ret = j; break;
          }
        }
        break;
      }
      int M = L + (R - L) / 2;
      if(query_min(1, 1, lsiz, 1, M) >= siz[i]) {
        L = M;
      } else {
        R = M;
      }
    }
    A[i] = ret; update(1, 1, lsiz, 1, ret, -siz[i]);
  }
}

int main() {
  scanf("%d%Lf", &n, &k);
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &d[i]); d2[i] = d[i];
  }
  process(); solve();
  for(int i = 1; i <= n; i ++) {
    if(i > 1) putchar(' ');
    printf("%d", d2[A[i]]);
  }
  puts(""); return 0;
}

[LibreOJ 2383][HNOI2013]游走

本野蛮人竟然没做过高消期望DP,,,泪,流了下来,,,

根据期望线性性,答案就是所有边的期望被走的次数乘上边的编号的和。一条边期望经过的次数可以根据他两个端点期望经过的次数来算(但是\(n\)要特判一下),要求所有点期望走过的次数当然就可以列\(n\)个方程然后高消力。然后期望走的次数多的边编号应该小,反之亦然,所以求完每条边走的次数的期望之后就贪心一下就好力。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <utility>
#include <cmath>
const int maxn = 505;
const int maxm = maxn * maxn;
using R = double;
const R eps = 1e-9;
int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    return ((x < 0.00) ? -1 : 1);
  }
}
R D[maxn][maxn];
int n;
void gauss() {
#ifdef LOCAL
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n + 1; j ++) {
      printf("%.3lf ", D[i][j]);
    }
    puts("");
  }
#endif
  for(int i = 1; i <= n; i ++) {
    int r = i;
    for(int j = i + 1; j <= n; j ++) {
      if(fabs(D[j][i]) > fabs(D[r][i])) {
        r = j;
      }
    }
    assert(sign(D[r][i]) != 0);
    if(r != i) {
      for(int j = 1; j <= n + 1; j ++) {
        std::swap(D[i][j], D[r][j]);
      }
    }
    for(int k = i + 1; k <= n; k ++) {
      R rate = D[k][i] / D[i][i];
      for(int j = i; j <= n + 1; j ++) {
        D[k][j] -= D[i][j] * rate;
      }
    }
  }
  for(int i = n; i >= 1; i --) {
    for(int j = i + 1; j <= n; j ++) {
      D[i][n + 1] -= D[j][n + 1] * D[i][j];
      D[i][j] = 0;
    }
    D[i][n + 1] /= D[i][i]; D[i][i] = 1;
#ifdef LOCAL
    printf("E[%d] : %.3lf\n", i, D[i][n + 1]);
#endif
  }
}

int E[maxm][2], deg[maxn];
R tms[maxm];
void add_edge(int u, int v) {
  if(u != n) D[v][u] += 1.00 / (R(deg[u]));
}

int main() {
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i ++) {
    D[i][i] = -1;
  }
  D[1][n + 1] = -1;
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d", &E[i][0], &E[i][1]);
    deg[E[i][0]] ++; deg[E[i][1]] ++;
  }
  for(int i = 1; i <= m; i ++) {
    int u = E[i][0], v = E[i][1];
    add_edge(u, v); add_edge(v, u);
  }
  gauss();
  for(int i = 1; i <= m; i ++) {
    tms[i] = 0;
    int u = E[i][0], v = E[i][1];
    if(u != n) tms[i] += D[u][n + 1] / (R(deg[u]));
    if(v != n) tms[i] += D[v][n + 1] / (R(deg[v]));
  }
  std::sort(tms + 1, tms + 1 + m, [&](const R &i, const R &j) { return i > j; });
  R ans = 0;
  for(int i = 1; i <= m; i ++) {
    ans += tms[i] * (R(i));
  }
  printf("%.3lf\n", ans);
  return 0;
}

[LibreOJ 2182][SDOI2015]寻宝游戏

很多人说事动态虚树……其实也不算是吧,虽然这个东西用力虚树的思路惹。

第一个想到的思路……就事动态的维护虚树,然后虚树上所有边的长度乘二就事答案。然后我们考虑一点……虚树求的时候需要对DFS序(严格来说事欧拉序)排序,所以我们大致可以认为,虚树上做欧拉回路的本质就事按照DFS序扫描,换言之就事DFS一遍,然后进入和回溯事都把边记录到答案里,这个值也就事虚树上按DFS序排序之后两两相邻点的距离的和(首尾也要额外算一遍)。

然后这样一来,我们发现虚树上的非关键点就可以删掉了。因为非关键点也就是所有两两在DFS序中相邻的关键点的LCA,然后那两个关键点的距离也就等于他们到这个非关键点的距离的和。因此我们不需要维护非关键点,问题就简单了许多……

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
const int maxn = 100005;
using ll = long long;
using pii = std::pair<int, ll>;
std::vector<pii> G[maxn];
void add_edge(int u, int v, ll w) {
  G[u].push_back(pii(v, w));
}
void ins_edge(int u, int v, ll w) {
  add_edge(u, v, w); add_edge(v, u, w);
}

int anc[maxn][17];
int dep[maxn], dfn[maxn]; ll dis[maxn];
int dcnt = 0;
void dfs(int x, int fa = -1) {
  anc[x][0] = fa; dfn[x] = ++ dcnt;
  for(auto &e : G[x]) {
    int v = e.first; ll w = e.second;
    if(v != fa) {
      dep[v] = dep[x] + 1;
      dis[v] = dis[x] + w;
      dfs(v, x);
    }
  }
}
int n;
void process() {
  memset(anc, -1, sizeof(anc)); dfs(1);
  for(int j = 1; (1 << j) < n; j ++) {
    for(int i = 1; i <= n; i ++) {
      int a = anc[i][j - 1];
      if(a != -1) {
        anc[i][j] = anc[a][j - 1];
      }
    }
  }
}
int lca(int u, int v) {
  if(dep[u] < dep[v]) std::swap(u, v);
  for(int j = 16; j >= 0; j --) {
    int a = anc[u][j];
    if(a != -1 && dep[a] >= dep[v]) {
      u = a;
    }
  }
  if(u == v) return u;
  for(int j = 16; j >= 0; j --) {
    int a1 = anc[u][j], a2 = anc[v][j];
    if(a1 != -1 && a2 != -1 && a1 != a2) {
      u = a1; v = a2;
    }
  }
  return anc[u][0];
}
ll calc_dist(int u, int v) {
  return dis[u] + dis[v] - 2LL * dis[lca(u, v)];
}

// template <typename T>
struct Comp {
  bool operator ()(const int &a, const int &b) const {
    return dfn[a] < dfn[b];
  }
};
ll now = 0LL; std::set<int, Comp> S;
bool sta[maxn];
void add(int p) {
  auto suc = S.upper_bound(p);
  if(suc != S.begin()) {
    auto pre = -- suc; ++ suc;
    now += calc_dist(*pre, p);
    if(suc != S.end()) {
      now -= calc_dist(*pre, *suc);
    }
  }
  if(suc != S.end()) {
    now += calc_dist(*suc, p);
  }
  S.insert(p);
}
void del(int p) {
  auto suc = S.upper_bound(p);
  if(suc != S.end()) {
    now -= calc_dist(*suc, p);
  }
  if((*S.begin()) != p) {
    -- suc; -- suc;
    int prev = *suc;
    now -= calc_dist(prev, p);
    ++ suc; ++ suc;
    if(suc != S.end()) {
      now += calc_dist(prev, *suc);
    }
  }
  S.erase(p);
}
ll query() {
  if(S.size() <= 1) return 0LL;
  ll ret = now;
  auto las = S.end(); -- las;
  ret += calc_dist(*S.begin(), *las);
  return ret;
}

int main() {
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= n - 1; i ++) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    ins_edge(u, v, w);
  }
  process();
  while(m --) {
    int x; scanf("%d", &x);
    if(sta[x]) {
      del(x);
    } else {
      add(x);
    }
    sta[x] = !sta[x];
    printf("%lld\n", query());
  }
  return 0;
}

[LibreOJ 6436][PKUSC2018]神仙的游戏

考场上写炸了FFT的zzs事野蛮人(确信)

兄啊这题怎么还卡常啊!

不妨设\(n = |S|\)。那么如果串有一个长度为$i$的border,就意味着串有一个长度为\(n - i\)的循环节。

那么考虑有两个非?的位置\(i\)和\(j\)(不妨设\(i < j\)),且\(S_i\neq S_j\)。那么我们设\(l = j - i\),则\(l\)的约数都不能成为循环节的长度,否则会出现矛盾(一个位置又要是0又要是1)。

那么考虑对于所有可能的\(l\)判定是否存在这种不合法的\(i\)与\(j\)。我们利用编辑距离函数:

\[f_l = \sum_{i} A_i A_{i + l}(A_i - A_{i + l})^2\]

这里\(A_i\)相当于\(S_i\)的一个重编码,\(S_i\)为?时应当为0,其他情况一种为1一种为2。这个函数不方便我们卷积,所以我们考虑把\(A\)翻转一下(新的序列称为\(B\)):

\[
\begin{aligned}
f_l &= \sum_{i} B_{n - i - 1} A_{i + l}(B_{n - i - 1} A_{i + l})^2\\
&= \sum_{i} B_{n - i - 1}^3 A_{i + l} - 2B_{n - i - 1}^2 A_{i + l}^2 + B_{n - i - 1}A_{i + l}^3
\end{aligned}\]

然后问题变成了三个卷积。FFT一下就行了(请注意IDFT只需要一次……否则会被卡常)。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cmath>
#include <complex>
#include <vector>
using R = double;
struct C {
  R x, y;
  C(R xx = 0.00, R yy = 0.00) {
    x = xx; y = yy;
  }
  R real() {
    return x;
  }
};
C operator +(const C &a, const C &b) {
  return C(a.x + b.x, a.y + b.y);
}
C operator -(const C &a, const C &b) {
  return C(a.x - b.x, a.y - b.y);
}
C operator *(const C &a, const C &b) {
  return C(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}

using ll = long long;
constexpr R pi = acos(-1);
int flip(int bi, int x) {
  int ret = 0;
  for(int i = 0; i < bi; i ++) {
    if(x & (1 << i)) {
      ret += (1 << (bi - i - 1));
    }
  }
  return ret;
}
void FFT(C *A, int bi, R flag = 1.00) {
  int n = 1 << bi;
  for(int i = 0; i < n; i ++) {
    int v = flip(bi, i);
    if(i < v) std::swap(A[v], A[i]);
  }
  for(int L = 1; L < n; L <<= 1) {
    R rd = pi / (R(L));
    C xi_n(cos(rd), sin(flag * rd));
    for(int j = 0; j < n; j += (L << 1)) {
      C xi(1.00, 0.00);
      for(int i = j; i < j + L; i ++) {
        C x = A[i], y = A[i + L];
        A[i] = x + xi * y;
        A[i + L] = x - xi * y;
        xi = xi * xi_n;
      }
    }
  }
}

const int maxn = 500005;
R tot[maxn];
C T[maxn << 2], TT[maxn << 2], D[maxn << 2];

char S[maxn];
inline int conv(char c) {
  if(c == '1') return 2;
  if(c == '0') return 1;
  return 0;
}
int A[maxn], B[maxn];
bool boom[maxn];
int main() {
  scanf("%s", S); int n = strlen(S);
  for(int i = 0; i < n; i ++) {
    A[i] = B[n - 1 - i] = conv(S[i]);
  }
  
  int len = 1, bi = 0;
  while(len < (2 * n)) {
    len <<= 1; bi ++;
  }
  
  C z(0.00, 0.00);
  // std::fill(T, T + len, z);
  // std::fill(TT, TT + len, z);
  for(int i = 0; i < n; i ++) {
    T[i] = A[i] * A[i] * A[i]; TT[i] = B[i];
  }
  FFT(T, bi); FFT(TT, bi);
  for(int i = 0; i < len; i ++) {
    D[i] = D[i] + (T[i] * TT[i]);
  }
  
  std::fill(T, T + len, z);
  std::fill(TT, TT + len, z);
  for(int i = 0; i < n; i ++) {
    T[i] = A[i] * A[i]; TT[i] = B[i] * B[i];
  }
  FFT(T, bi); FFT(TT, bi);
  for(int i = 0; i < len; i ++) {
    D[i] = D[i] + C(-2.00, 0.00) * (T[i] * TT[i]);
  }
  
  std::fill(T, T + len, z);
  std::fill(TT, TT + len, z);
  for(int i = 0; i < n; i ++) {
    T[i] = A[i]; TT[i] = B[i] * B[i] * B[i];
  }
  FFT(T, bi); FFT(TT, bi);
  for(int i = 0; i < len; i ++) {
    D[i] = D[i] + (T[i] * TT[i]);
  }
  FFT(D, bi, -1.00);
  
  for(int i = 1; i < n; i ++) {
    if(fabs(D[n - 1 + i].real() / (R(len))) > 0.99) {
      boom[i] = true;
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(int j = i * 2; j <= n; j += i) {
      boom[i] = (boom[i] || boom[j]);
    }
  }
  ll ret = 0LL;
  for(int i = 1; i <= n; i ++) {
    if(!boom[n - i]) {
      ret ^= (ll(i)) * (ll(i));
    }
  }
  printf("%lld\n", ret);
  return 0;
}

[LibreOJ 2562][SDOI2018]战略游戏

aji圆方树毁我青春,,,省选现场看出来是圆方树但写不出点双滚粗。

显然可以割的点是某两个点的某一条简单路径上的割点,然后两点间的简单路劲的并就是圆方树上的路径,割点在圆方树上就是非叶子的圆点。我们求所有两点路径的并,就需要虚树。

然后做完了……直接建圆方树,每次询问建虚树xjb统计即可。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
const int maxn = 100005;
const int maxm = 200005;
std::vector<int> G[maxn];
void cz1() {
  for(int i = 0; i < maxn; i ++) {
    G[i].clear();
  }
}
void add_edge1(int u, int v) {
  G[u].push_back(v); G[v].push_back(u);
}

using pii = std::pair<int, int>;
int dcnt, bcc_cnt; int pre[maxn]; bool iscut[maxn];
int bccno[maxn]; std::vector<int> bcc[maxm];
int dfs(int x, int fa = -1) {
  static std::stack<pii> S;
  pre[x] = ++ dcnt; int low = pre[x];
  int cld = 0;
  for(auto v : G[x]) {
    pii e = std::make_pair(x, v);
    if(!pre[v]) {
      S.push(e); cld ++;
      int lowv = dfs(v, x);
      low = std::min(low, lowv);
      if(lowv >= pre[x]) {
        iscut[x] = true; bcc_cnt ++;
        bcc[bcc_cnt].clear();
        while(true) {
          pii ee = S.top(); S.pop();
          int f = ee.first, g = ee.second;
          if(bccno[f] != bcc_cnt) {
            bccno[f] = bcc_cnt;
            bcc[bcc_cnt].push_back(f);
          }
          if(bccno[g] != bcc_cnt) {
            bccno[g] = bcc_cnt;
            bcc[bcc_cnt].push_back(g);
          }
          if(f == x && g == v) break;
        }
      }
    } else if(pre[v] < pre[x] && v != fa) {
      S.push(e);
      low = std::min(low, pre[v]);
    }
  }
  return low;
}
int n, m;
void calc_bcc() {
  std::fill(pre, pre + 1 + n, 0);
  std::fill(iscut, iscut + 1 + n, false);
  std::fill(bccno, bccno + 1 + m, 0);
  dcnt = bcc_cnt = 0;
  for(int i = 1; i <= n; i ++) {
    if(!pre[i]) dfs(i);
  }
}

std::vector<int> G2[maxn + maxm];
void cz2() {
  for(int i = 0; i < maxn + maxm; i ++) G2[i].clear();
}
void add_edge2(int u, int v) {
  G2[u].push_back(v); G2[v].push_back(u);
}

int anc[maxn + maxm][19], dep[maxn + maxm], d[maxn + maxm];
int dfn[maxn + maxm], siz[maxn + maxm];
int cnt2;
void dfs_tree(int x, int fa = -1, int depth = 0, int s = 0) {
#ifdef LOCAL
  printf("V (%d, %d, %d, %d)\n", x, fa, depth, s);
#endif
  cnt2 ++; dfn[x] = cnt2; siz[x] = 1;
  d[x] = s; anc[x][0] = fa; dep[x] = depth;
  for(auto v : G2[x]) {
    if(v != fa) {
      dfs_tree(v, x, depth + 1, s + ((v <= n) ? 1 : 0));
      siz[x] += siz[v];
    }
  }
}
void process_lca() {
  memset(anc, -1, sizeof(anc));
  cnt2 = 0;
  int s = bcc_cnt + n; dfs_tree(n + 1);
#ifdef LOCAL
  printf("s : %d\n", s);
#endif
  for(int j = 1; (1 << j) < s; j ++) {
    for(int i = 1; i <= s; i ++) {
      int a = anc[i][j - 1];
      if(a != -1) anc[i][j] = anc[a][j - 1];
    }
  }
}
int lca(int x, int y) {
  if(dep[x] < dep[y]) std::swap(x, y);
  for(int j = 18; j >= 0; j --) {
    int a = anc[x][j];
    if(a != -1 && dep[a] >= dep[y]) {
      x = a;
    }
  }
  if(x == y) return x;
  for(int j = 18; j >= 0; j --) {
    int a1 = anc[x][j], a2 = anc[y][j];
    if(a1 != -1 && a2 != -1 && a1 != a2) {
      x = a1; y = a2;
    }
  }
  return anc[x][0];
}

void process() {
  calc_bcc();
  cz2();
  for(int i = 1; i <= bcc_cnt; i ++) {
    int id = n + i;
    for(auto u : bcc[i]) {
      add_edge2(u, id);
    }
  }
  process_lca();
}
int get_delta(int x, int y) { // y is x's ancestor.
  return (d[anc[x][0]] - d[y]);
}
bool is_anc(int fa, int bef) {
  int l1 = dfn[fa], r1 = dfn[fa] + siz[fa] - 1;
  int l2 = dfn[bef], r2 = dfn[bef] + siz[bef] - 1;
  return (l1 <= l2 && r2 <= r1);
}
int query(int sz) {
  std::vector<int> V;
  for(int i = 1; i <= sz; i ++) {
    int x; scanf("%d", &x);
    V.push_back(x);
  }
  std::sort(V.begin(), V.end(), [&](const int &i, const int &j) {
    return dfn[i] < dfn[j];
  });
  std::set<int> ds; ds.insert(V[0]);
  for(int i = 1; i < sz; i ++) {
    ds.insert(V[i]);
    ds.insert(lca(V[i - 1], V[i]));
  }
  V.clear(); for(auto u : ds) V.push_back(u);
  std::sort(V.begin(), V.end(), [&](const int &i, const int &j) {
    return dfn[i] < dfn[j];
  });
  std::stack<int> S;
  int ans = 0;
  for(int i = 0; i < V.size(); i ++) {
    int u = V[i];
    while(!S.empty() && !is_anc(S.top(), u)) {
      S.pop();
    }
    if(!S.empty()) {
#ifdef LOCAL
      printf("ans (%d, %d) : %d\n", u, S.top(), get_delta(u, S.top()));
#endif
      ans += get_delta(u, S.top());
    }
    S.push(u);
  }
  for(auto u : ds) {
    if(u <= n) ans ++;
  }
  ans -= sz;
  return ans;
}

int main() {
  int T; scanf("%d", &T);
  while(T --) {
    scanf("%d%d", &n, &m); cz1();
    for(int i = 1; i <= m; i ++) {
      int u, v; scanf("%d%d", &u, &v);
      add_edge1(u, v);
    }
    process();
    int q; scanf("%d", &q);
    while(q --) {
      int sz; scanf("%d", &sz);
      printf("%d\n", query(sz));
#ifdef LOCAL
      fflush(stdout);
#endif
    }
  }
  return 0;
}

[LibreOJ 121]可离线动态图连通性

LCT+扫描线应该随便做吧这题……但我学了一下线段树分治

这个问题有删除非常的恶心,让我们考虑怎么去掉删除的影响。

每条边存在的时间段是一个区间,而区间在线段树上可以被表示为\(O(\log n)\)个区间。然后我们以时间为下标,对所有询问建线段树,然后对一段区间加边就是一个区间打标记,最后扫一遍线段树就可以解决问题。

同时需要注意,这个题在DFS线段树的过程中,往父亲回溯的时候是需要撤销之前的操作的。这样的话我们的并查集就不能使用路径压缩,但是可以按轶合并。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
const int maxn = 5005;
const int maxm = 500005;
using pii = std::pair<int, int>;
struct Node {
  Node *fa; int siz;
  Node() {
    fa = NULL; siz = 1;
  }
  void sc(Node *c) {
    siz += c -> siz;
    c -> fa = this;
  }
  void brk() {
    fa -> siz -= siz;
    fa = NULL;
  }
};
Node *r[maxn];
int n;
void init_set() {
  for(int i = 1; i <= n; i ++) {
    r[i] = new Node();
  }
}
Node *get_fa(Node *x) {
  if(x -> fa == NULL) {
    return x;
  } else {
    return get_fa(x -> fa);
  }
}
Node *link_set(Node *x, Node *y) {
  if(x -> siz < y -> siz) std::swap(x, y);
  x -> sc(y); return y;
}
Node *merge_set(Node *x, Node *y) {
  return link_set(get_fa(x), get_fa(y));
}
bool is_same(Node *x, Node *y) {
  return (get_fa(x) == get_fa(y));
}

const int maxno = maxm << 2;
std::vector<pii> event[maxno];
void add_event(int o, int L, int R, int ql, int qr, const pii &e) {
  if(ql <= L && R <= qr) {
    event[o].push_back(e);
  } else {
    int M = (L + R) / 2;
    if(ql <= M) add_event(o << 1, L, M, ql, qr, e);
    if(qr > M) add_event(o << 1 | 1, M + 1, R, ql, qr, e);
  }
}
pii que[maxno];
void add_query(int o, int L, int R, int p, const pii &e) {
  if(L == R) {
    que[o] = e;
  } else {
    int M = (L + R) / 2;
    if(p <= M) {
      add_query(o << 1, L, M, p, e);
    } else {
      add_query(o << 1 | 1, M + 1, R, p, e);
    }
  }
}
int ret[maxno];
std::stack<std::pair<Node*, int> > S;
void solve(int o, int L, int R) {
  for(auto e : event[o]) {
    int u = e.first, v = e.second;
    if(!is_same(r[u], r[v])) {
#ifdef LOCAL
      printf("Merging %d and %d.\n", u, v);
#endif
      S.push(std::make_pair(merge_set(r[u], r[v]), o));
    }
  }
  if(L == R) {
    int u = que[o].first, v = que[o].second;
    if(u == -1 && v == -1) {
      ret[L] = -1;
    } else {
      if(is_same(r[u], r[v])) {
        ret[L] = 1;
      } else {
        ret[L] = 0;
      }
    }
  } else {
    int M = (L + R) / 2;
    solve(o << 1, L, M); solve(o << 1 | 1, M + 1, R);
  }
  while(!S.empty() && S.top().second >= o) {
    Node *u = S.top().first; S.pop();
    u -> brk();
  }
}

std::map<pii, std::stack<int> > ma;
std::vector<pii> V;
int main() {
  int m; scanf("%d%d", &n, &m);
  init_set();
  pii fl(-1, -1);
  for(int i = 1; i <= m; i ++) {
    pii e; int op;
    scanf("%d%d%d", &op, &e.first, &e.second);
    if(e.first > e.second) {
      std::swap(e.first, e.second);
    }
    if(op == 2) {
      add_query(1, 1, m, i, e);
    } else {
      add_query(1, 1, m, i, fl);
      V.push_back(e);
      if(op == 0) {
        ma[e].push(i);
      } else {
        int last = ma[e].top(); ma[e].pop();
        add_event(1, 1, m, last, i - 1, e);
      }
    }
  }
  for(auto e : V) {
    while(!ma[e].empty()) {
      int g = ma[e].top(); ma[e].pop();
      add_event(1, 1, m, g, m, e);
    }
  }
  solve(1, 1, m);
  for(int i = 1; i <= m; i ++) {
    if(ret[i] != -1) {
      if(ret[i]) {
        puts("Y");
      } else {
        puts("N");
      }
    }
  }
  return 0;
}

[LibreOJ 2558][LNOI2014]LCA

现在才做这题TAT

如果询问的是一个子集和\(z\)的所有LCA的深度的和,那可以把子集里每一个元素到根的路径全部加1,然后根到\(z\)的路径上的和就是答案。

如果是区间的话,每次都扫一次整个区间一定会T……所以考虑把区间拆成两个前缀区间,然后离线,给询问排个序然后就好做了。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
const int maxn = 50005;
using ll = long long;
const ll ha = 201314LL;
std::vector<int> G[maxn];
void add_edge(int u, int v) {
  G[u].push_back(v);
  G[v].push_back(u);
}

const int maxno = maxn << 2;
ll sumv[maxno], addv[maxno];
void maintain(int o) {
  sumv[o] = (sumv[o << 1] + sumv[o << 1 | 1]) % ha;
}
void paint(int o, int L, int R, ll v) {
  v %= ha;
  addv[o] += v; addv[o] %= ha;
  sumv[o] += (v * (ll(R - L + 1))) % ha; sumv[o] %= ha;
}
void pushdown(int o, int L, int R) {
  if(addv[o] != 0LL) {
    ll v = addv[o]; addv[o] = 0;
    int M = (L + R) / 2;
    int lc = o << 1, rc = o << 1 | 1;
    paint(lc, L, M, v); paint(rc, M + 1, R, v);
  }
}
int ql, qr; ll v;
void modify(int o, int L, int R) {
  if(ql <= L && R <= qr) {
    paint(o, L, R, v);
  } else {
    pushdown(o, L, R);
    int M = (L + R) / 2;
    if(ql <= M) modify(o << 1, L, M);
    if(qr > M) modify(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
ll query(int o, int L, int R) {
  if(ql <= L && R <= qr) {
    return sumv[o];
  } else {
    pushdown(o, L, R);
    int M = (L + R) / 2;
    ll ans = 0;
    if(ql <= M) ans = (ans + query(o << 1, L, M)) % ha;
    if(qr > M) ans = (ans + query(o << 1 | 1, M + 1, R)) % ha;
    return ans;
  }
}

int siz[maxn], fa[maxn], dep[maxn], hson[maxn];
void dfs_1(int x, int f = 0, int depth = 0) {
  fa[x] = f; dep[x] = depth; siz[x] = 1;
  int maxs = 0;
  for(auto v : G[x]) {
    if(v != f) {
      dfs_1(v, x, depth + 1);
      siz[x] += siz[v];
      if(siz[v] > maxs) {
        maxs = siz[v]; hson[x] = v;
      }
    }
  }
}
int top[maxn], tid[maxn], dfn[maxn];
void dfs_2(int x, int a) {
  static int cnt = 0; cnt ++;
  top[x] = a; tid[cnt] = x; dfn[x] = cnt;
  if(hson[x]) {
    dfs_2(hson[x], a);
  } else {
    return;
  }
  for(auto v : G[x]) {
    if(v != fa[x] && v != hson[x]) {
      dfs_2(v, v);
    }
  }
}

int n;
void update(int x, int y, const ll &delta) {
  if(top[x] == top[y]) {
    if(dfn[x] > dfn[y]) std::swap(x, y);
    ql = dfn[x], qr = dfn[y]; v = delta;
    modify(1, 1, n); return;
  }
  if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
  ql = dfn[top[x]], qr = dfn[x]; v = delta;
  modify(1, 1, n);
  update(fa[top[x]], y, delta);
}
ll query(int x, int y) {
  if(top[x] == top[y]) {
    if(dfn[x] > dfn[y]) std::swap(x, y);
    ql = dfn[x], qr = dfn[y];
    return query(1, 1, n);
  }
  if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
  ql = dfn[top[x]], qr = dfn[x];
  ll ret = query(1, 1, n);
  return (ret + query(fa[top[x]], y)) % ha;
}

struct Q {
  int l, z;
  int id; ll p;
  bool operator <(const Q &res) const {
    if(l == res.l) {
      return id < res.id;
    } else {
      return l < res.l;
    }
  }
};
Q que[maxn << 1];
ll ans[maxn];

int main() {
  int q; scanf("%d%d", &n, &q);
  for(int i = 2; i <= n; i ++) {
    int f; scanf("%d", &f); f ++;
    add_edge(f, i);
  }
  dfs_1(1); dfs_2(1, 1);
  for(int i = 1; i <= q; i ++) {
    int l, r, z; scanf("%d%d%d", &l, &r, &z);
    l ++; r ++; z ++;
    Q &L = que[i * 2 - 1]; Q &R = que[i * 2];
    L.id = R.id = i; L.p = -1; R.p = 1;
    L.z = R.z = z; L.l = l - 1; R.l = r;
  }
  std::sort(que + 1, que + 1 + 2 * q);
  int p = 0;
  for(int i = 1; i <= 2 * q; i ++) {
    const Q &t = que[i];
    while(p < t.l) {
      p ++; update(1, p, 1);
    }
    ans[t.id] = (ans[t.id] + t.p * query(1, t.z) + ha) % ha;
  }
  for(int i = 1; i <= q; i ++) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}

[LibreOJ 2137][ZJOI2015]诸神眷顾的幻想乡

复习SAM了呢~

那个度数为1的点至多有20个的条件非常神奇……让我们想想怎么用。

我们发现,(钦定根后)在树上有一条路径是弯的这种情况非常不好统计,但如果是直着下来就很好说(把所有从根到一个点的路径扔到SAM里,然后是经典题)。但是,任何一条路一定会在某个度数为1的点为根的情况下是直的(可以意会一下吧(逃

然后我们从那20个点每个点当根DFS一遍,把搞出来的每一条从根开始的路径放前缀Trie里。然后对前缀Trie构一个SAM就行啦~

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
const int BUFSIZE = 128 * 1024 * 1024;
char buf[BUFSIZE];
void *alloc(size_t size) {
  static char *cur = buf;
  if(cur - buf + size > BUFSIZE) {
    return malloc(size);
  } else {
    char *ret = cur; cur += size;
    return ret;
  }
}

const int maxn = 100005;
std::vector<int> G[maxn];
int deg[maxn];

int ssiz;
struct TNode {
  TNode *ch[10];
};
TNode *alloc_tn() {
  auto ret = (TNode*)alloc(sizeof(TNode));
  memset(ret -> ch, 0, sizeof(ret -> ch));
  return ret;
}
TNode *step(TNode *o, int c) {
  if(!(o -> ch[c])) {
    o -> ch[c] = alloc_tn();
  }
  return (o -> ch[c]);
}
TNode *trt;
int col[maxn];
void dfs(int x, int fa, TNode *last) {
  TNode *np = step(last, col[x]);
  for(auto v : G[x]) {
    if(v != fa) {
      dfs(v, x, np);
    }
  }
}

struct Node {
  int len; Node *fa;
  Node *ch[10];
};
std::vector<Node*> pool;
Node *alloc_node(int len = 0, Node *fa = NULL) {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> len = len; ret -> fa = fa;
  memset(ret -> ch, 0, sizeof(ret -> ch));
  pool.push_back(ret);
  return ret;
}
Node *rt;
Node *extend(int c, Node *last) {
  Node *np = alloc_node(last -> len + 1);
  Node *p = last;
  while(p != NULL && p -> ch[c] == NULL) {
    p -> ch[c] = np; p = p -> fa;
  }
  if(p == NULL) {
    np -> fa = rt;
  } else {
    Node *q = p -> ch[c];
    if(q -> len == p -> len + 1) {
      np -> fa = q;
    } else {
      Node *nq = alloc_node(p -> len + 1, q -> fa);
      memcpy(nq -> ch, q -> ch, sizeof(q -> ch));
      q -> fa = np -> fa = nq;
      while(p != NULL && p -> ch[c] == q) {
        p -> ch[c] = nq; p = p -> fa;
      }
    }
  }
  return np;
}
void dfs_2(TNode *o, Node *last) {
  for(int i = 0; i < ssiz; i ++) {
    TNode *v = o -> ch[i];
    if(!v) continue;
    Node *np = extend(i, last);
    dfs_2(v, np);
  }
}

using ll = long long;
int main() {
  int n; scanf("%d%d", &n, &ssiz);
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &col[i]);
  }
  trt = alloc_tn();
  for(int i = 1; i <= n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    G[u].push_back(v); G[v].push_back(u);
    deg[u] ++; deg[v] ++;
  }
  for(int i = 1; i <= n; i ++) {
    if(deg[i] == 1) {
      dfs(i, 0, trt);
    }
  }
  rt = alloc_node();
  dfs_2(trt, rt);
  ll ans = 0;
  for(auto p : pool) {
    if(p -> fa) {
      ans += p -> len - p -> fa -> len;
    }
  }
  printf("%lld\n", ans);
  return 0;
}