2021CCPC网络赛

Pro. ID	Problem Title	Solved
7100	Cut The Wire	（赛时）
7101	Time-division Multiplexing	（赛时）
7102	Pattern Recognition	（赛后）
7103	Depth First Search	（赛后）
7104	Easy Math Problem	（赛后）
7105	Power Sum	（赛时）
7106	Function	（赛时）
7107	GCD on Sequence	（赛时）
7108	Command Sequence	（赛时）
7109	Random Walk	（赛后）
7110	Shooting Bricks	（赛时）
7111	Remove	（赛时）
7112	Start Dash ! !

Cut The Wire

Time-division Multiplexing

数据较水，1.1 倍过了。

// Author:  HolyK
// Created: Sat Aug 28 13:37:05 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(105);
char s[N * 12], *p[N], *e[N], t[10000005];
int v[26];
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int _;
  std::cin >> _;
  while (_--) {
    int n;
    std::cin >> n;   
    int len = 1;
    p[0] = e[0] = s;
    for (int i = 1; i <= n; i++) {
      p[i] = e[i - 1];
      std::cin >> p[i];
      e[i] = p[i] + strlen(p[i]);
      int l = e[i] - p[i];
      len = len * l / std::__gcd(len, l);
    }
    len *= 1.1;
    char *o;
    memset(v, 0, sizeof v);
    for (o = s; o < e[n]; o++) v[*o - 'a'] = 1;
    int tot = std::accumulate(v, v + 26, 0);
    o = t;
    for (int i = 0; i < len; i++) {
      for (int j = 1; j <= n; j++) {
        *o++ = *p[j]++;
        if (p[j] == e[j]) p[j] = e[j - 1];
      }
    } 
    int ans = o - t, cnt = 0;
    memset(v, 0, sizeof v);
    for (char *i = t, *j = t; i < o; i++) {
      if (1 == ++v[*i - 'a']) cnt++;
      while (cnt == tot) {
        smin(ans, i - j + 1);
        if (0 == --v[*j++ - 'a']) cnt--;
      }
    }
    std::cout << ans << "\n";
  }
  return 0;
}

Pattern Recognition

和多校题差不多，只不过换成了矩阵，只要建出广义 sam 即可。

数据太水，sam 点数太少，爆踩 std。

// Author:  HolyK
// Created: Sun Aug 29 20:49:05 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(4e5 + 5);
struct Sam {
  std::array<int, 26> ch[N];
  int len[N], fa[N], cnt;
  void init() {
    fa[0] = -1;
    len[0] = 0;
    for (int i = 0; i <= cnt; i++) {
      ch[i].fill(0);
    }
    cnt = 0;
  }
  int ins(int last, int x) {
    if (ch[last][x] && len[last] + 1 == len[ch[last][x]]) return ch[last][x];
    int p = last, np = ++cnt, q;
    len[np] = len[p] + 1;
    for (; ~p && !ch[p][x]; p = fa[p]) ch[p][x] = np;
    if (p == -1) {
      fa[np] = 0;
    } else if (len[q = ch[p][x]] == len[p] + 1) {
      fa[np] = q;
    } else {
      int nq = p == last ? np : ++cnt;
      len[nq] = len[p] + 1;
      ch[nq] = ch[q];
      for (; ~p && ch[p][x] == q; p = fa[p]) ch[p][x] = nq;
      fa[np] = nq;
      fa[nq] = fa[q];
      fa[q] = nq;    
    }
    return np;
  }
} a, b;
int n, m, q;
struct Node {
  Node *ls, *rs;
  int w;
} t[N * 50], *cur;
void ins(Node *&o, int l, int r, int x) {
  if (!o) o = cur++, *o = {nullptr, nullptr, 0};
  o->w++;
  if (l == r) return;
  int m = l + r >> 1;
  x <= m ? ins(o->ls, l, m, x) : ins(o->rs, m + 1, r, x);
}
int ask(Node *o, int l, int r, int x, int y) {
  if (!o || r < x || y < l) return 0;
  if (x <= l && r <= y) return o->w;
  int m = l + r >> 1;
  return ask(o->ls, l, m, x, y) + ask(o->rs, m + 1, r, x, y);
}
Node *merge(Node *x, Node *y) {
  if (!x) return y;
  if (!y) return x;
  Node *o = cur++;
  o->w = x->w + y->w;
  o->ls = merge(x->ls, y->ls);
  o->rs = merge(x->rs, y->rs);
  return o;
}
Node *root[N];
std::vector<int> g[N];
int in[N], out[N], cnt;
void dfs1(int x) {
  in[x] = ++cnt;
  for (int y : g[x]) {
    dfs1(y);
  }
  out[x] = cnt;
}
void dfs2(int x) {
  for (int y : g[x]) {
    dfs2(y);
    root[x] = merge(root[x], root[y]);
  }
}
void solve() {
  cur = t;
  std::cin >> n >> m >> q;
  std::vector<std::string> s(n);
  std::vector<int> pos1(n * m), pos2(n * m), pos3(n * m), pos4(n * m);
  a.init(), b.init();
  for (int i = 0; i < n; i++) {
    std::cin >> s[i];
    for (int j = 0, p = 0; j < m; j++) {
      pos1[i * m + j] = p = a.ins(p, s[i][j] - 'a');
    }
    for (int j = m - 1, p = 0; j >= 0; j--) {
      pos2[i * m + j] = p = a.ins(p, s[i][j] - 'a');
    }
  }
  for (int j = 0; j < m; j++) {
    for (int i = 0, p = 0; i < n; i++) {
      pos3[i * m + j] = p = b.ins(p, s[i][j] - 'a');
    }
    for (int i = n - 1, p = 0; i >= 0; i--) {
      pos4[i * m + j] = p = b.ins(p, s[i][j] - 'a');
    }
  }
  for (int i = 0; i <= a.cnt; i++) {
    g[i].clear();
  }
  for (int i = 1; i <= a.cnt; i++) {
    g[a.fa[i]].push_back(i);
  }
  cnt = -1, dfs1(0);
  for (int i = 0; i <= b.cnt; i++) {
    g[i].clear();
    root[i] = 0;
  }
  for (int i = 0; i < n * m; i++) {
    int x = in[pos1[i]], y = in[pos2[i]];
    assert(x && y);
    ins(root[pos3[i]], 1, cnt, x);
    ins(root[pos3[i]], 1, cnt, y);
    ins(root[pos4[i]], 1, cnt, x);
    ins(root[pos4[i]], 1, cnt, y);
  }
  for (int i = 1; i <= b.cnt; i++) {
    g[b.fa[i]].push_back(i);
  }
  dfs2(0);
  while (q--) {
    std::string s;
    std::cin >> s;
    n = s.size();
    pos1.assign(n, 0);
    for (int i = 0, o = 0; i < n; i++) {
      pos1[i] = o = a.ch[o][s[i] - 'a'];
      if (!o) break;
    }
    pos2.assign(n, 0);
    for (int i = n - 1, o = 0; i >= 0; i--) {
      pos2[i] = o = a.ch[o][s[i] - 'a'];
      if (!o) break;
    }
    pos3.assign(n, 0);
    for (int i = 0, o = 0; i < n; i++) {
      pos3[i] = o = b.ch[o][s[i] - 'a'];
      if (!o) break;
    }
    pos4.assign(n, 0);
    for (int i = n - 1, o = 0; i >= 0; i--) {
      pos4[i] = o = b.ch[o][s[i] - 'a'];
      if (!o) break;
    }
    int ans = 0, ans1 = 0;
    if (n == 1 && pos1[0] && pos4[0]) {
      ans1 = ask(root[pos4[0]], 1, cnt, in[pos1[0]], out[pos1[0]]);
    }
    for (int i = 0; i + 1 < n; i++) {
      if (pos1[i] && pos4[i]) {
        (i ? ans : ans1) += ask(root[pos4[i]], 1, cnt, in[pos1[i]], out[pos1[i]]);
      }
      if (pos2[i] && pos3[i]) {
        (i ? ans : ans1) += ask(root[pos3[i]], 1, cnt, in[pos2[i]], out[pos2[i]]);
      }
    }
    ans += ans1 / 2;
    auto t = s;
    std::reverse(t.begin(), t.end());
    if (t == s) ans /= 2;
    std::cout << ans << "\n";
  }
}
int main() {
  // freopen("t.in", "r", stdin);
  // freopen(".out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int t;
  std::cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

Depth First Search

拆点，LCT。

// Author:  HolyK
// Created: Sun Aug 29 16:57:07 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
inline char gc() {
  static constexpr int BufferSize = 1 << 22 | 5;
  static char buf[BufferSize], *p, *q;
  static std::streambuf *i = std::cin.rdbuf();
  return p == q ? p = buf, q = p + i->sgetn(p, BufferSize), p == q ? EOF : *p++ : *p++;
}
struct Reader {
  template <class T>
  Reader &operator>>(T &w) {
    char c, p = 0;
    for (; !std::isdigit(c = gc());) if (c == '-') p = 1;
    for (w = c & 15; std::isdigit(c = gc()); w = w * 10 + (c & 15)) ;
    if (p) w = -w;
    return *this;
  }
} cin;

constexpr int N(4e5 + 5);
struct Node {
  Node *ch[2], *fa;
#define ls ch[0]
#define rs ch[1]
  
  int dir() const { return this == fa->rs; }
  bool nrt() const { return fa && (this == fa->ls || this == fa->rs); }
  void sch(int d, Node *x) {
    ch[d] = x;
    if (x) x->fa = this;
  }
  void rotate() {
    Node *p = fa;
    int k = dir();
    fa = p->fa;
    if (p->nrt()) fa->ch[p->dir()] = this;
    p->sch(k, ch[!k]), sch(!k, p);
    p->pushup();
    // pushup();
  }
  void splay() {
    for (; nrt(); rotate()) {
      if (fa->nrt()) {
        (dir() == fa->dir() ? fa : this)->rotate();
      }
    }
    pushup();
  }
  void access() {
    for (splay(), rs = nullptr; fa; rotate()) {
      fa->splay(), fa->rs = this;
    }
    pushup();
  }
  void link(Node *p) {
    p->access();
    fa = p;
  }
  void cut() {
    access();
    if (ls) ls->fa = nullptr, ls = nullptr, pushup();
  }
  LL sum;
  int max, val, id;
  void pushup() {
    sum = max = val;
    if (ls) sum += ls->sum, smax(max, ls->max);
    if (rs) sum += rs->sum, smax(max, rs->max);
  }
} t[N * 2], *cur;
Node *newNode(int id, int val) {
  cur->ls = cur->rs = cur->fa = 0;
  cur->sum = cur->max = cur->val = val;
  cur->id = id;
  return cur++;
}
std::list<int> bfs;
std::list<int>::iterator iter[N];

Node *r[N * 2][2];
int dep[N];
int expose(int x, int d) {
  Node *o = r[x][0], *p = o;
  o->access();
  int res = 0;
  while (o) {
    p = o;
    if (dep[o->id] - dep[x] == d) {
      res = o->id;
    }
    if (dep[o->id] - dep[x] < d) {
      o = o->ls;
    } else {
      o = o->rs;
    }
  }
  assert(dep[res] - dep[x] == d);
  p->splay();
  return res;
}
int son[N], fa[N];
void solve() {
  cur = t;
  bfs.clear();
  iter[1] = bfs.insert(bfs.end(), 1);
  r[1][0] = newNode(1, 1);
  r[1][1] = newNode(1, 0);
  int q;
  cin >> q;
  for (int i = q + 2, p = 1; i <= q + q + 1; i++) {
    son[p] = 1, fa[i] = p;
    dep[i] = dep[p] + 1;
    r[i][0] = newNode(i, i);
    r[i][1] = newNode(i, 0);
    r[p][0]->link(r[i][0]);
    r[p][1]->link(r[i][0]);
    iter[i] = bfs.insert(bfs.end(), i);
    p = i;
  }
  son[q + q + 1] = 0;
  int key = 0;
  for (int t = 1; t <= q; t++) {
    auto addLeaf = [&](int x) {
      assert(!son[x]);
      int y;
      if (dep[y = *std::prev(iter[x])] == dep[x] && !son[y]) {
        r[y][0]->cut();
        r[y][1]->cut();
        r[y][0]->link(r[x][1]);
        r[y][1]->link(r[x][1]);
      }
      if (dep[y = *std::next(iter[x])] == dep[x]) {
        r[x][0]->link(r[y][1]);
        r[x][1]->link(r[y][1]);
      }
    };
    int opt, x, y, z;
    cin >> opt >> x;
    x ^= key;
    if (opt == 1) {
      cin >> y >> z;
      y ^= key;
      z ^= key;
      dep[x] = dep[y] + 1;
      fa[x] = y;
      son[x] = 0, son[y]++;
      r[x][0] = newNode(x, x);
      r[x][1] = newNode(x, 0);
      if (!z) {
        z = expose(y, 1);
        r[y][0]->cut();
        r[y][1]->cut();
        r[y][0]->link(r[x][0]);
        r[y][1]->link(r[x][0]);
      } else {
        z = *std::next(iter[z]);
      }
      iter[x] = bfs.insert(iter[z], x);
      addLeaf(x);
    } else if (opt == 2) {

      r[x][0]->cut();
      r[x][1]->cut();
      y = *std::prev(iter[x]);
      z = *std::next(iter[x]);
      bfs.erase(iter[x]);
      if (dep[x] == dep[y] && !son[y]) {
        r[y][0]->cut();
        r[y][1]->cut();
        if (dep[y] == dep[z]) {
          r[y][0]->link(r[z][1]);
          r[y][1]->link(r[z][1]);
        }
      }
      son[fa[x]]--;
      if (fa[x] != fa[y]) {
        y = fa[x];
        r[y][0]->cut();
        r[y][1]->cut();
        if (y == fa[z]) {
          r[y][0]->link(r[z][0]);
          r[y][1]->link(r[z][0]);
        } else {
          addLeaf(y);
        }
      }
    } else {
      cin >> z;
      z ^= key;
      LL a;
      int b;
      if (!z) {
        a = b = x;
      } else {
        y = expose(x, z);
        Node *o = r[y][0];
        o->splay();
        assert(o->rs);
        a = o->rs->sum + y;
        b = std::max(o->rs->max, y);
      }
      key = a % b;
      std::cout << a << " " << b << "\n";
    }
  }
}
int main() {
  // freopen("t.in", "r", stdin);
  // freopen(".out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

Easy Math Problem

// Author:  HolyK
// Created: Sat Aug 28 21:36:36 2021
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#include <utility>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
constexpr int P(998244353);
inline void inc(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
inline void dec(int &x, int y) {
  x -= y;
  if (x < 0) x += P;
}
inline int mod(LL x) { return x % P; }
int fpow(int x, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, x = 1LL * x * x % P) {
    if (k & 1) r = 1LL * r * x % P;
  }
  return r;
}
struct Z {
  int x;
  Z(int v = 0) : x(v < 0 ? v + P : v >= P ? v - P : v) {}
  Z(LL v) : x((v %= P) < 0 ? v + P : v) {}
  explicit operator bool() { return !!x; }
  Z inv() const { return Z(fpow(x)); }
  Z pow(int k) const { return Z(fpow(x, k)); }
  Z operator-() const { return Z(P - x); }
  Z &operator+=(const Z &r) { return inc(x, r.x), *this; }
  Z &operator-=(const Z &r) { return dec(x, r.x), *this; }
  Z &operator*=(const Z &r) { return x = LL(x) * r.x % P, *this; }
  Z &operator/=(const Z &r) { return x = LL(x) * fpow(r.x) % P, *this; }
  inline friend Z operator+(const Z &a, const Z &b) { return Z(a) += b; }
  inline friend Z operator-(const Z &a, const Z &b) { return Z(a) -= b; }
  inline friend Z operator*(const Z &a, const Z &b) { return Z(a) *= b; }
  inline friend Z operator/(const Z &a, const Z &b) { return Z(a) /= b; }
  inline friend std::ostream &operator<<(std::ostream &os, const Z &r) {
    return os << r.x;
  }
};

using Matrix = std::array<Z, 4>;
Matrix operator*(const Matrix &a, const Z &b) {
  return {a[0] * b, a[1] * b, a[2] * b, a[3] * b};
}
Matrix operator+(const Matrix &a, const Matrix &b) {
  return {a[0] + b[0], a[1] + b[1], a[2] + b[2], a[3] + b[3]};
}
Matrix operator-(const Matrix &a, const Matrix &b) {
  return {a[0] - b[0], a[1] - b[1], a[2] - b[2], a[3] - b[3]};
}
Matrix operator*(const Matrix &a, const Matrix &b) {
  return {a[0] * b[0] + a[1] * b[2], a[0] * b[1] + a[1] * b[3],
          a[2] * b[0] + a[3] * b[2], a[2] * b[1] + a[3] * b[3]};
}
constexpr int N(2e5 + 5);
Z fac[N], ifac[N], inv[N];
void init(int n) {
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i;
  ifac[n] = fac[n].inv();
  for (int i = n; i; i--) ifac[i - 1] = ifac[i] * i;
  inv[1] = 1;
  for (int i = 2; i <= n; i++) inv[i] = inv[P % i] * (P - P / i);
}
Matrix f[N], g[N], h[N];
int main() {
  freopen("t.in", "r", stdin);
  // freopen(".out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  init(2e5);
  int t;
  std::cin >> t;
  g[0] = h[0] = {1, 0, 0, 1};
  while (t--) {
    int n;
    Z a, b, c, d, e, ans;
    std::cin >> n >> a.x >> b.x >> c.x >> d.x >> e.x;
    Matrix aa = {b, 1, c, 0}, bb = {d, 1, e, 0};
    
    for (int i = 1; i <= 2 * n; i++) {
      if (i <= n) {
        g[i] = g[i - 1] * aa;
        h[i] = h[i - 1] * bb;
      } else {
        g[i] = h[i] = {0, 0, 0, 0};
      }
    }
    auto pa = g[n] * aa, pb = h[n] * bb;
    for (int i = 1; i <= n; i++) {
      g[i] = g[i] * ifac[i];
      h[i] = h[i] * ifac[i];
    }
    f[2] = g[1] * h[1];
    for (int i = 2; i < 2 * n; i++) {
      f[i + 1] = aa * f[i] + f[i] * bb ;
      if (i > n) {
        f[i + 1] = f[i + 1] - (pa * h[i - n] + g[i - n] * pb) * ifac[n];
      } else {
        f[i + 1] = f[i + 1] + aa * h[i] + g[i] * bb;
      }
      f[i + 1] = f[i + 1] * inv[i + 1];
    }
    a /= c;
    for (int i = 2; i <= 2 * n; i++) {
      f[i] = f[i] * fac[i];
      ans += f[i][2] * a;
    }
    std::cout << ans << "\n";
  }
  return 0;
}

Power Sum

// Author:  HolyK
// Created: Sat Aug 28 12:20:19 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  auto out = [&](int n) {
    for (int i = 1; i <= n; i += 4) {
      std::cout << "1001";
    }
    std::cout << "\n";
  };
  int t;
  std::cin >> t;
  while (t--) {
    int n;
    std::cin >> n;
    
    if (n % 4 == 0) {
      std::cout << n << "\n";
      out(n);
    } else if (n % 4 == 1) {
      std::cout << n << "\n";
      std::cout << "1";
      out(n - 1);
    } else if (n % 4 == 2) {
      std::cout << n + 2 << "\n";
      std::cout << "0001"; // 2
      out(n - 2);
    } else if (n % 4 == 3) {
      std::cout << n + 2 << "\n";
      std::cout << "0";
      out(n + 1);
    }
             
  }
  return 0;
}

Function

// Author:  HolyK
// Created: Sat Aug 28 13:08:51 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

int cal(int x) {
  int r = 0;
  for (; x; x /= 10) r += x % 10;
  return r;
}
std::vector<int> s[60];
LL cal(LL a, LL b, LL x) {
  return (a * x + b) * x;
}
LL n;
LL getMin(std::vector<int> &s, LL a, LL b) {
  LL r = LLONG_MAX;
  if (s.empty()) return r;
  if (s[0] > n) return r;
  smin(r, cal(a, b, s[0]));
  auto end = std::upper_bound(s.begin(), s.end(), n);
  smin(r, cal(a, b, *std::prev(end)));
  if (a > 0) {
    LL u = -b / (2 * a);
    auto it = std::lower_bound(s.begin(), end, u);
    if (it < end) smin(r, cal(a, b, *it));
    if (it != s.begin() && *--it <= n) smin(r, cal(a, b, *it));
  }
  return r;
}
// std::mt19937_64 rng(std::chrono::high_resolution_clock::now().time_since_epoch().count());
// LL rnd(LL l, LL r) {
//   if (l > r) std::swap(l, r);
//   return l + rng() % (r - l + 1);
// }
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  for (int i = 1; i <= 1e6; i++) {
    s[cal(i)].push_back(i);
  }
  int t;
  std::cin >> t;
  // t = 100000;
  while (t--) {
    LL a, b, c, d;
    std::cin >> a >> b >> c >> d >> n;
    // a = rnd(-1000, 1000);
    // b = rnd(-1e6, 1e6);
    // c = rnd(-1e6, 1e6);
    // d = rnd(-1e6, 1e6);
    // n = rnd(1, 1e3);
    LL r = LLONG_MAX;
    for (int i = 1; i <= 54; i++) {
      smin(r, getMin(s[i], a * i + b, i * (c * i + d)));
    }
    std::cout << r << "\n";

    // LL rr = LLONG_MAX;
    // for (int i = 1; i <= n; i++) {
    //   int j = cal(i);
    //   smin(rr, cal(a * j + b, j * (c * j + d), i));
    // }
    // if (rr != r) {
    //   std::cerr << a << " " << b << " " << c << " " << d << " " << n << "\n";
    //   break;
    // }
    // std::cerr << "ac\n";
  }
  return 0;
}

GCD on Sequence

// Author:  HolyK
// Created: Sat Aug 28 15:57:56 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}
inline char gc() {
  static constexpr int BufferSize = 1 << 22 | 5;
  static char buf[BufferSize], *p, *q;
  static std::streambuf *i = std::cin.rdbuf();
  return p == q ? p = buf, q = p + i->sgetn(p, BufferSize), p == q ? EOF : *p++ : *p++;
}
struct Reader {
  template <class T>
  Reader &operator>>(T &w) {
    char c, p = 0;
    for (; !std::isdigit(c = gc());) if (c == '-') p = 1;
    for (w = c & 15; std::isdigit(c = gc()); w = w * 10 + (c & 15)) ;
    if (p) w = -w;
    return *this;
  }
} cin;

using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(1e5 + 6);
std::vector<int> fac[N];
void init(int n) {
  for (int i = n; i >= 1; i--) {
    for (int j = i; j <= n; j += i) {
      fac[j].push_back(i);
    }
  }
}
int n, a[N], pos[N];
#define ls o << 1
#define rs o << 1 | 1
LL sum[N << 2], ans[N];
int min[N << 2], max[N << 2];
PII tag[N << 2];
void modify(int o, int l, int r, PII x) {
  tag[o] = x;
  sum[o] = (r - l + 1LL) * x.second;
  max[o] = min[o] = x.first;
}
void pushup(int o) {
  min[o] = std::min(min[ls], min[rs]);
  max[o] = std::max(max[ls], max[rs]);
  sum[o] = sum[ls] + sum[rs];
}
void pushdown(int o, int l, int r) {
  if (tag[o].first) {
    int m = l + r >> 1;
    modify(ls, l, m, tag[o]);
    modify(rs, m + 1, r, tag[o]);
    tag[o].first = 0;
  }
}
void update(int o, int l, int r, int x, int y, int z, int i) {
  if (min[o] >= z) return;
  if (x <= l && r <= y && max[o] == min[o]) {
    ans[max[o]] += i * (r - l + 1LL) - sum[o];
    modify(o, l, r, {z, i});
    return;
  }
  pushdown(o, l, r);
  int m = l + r >> 1;
  if (x <= m) update(ls, l, m, x, y, z, i);
  if (y > m) update(rs, m + 1, r, x, y, z, i); 
  pushup(o);
}
void solve() {
  cin >> n;
  memset(pos, 0, (n + 1) * sizeof(int));
  memset(ans, 0, (n + 1) * sizeof(LL));
  memset(sum, 0, (n + 1) * 4 * sizeof(LL));
  memset(min, 0, (n + 1) * 4 * sizeof(int));
  memset(max, 0, (n + 1) * 4 * sizeof(int));
  memset(tag, 0, (n + 1) * 4 * sizeof(PII));
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    std::vector<int> s;
    for (int j : fac[a[i]]) {
      if (pos[j]) {
        if (s.empty() || pos[s.back()] < pos[j]) s.push_back(j);
      }
    }
    int last = 0;
    for (int x : s) {
      int j = pos[x];
      update(1, 1, n, last + 1, j, x, i);
      last = j;
    }
    for (int j : fac[a[i]]) {
      pos[j] = i;
    }
  }
  update(1, 1, n, 1, n, n + 1, n + 1);
  for (int i = 1; i <= n; i++) {
    std::cout << ans[i] << "\n";
  }
}
int main() {
  // freopen("t.in", "r", stdin);
  // freopen(".out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  init(1e5);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

Command Sequence

// Author:  HolyK
// Created: Sat Aug 28 12:08:46 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int t;
  std::cin >> t;
  while (t--) {
    int n;
    std::string s;
    std::cin >> n >> s;
    std::map<PII, int> mp;
    mp[{0, 0}] = 1;
    int x = 0, y = 0;
    LL ans = 0;
    for (char c : s) {
      if (c == 'U') {
        x++;
      } else if (c == 'D') {
        x--;
      } else if (c == 'L') {
        y++;
      } else {
        y--;
      }
      auto &v = mp[{x, y}];
      ans += v;
      v++;
    }
    std::cout << ans << "\n";
  }
  return 0;
}

Random Walk

// Author:  HolyK
// Created: Mon Aug 30 17:52:12 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;
constexpr int P(998244353);
inline void inc(int &x, int y) {
  x += y;
  if (x >= P) x -= P;
}
inline void dec(int &x, int y) {
  x -= y;
  if (x < 0) x += P;
}
inline int mod(LL x) { return x % P; }
int fpow(int x, int k = P - 2) {
  int r = 1;
  for (; k; k >>= 1, x = 1LL * x * x % P) {
    if (k & 1) r = 1LL * r * x % P;
  }
  return r;
}
struct Z {
  int x;
  Z() : x(0) {}
  Z(int v) : x(v < 0 ? v + P : v >= P ? v - P : v) {}
  Z(LL v) : x((v %= P) < 0 ? v + P : v) {}
  explicit operator bool() { return !!x; }
  Z inv() const { return Z(fpow(x)); }
  Z pow(int k) const { return Z(fpow(x, k)); }
  Z operator-() const { return Z(P - x); }
  Z &operator+=(const Z &r) { return inc(x, r.x), *this; }
  Z &operator-=(const Z &r) { return dec(x, r.x), *this; }
  Z &operator*=(const Z &r) { return x = LL(x) * r.x % P, *this; }
  Z &operator/=(const Z &r) { return x = LL(x) * fpow(r.x) % P, *this; }
  inline friend Z operator+(const Z &a, const Z &b) { return Z(a) += b; }
  inline friend Z operator-(const Z &a, const Z &b) { return Z(a) -= b; }
  inline friend Z operator*(const Z &a, const Z &b) { return Z(a) *= b; }
  inline friend Z operator/(const Z &a, const Z &b) { return Z(a) /= b; }
  inline friend std::ostream &operator<<(std::ostream &os, const Z &r) {
    return os << r.x;
  }
};

inline char gc() {
  static constexpr int BufferSize = 1 << 22 | 5;
  static char buf[BufferSize], *p, *q;
  static std::streambuf *i = std::cin.rdbuf();
  return p == q ? p = buf, q = p + i->sgetn(p, BufferSize), p == q ? EOF : *p++ : *p++;
}
struct Reader {
  template <class T>
  Reader &operator>>(T &w) {
    char c, p = 0;
    for (; !std::isdigit(c = gc());) if (c == '-') p = 1;
    for (w = c & 15; std::isdigit(c = gc()); w = w * 10 + (c & 15)) ;
    if (p) w = -w;
    return *this;
  }
} cin;

constexpr int N(505);
Z p[N][N], ip[N][N * 2], w[N], ideg[N], a[9][N];

int deg[N], id[N][N];
struct Edge {
  int x, y, a, b;
} e[10005];
Z s[10005];
int main() {
  // freopen("t.in", "r", stdin);
  // freopen(".out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, m, q;
  cin >> n >> m >> q;
  for (int i = 1; i < n; i++) cin >> w[i].x;
  for (int i = 1; i <= m; i++) {
    cin >> e[i].x >> e[i].y >> e[i].a >> e[i].b;
    deg[e[i].x]++, deg[e[i].y]++;
    id[e[i].x][e[i].y] = id[e[i].y][e[i].x] = i;
  }
  for (int i = 1; i < n; i++) {
    ideg[i] = Z(deg[i]).inv();
  }
  for (int i = 1; i <= m; i++) {
    int x = e[i].x, y = e[i].y;
    p[x][y] = ideg[x];
    p[y][x] = ideg[y];
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      ip[i][j] = -p[i][j];
      if (i == j) {
        ip[i][j] += 1;
        ip[i][j + n + 1] = 1;
      }
    }
  }
  for (int i = 1, j; i <= n; i++) {
    for (j = i; j <= n && !ip[j][i]; j++) ;
    assert(j <= n);
    if (i != j) std::swap(ip[i], ip[j]);
    Z c = ip[i][i].inv();
    for (int k = n * 2 + 1; k >= i; k--) ip[i][k] *= c;
    for (j = 1; j <= n; j++) {
      if (i == j || !ip[j][i]) continue;
      c = ip[j][i];
      for (int k = n * 2 + 1; k >= i; k--) {
        ip[j][k] -= ip[i][k] * c;
      }
    }
  }
  auto getp = [&] {
    Z sum;
    for (int i = 1; i < n; i++) sum += w[i];
    Z inv = sum.inv();
    for (int i = 1; i < n; i++) {
      p[0][i] = w[i] * inv;
    }
    ip[0][0] = ip[0][n + 1] = 1;
    for (int i = 1; i <= n; i++) {
      ip[0][i + n + 1] = 0;
      if (!p[0][i]) continue;
      for (int j = n + 1; j <= n * 2 + 1; j++) {
        ip[0][j] += p[0][i] * ip[i][j];
      }
    }
    memset(a, 0, sizeof a);
    a[0][0] = 1;
    for (int i = 1; i <= 7; i++) {
      for (int j = 0; j <= n; j++) {
        for (int k = 0; k <= n; k++) {
          a[i][k] += a[i - 1][j] * p[j][k];
        }
      }
    }
    for (int j = 0; j <= n; j++) {
      for (int k = 0; k <= n; k++) {
        a[8][k] += a[7][j] * ip[j][k + n + 1];
      }
    }
  };
  auto cal = [&](int x, int y, int max, int min) {
    Z res;
    for (int i = 1; i <= 6; i++) {
      res += (a[i][x] * ideg[x] + a[i][y] * ideg[y]) * std::max(max, min);
      max >>= 1;
    }
    res += (a[8][x] * ideg[x] + a[8][y] * ideg[y]) * min;
    return res;
  };
  Z ans;
  getp();
  for (int i = 1; i <= m; i++) {
    ans += s[i] = cal(e[i].x, e[i].y, e[i].a, e[i].b);
  }
  std::cout << ans << "\n";
  while (q--) {
    int opt, x, y, a, b;
    cin >> opt >> x >> y;
    if (opt == 1) {
      int i = id[x][y];
      ans -= s[i];
      cin >> e[i].a >> e[i].b;
      ans += s[i] = cal(x, y, e[i].a, e[i].b);
    } else {
      w[x] = y;
      getp();
      ans = 0;
      for (int i = 1; i <= m; i++) {
        ans += s[i] = cal(e[i].x, e[i].y, e[i].a, e[i].b);
      }
    }
    std::cout << ans << "\n";
  }
  return 0;
}

Shooting Bricks

Remove

// Author:  HolyK
// Created: Sat Aug 28 14:21:04 2021
#include <bits/stdc++.h>
template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}
inline char gc() {
  static constexpr int BufferSize = 1 << 22 | 5;
  static char buf[BufferSize], *p, *q;
  static std::streambuf *i = std::cin.rdbuf();
  return p == q ? p = buf, q = p + i->sgetn(p, BufferSize), p == q ? EOF : *p++ : *p++;
}
struct Reader {
  template <class T>
  Reader &operator>>(T &w) {
    char c, p = 0;
    for (; !std::isdigit(c = gc());) if (c == '-') p = 1;
    for (w = c & 15; std::isdigit(c = gc()); w = w * 10 + (c & 15)) ;
    if (p) w = -w;
    return *this;
  }
} cin;

using LL = long long;
using PII = std::pair<int, int>;
constexpr int N(2e6 + 5);
int primes[N], g[N], val[N], vis[N], now, cnt;
std::bitset<N> np;
void init(int n) {
  cnt = 0;
  memset(g, 0, (n + 1) * sizeof(int));
  np.reset();
  for (int i = 2; i <= n; i++) {
    if (!np[i]) {
      primes[++cnt] = i;
      g[i] = vis[i] == now ? i : 0;
    }
    for (int j = 1; j <= cnt; j++){
      if (1LL * i * primes[j] > n) break;
      g[i * primes[j]] = std::max(g[i], g[primes[j]]);
      np[i * primes[j]] = 1;
      if (i % primes[j] == 0) break;
    }
  }
}
int f[N], p[N];
int main() {
  freopen("t.in", "r", stdin);
  // freopen("t.out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int t;
  cin >> t;
  for (now = 1; now <= t; now++) {
    int n, m;
    cin >> n >> m;
    int max = 0;
    for (int i = 1; i <= m; i++) {
      cin >> p[i];
      vis[p[i]] = now;
      smax(max, p[i]);
    }
    init(n);
    for (int i = 1; i < max; i++) f[i] = 1;
    for (int i = max, j = 2; i <= n; i++) {
      while (j < i && j + g[j] <= i) j++;
      // debug
      // int max = 0;
      // for (int k = 1; k <= m; k++) {
      //   smax(max, i % p[k]);
      // }
      // if (i - max != j) {
      //   // std::cerr << i << " " << j << " " << i - max << "\n";
      //   // std::cerr << g[3589] << "\n";
      //   for (int k = 1; k <= m; k++) {
      //     if (max == i % p[k]) std::cerr << p[k] << "\n";
      //   }
      //   assert(false);
      // }
      //------
      f[i] = j < i ? f[j] + 1 : 1e9;
    }
    uint64_t ans = 0;
    for (int i = 1; i <= n; i++) {
      if (f[i] >= 1e9) f[i] = 0;
      // std::cout << f[i] << " \n"[i == n];
      ans = (ans * 23333 + f[i]);
    }
    std::cout << ans << "\n";
  }
  // std::cerr << (double)clock() / CLOCKS_PER_SEC << "\n";
  return 0;
}

Start Dash ! !

最后修改于 2021-08-31