TJOI 2019 简要题解

2020-05-18

~~我没有在刷水题 (确信~~

打扰了.

「TJOI2019」甲苯先生的字符串

题目链接

https://loj.ac/problem/3104

解题思路

很套路的矩阵乘法 = =

设 $f(i, c)$ 表示当前计算到 $s_2$ 中第 $i$ 位, 且第 $i$ 位字符为 $c$. 容易发现转移和 $i$ 无关, 构造矩阵加速转移即可.

时间复杂度 $O(|s_1| + \log n)$, 同时带有矩阵乘法的常数 ($26 \times 26$).

代码实现

> 点击显示 / 隐藏

// LOJ #3104
// DeP
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAXN = 1e5 + 5, MAXM = 26, P = 1e9 + 7;

struct Matrix {
  int g[MAXM][MAXM];
  Matrix() { memset(g, 0, sizeof g); }
  Matrix operator * (const Matrix& rhs) const {
    Matrix ret;
    for (int i = 0; i < MAXM; ++i)
      for (int k = 0; k < MAXM; ++k) if (g[i][k] != 0)
        for (int j = 0; j < MAXM; ++j) if (rhs.g[k][j] != 0)
          ret.g[i][j] = (ret.g[i][j] + 1LL * g[i][k] * rhs.g[k][j] % P) % P;
    return ret;
  }
  inline void init() {
    for (int i = 0; i < MAXM; ++i) g[i][i] = 1;
  }
};

Matrix fpow(Matrix base, LL b) {
  Matrix ret; ret.init();
  while (b > 0) {
    if (b & 1) ret = ret * base;
    base = base * base, b >>= 1;
  }
  return ret;
}

int m; LL n;
char S[MAXN];

Matrix f, g;

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  scanf("%lld%s", &n, S + 1);

  m = (int) strlen(S + 1);
  for (int i = 0; i < MAXM; ++i)
    for (int j = 0; j < MAXM; ++j) f.g[i][j] = 1;
  for (int i = 1; i < m; ++i) {
    int c1 = S[i] - 'a', c2 = S[i + 1] - 'a';
    f.g[c1][c2] = 0;
  }
  g = fpow(f, n - 1);

  int ans = 0;
  for (int i = 0; i < MAXM; ++i)
    for (int j = 0; j < MAXM; ++j) ans = (ans + g.g[i][j]) % P;
  printf("%d\n", ans);
  return 0;
}

「TJOI2019」甲苯先生的滚榜

题目链接

https://loj.ac/problem/3105

解题思路

这是一道平衡树模板题.

唯一需要注意的地方是, 该题中排名指所有元素中, 严格大于某元素的个数. 同常见的 “求 rank“ 有些许不同.

时间复杂度 $O\big(T (n + m) \log m\big)$.

代码实现

> 点击显示 / 隐藏

// LOJ #3105
// DeP
#include <cstdio>
#include <cstdlib>
using namespace std;

const int MAXN = 1.5e6 + 5, MAXM = 1e5 + 5;

unsigned randNum(unsigned& seed, unsigned lst, const int& m){ 
  return seed = seed * 17 + lst, seed % m + 1; 
}

struct Item {
  int c, p;
  Item() { c = p = 0; }
  Item(int _c, int _p): c(_c), p(_p) { }
  bool operator < (const Item& rhs) const {
    return c < rhs.c || (c == rhs.c && p > rhs.p);
  }
  bool operator == (const Item& rhs) const {
    return !(*this < rhs) && !(rhs < *this);
  }
} A[MAXM];

int n, m, root; unsigned seed;

namespace Splay {
  Item val[MAXN];
  int ch[2][MAXN], pre[MAXN], size[MAXN], cnt[MAXN], nidx;

  inline int newnode(const Item& v) {
    int nd = ++nidx;
    ch[0][nd] = ch[1][nd] = pre[nd] = 0;
    return val[nd] = v, size[nd] = cnt[nd] = 1, nd;
  }
  inline void maintain(const int& nd) {
    size[nd] = cnt[nd];
    if (ch[0][nd]) size[nd] += size[ch[0][nd]];
    if (ch[1][nd]) size[nd] += size[ch[1][nd]];
  }

  inline int which(const int& u) { return pre[u]? ch[1][pre[u]] == u: 0; }
  inline void connect(int u, int fa, const int& w) {
    if (u) pre[u] = fa;
    if (fa) ch[w][fa] = u; else root = u;
  }
  inline void rotate(const int& u) {
    int fa = pre[u], w = which(u);
    connect(u, pre[fa], which(fa));
    connect(ch[w ^ 1][u], fa, w), connect(fa, u, w ^ 1);
    maintain(fa);
  }

  void splay(const int& u, int v) {
    v = pre[v];
    while (pre[u] != v) {
      int fa = pre[u];
      if (pre[fa] != v) which(u) == which(fa)? rotate(fa): rotate(u);
      rotate(u);
    }
    maintain(u);
  }

  void Ins(const Item& v) {
    if (!root) return void( root = newnode(v) );
    for (int nd = root; nd; nd = ch[val[nd] < v][nd]) {
      if (val[nd] == v) return ++cnt[nd], splay(nd, root);
      if (!ch[val[nd] < v][nd]) {
        ch[val[nd] < v][nd] = newnode(v);
        return pre[nidx] = nd, splay(nidx, root);
      }
    }
  }

  inline void Fnd(const Item& v) {
    for (int nd = root; nd; nd = ch[val[nd] < v][nd])
      if (val[nd] == v) return splay(nd, root);
    abort();
  }
  void Rmv(const Item& v) {
    Fnd(v);
    if (cnt[root] > 1) return void( --cnt[root] );
    if (!ch[0][root] && !ch[1][root])
      return void( root = 0 );
    if (!ch[0][root] || !ch[1][root]) {
      int w = !ch[0][root];
      return root = ch[w][root], void( pre[root] = 0 );
    }
    int nd = ch[0][root];
    while (ch[1][nd] > 0) nd = ch[1][nd];
    splay(nd, ch[0][root]);
    ch[1][nd] = ch[1][root], pre[nd] = 0, root = pre[ch[1][nd]] = nd;
    maintain(nd);
  }

  inline int Rnk(const Item& v) {
    return Ins(v), size[ch[1][root]];
  }
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  int Ti, lstans = 7;
  scanf("%d", &Ti);
  while (Ti--) {
    scanf("%d%d%u", &m, &n, &seed);

    Splay::nidx = root = 0;
    for (int i = 1; i <= m; ++i)
      A[i] = Item(0, 0), Splay::Ins(A[i]);

    for (int x, y; n; --n) {
      x = randNum(seed, lstans, m), y = randNum(seed, lstans, m);
      Splay::Rmv(A[x]), ++A[x].c, A[x].p += y;
      printf("%d\n", lstans = Splay::Rnk(A[x]));
    }
  }
  return 0;
}

「TJOI2019」唱、跳、rap 和篮球

题目链接

https://loj.ac/problem/3106

解题思路

我们可用容斥原理计算讨论 [数据删除] 的队伍数.

记 $A_i$ 表示满足队伍中存在 $i$ 组讨论 [数据删除] 的集合, 最多情况下讨论 [数据删除] 的组数为 $m = \min \{ a, b, c, d, \lfloor \frac{n}{4} \rfloor \}$. 那么所有 $A_i$ 的补集交即为所求. 根据容斥原理可得

$|\bigcap_{i = 1} ^ m \bar A_i| = \sum_{k = 0} ^ m (-1) ^ k \sum_{1 \le i_1,\ \cdots,\ i_k \le n} |\bigcap_{j = 1} ^ k A_{i_j}|$

队伍中每组讨论各在那个位置并不重要, 因此可枚举讨论组数 $k$, 得

$\sum_{k = 0} ^ m (-1) ^ k \binom{n - 3k}{k}\ g(n - 4k, a - k, b - k, c - k, d - k)$

系数 $\binom{n - 3k}{k}$ 表示在队伍中选出 $k$ 组讨论的方案数. 可将每组讨论看作一个人, 那么队伍中人数为 $n - 3k$, 从中选择 $k$ 人作为讨论, 从而得到.

同时, $g(n, a, b, c, d)$ 表示剩余学生的排列数, 也就是可重集合的排列数. 即

$g(n, a, b, c, d) = \sum_{x_1 + x_2 + x_3 + x_4 = n} \binom{n}{x_1\; x_2\; x_3\; x_4} = n! \cdot \sum_{x_1 + x_2 + x_3 + x_4 = n} \frac{1}{x_1!\ x_2!\ x_3!\ x_4!}$

其中 $x_1, x_2, x_3, x_4$ 满足 $x_1 \le a, x_2 \le b, x_3 \le c, x_4 \le d$.

显然是卷积的形式, 利用 NTT 计算 $g$ 即可.

时间复杂度 $O(n ^ 2 \log n)$. 似乎存在更加优秀的做法?

代码实现

> 点击显示 / 隐藏

// LOJ #3106
// DeP
#include <cstdio>
#include <algorithm>
using namespace std;

const int LOG = 13, MAXN = 1 << LOG | 1, P = 998244353, G = 3;

int W[LOG][MAXN];
int fac[MAXN], ifac[MAXN], inv[MAXN];

inline int binom(int n, int m) {
  return (n < m)? 0: 1LL * fac[n] * ifac[m] % P * ifac[n - m] % P;
}

int fpow(int base, int b) {
  int ret = 1;
  while (b > 0) {
    if (b & 1) ret = 1LL * ret * base % P;
    base = 1LL * base * base % P, b >>= 1;
  }
  return ret;
}

namespace Poly {
  int r[MAXN];
  inline void init(const int& Lim, const int& L) {
    for (int i = 1; i < Lim; ++i) r[i] = (r[i>>1] >> 1) | ((i & 1) << (L-1));
  }

  void NTT(int* f, const int& Lim, const int& type) {
    for (int i = 1; i < Lim; ++i) if (i < r[i]) swap(f[i], f[r[i]]);
    for (int k = 0, Mid = 1; Mid < Lim; Mid <<= 1, ++k) {
      const int* w = W[k];
      for (int i = 0; i < Lim; i += Mid << 1)
        for (int j = 0; j < Mid; ++j) {
          int f0 = f[i+j], f1 = 1LL * w[j] * f[i+j+Mid] % P;
          f[i+j] = (f0 + f1) % P, f[i+j+Mid] = (f0 - f1 + P) % P;
        }
    }
    if (type < 0) {
      int inv = fpow(Lim, P - 2);
      for (int i = 0; i < Lim; ++i) f[i] = 1LL * f[i] * inv % P;
      reverse(f + 1, f + Lim);
    }
  }
}

void PolyPre(int N) {
  inv[1] = 1;
  for (int i = 2; i <= N; ++i)
    inv[i] = 1LL * inv[P % i] * (P - P / i) % P;
  fac[0] = ifac[0] = 1;
  for (int i = 1; i <= N; ++i) {
    fac[i] = 1LL * i * fac[i - 1] % P;
    ifac[i] = 1LL * inv[i] * ifac[i - 1] % P;
  }
  for (int w, i = 0, Mid = 1; i < LOG; ++i, Mid <<= 1) {
    W[i][0] = 1, w = fpow(G, (P - 1) / (Mid << 1));
    for (int j = 1; j < Mid; ++j)
      W[i][j] = 1LL * w * W[i][j - 1] % P;
  }
}

int g(int n, int a, int b, int c, int d) {
  static int A[MAXN], B[MAXN], C[MAXN], D[MAXN], f[MAXN];
  int Lim = 1, L = 0;
  while (Lim <= 2 * (a + b + c + d)) Lim <<= 1, ++L;
  Poly::init(Lim, L);
  for (int i = 0; i < Lim; ++i) {
    A[i] = (i <= a)? ifac[i]: 0, B[i] = (i <= b)? ifac[i]: 0;
    C[i] = (i <= c)? ifac[i]: 0, D[i] = (i <= d)? ifac[i]: 0;
  }
  Poly::NTT(A, Lim, 1), Poly::NTT(B, Lim, 1);
  Poly::NTT(C, Lim, 1), Poly::NTT(D, Lim, 1);
  for (int i = 0; i < Lim; ++i)
    f[i] = 1LL * A[i] * B[i] % P * C[i] % P * D[i] % P;
  Poly::NTT(f, Lim, -1);
  return 1LL * f[n] * fac[n] % P;
}

int n, a, b, c, d;

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);

  if (a + b + c + d < n)
    return puts("0"), 0;
  PolyPre(2 * n);
  int N = min(min(a, min(b, min(c, d))), n / 4), ans = 0;
  for (int i = 0; i <= N; ++i) {
    int s = g(n - 4 * i, a - i, b - i, c - i, d - i) % P;
    ans = (ans + 1LL * binom(n - 3 * i, i) * ((i & 1)? P - s: s) % P) % P;
  }

  printf("%d\n", ans);
  return 0;
}

「TJOI2019」大中锋的游乐场

题目链接

https://loj.ac/problem/3107

解题思路

注意到 $k \le 10$, 那么设 $f(i, j)$ 表示从起点 $s$ 出发到第 $i$ 个位置, 汉堡和可乐个数差值为 $j$ 时的最短路, 其中 $-k \le j \le k$.

直接在 Dijkstra 的过程中计算即可, 注意 $j$ 的范围, 以及不要忘了在起点处更新 $j$. 本质上为分层图最短路.

时间复杂度 $O(T n k \log m)$.

代码实现

> 点击显示 / 隐藏

// LOJ #3107
// DeP
#include <queue>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

namespace IO {
  const int MAXSIZE = 1 << 18 | 1;
  char buf[MAXSIZE], *p1, *p2;

  inline int Gc() {
    return p1 == p2 &&
      (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
  }
  template<typename T> inline void read(T& x) {
    x = 0; int f = 0, ch = Gc();
    while (!isdigit(ch)) f |= ch == '-', ch = Gc();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
    if (f) x = -x;
  }
}
using IO::read;

const int MAXN = 1e4 + 5, MAXM = 1e5 + 5, MAXK = 1e1 + 5, INF = 0x3f3f3f3f;

int n, m, K, s, t;
int A[MAXN], d[MAXN][MAXK];

namespace Graph {
  struct Edge { int nxt, to, w; } edges[MAXM << 1];
  int head[MAXN], eidx;

  inline void init() { memset(head, -1, sizeof head), eidx = 1; }
  inline void AddEdge(int from, int to, int w) {
    edges[++eidx] = (Edge){ head[from], to, w }, head[from] = eidx;
  }

  struct Node {
    int u, k, d;
    Node(int _u, int _k, int _d): u(_u), k(_k), d(_d) { }
    bool operator < (const Node& rhs) const { return d > rhs.d; }
  };

  int Dijkstra() {
    priority_queue<Node> PQ;
    memset(d, 0x3f, sizeof d);
    PQ.push(Node(s, K + A[s], d[s][K + A[s]] = 0));
    while (!PQ.empty()) {
      int u = PQ.top().u, k = PQ.top().k, w = PQ.top().d; PQ.pop();
      if (d[u][k] != w) continue;
      for (int i = head[u]; ~i; i = edges[i].nxt) {
        int v = edges[i].to, vk = k + A[v];
        if (0 <= vk && vk <= 2 * K && d[v][vk] > d[u][k] + edges[i].w)
          PQ.push(Node(v, vk, d[v][vk] = d[u][k] + edges[i].w));
      }
    }
    int ret = INF;
    for (int k = 0; k <= 2 * K; ++k) ret = min(ret, d[t][k]);
    return ret < INF? ret: -1;
  }
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  int Ti; read(Ti);
  while (Ti--) {
    Graph::init();

    read(n), read(m), read(K);
    for (int i = 1; i <= n; ++i)
      read(A[i]), A[i] = (A[i] == 1)? 1: -1;
    for (int u, v, w, i = 1; i <= m; ++i) {
      read(u), read(v), read(w);
      Graph::AddEdge(u, v, w), Graph::AddEdge(v, u, w);
    }
    read(s), read(t);

    printf("%d\n", Graph::Dijkstra());
  }
  return 0;
}

「TJOI2019」甲苯先生和大中锋的字符串

题目链接

https://loj.ac/problem/3108

解题思路

首先有一个 (可能)? 不太常用的 SAM 性质:

对于每一个状态 $v$ ，一个或多个子串与之匹配。我们记 $longest(v)$ 为其中最长的一个字符串，记 $len(v)$ 为它的长度。类似地，记 $shortest(v)$ 为最短的子串，它的长度为 $minlen(v)$ 。那么对应这个状态的所有字符串都是字符串 $longest(v)$ 的不同的后缀，且所有字符串的长度恰好覆盖区间 $[minlen(v),len(v)]$ 中的每一个整数。

对于初始状态 $t_0$ 以外的状态 $v$ ，可用后缀链接 $link(v)$ 表达 $minlen(v)$ ：
$minlen(v)=len(link(v))+1.$
from OI Wiki

那么在建出 SAM 后, 对于一个每个包含出现 $k$ 次子串的状态 $v$, 在长度区间 $\Big(len\big(link(v)\big), len(v)\Big]$ 上 $+1$, 最后统计答案即可. 可利用差分实现.

时间复杂度 $O(Tn)$.

代码实现

> 点击显示 / 隐藏

// LOJ #3108
// DeP
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 2e5 + 5, SIGMA = 26;

int n, K;
char S[MAXN];

namespace SAM {
  int ch[MAXN][SIGMA], lnk[MAXN], len[MAXN], size[MAXN], lst, nidx;
  int f[MAXN], cnt[MAXN], idx[MAXN];

  inline int newnode(const int& l) {
    len[++nidx] = l, lnk[nidx] = 0, size[nidx] = 0;
    return memset(ch[nidx], 0, sizeof ch[nidx]), nidx;
  }
  inline void init() { nidx = 0, lst = newnode(0); }

  inline void Ins(const int& v) {
    int nd = newnode(len[lst] + 1), p = lst;
    size[nd] = 1;
    while (p && !ch[p][v]) ch[p][v] = nd, p = lnk[p];
    if (!p) lnk[nd] = 1;
    else {
      int q = ch[p][v];
      if (len[q] == len[p] + 1) lnk[nd] = q;
      else {
        int nxt = newnode(len[p] + 1);
        lnk[nxt] = lnk[q], memcpy(ch[nxt], ch[q], sizeof ch[nxt]);
        while (p && ch[p][v] == q) ch[p][v] = nxt, p = lnk[p];
        lnk[nd] = lnk[q] = nxt;
      }
    }
    lst = nd;
  }

  inline int Mdy(const int& L, const int& R) { ++f[L], --f[R + 1]; }
  int solve() {
    memset(f, 0, (n + 1) * sizeof (int));
    memset(cnt, 0, (n + 1) * sizeof (int));

    for (int i = 1; i <= nidx; ++i) ++cnt[len[i]];
    for (int i = 1; i <= n; ++i) cnt[i] += cnt[i - 1];
    for (int i = nidx; i; --i) idx[cnt[len[i]]--] = i;
    for (int u, i = nidx; i; --i) {
      u = idx[i], size[lnk[u]] += size[u];
      if (size[u] == K) Mdy(len[lnk[u]] + 1, len[u]);
    }

    for (int i = 1; i <= n; ++i) f[i] += f[i - 1];
    int ret = -1, Mx = 0;
    for (int i = n; i; --i)
      if (f[i] > Mx) Mx = f[i], ret = i;
    return ret;
  }
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  int Ti;
  scanf("%d", &Ti);
  while (Ti--) {
    SAM::init(), scanf("%s%d", S + 1, &K);
    n = (int) strlen(S + 1);
    for (int i = 1; i <= n; ++i) SAM::Ins(S[i] - 'a');

    printf("%d\n", SAM::solve());
  }
  return 0;
}

「TJOI2019」甲苯先生的线段树

题目链接

解题思路

首先考虑 $c = 1$ 的情况.

首先可以观察到一个性质: 对于每一个节点, 除去最高位, 可通过其他位上 0 / 1 的区别, 我们可以确定该节点在不同层上选择左 / 右节点.

因此, 对于线段树上两个节点 $x$, $y$, 其在线段树上 LCA 为 $x$, $y$ 在二进制表示下, 将高位对齐得到的 LCP.

同时, 一个节点 $x$ 到根节点路径上编号和为 $2x - \operatorname{popcount}(x)$. 其中 $\operatorname{popcount}(x)$ 表示 $x$ 在二进制表示下 $1$ 的个数. 当然直接在线段树上暴力向上跳也可以.

简单证明一下, 考虑祖先中出现多出一次左儿子的影响, 体现在二进制表示下即某位改变为 $1$. 将多出的贡献单独拿出来计算, 等同于再次从根节点开始的贡献, 只不过深度改变了. 那么答案为 $2x - \operatorname{popcount}(x)$.

考虑 $c = 2$ 的情况.

记第一问求出的答案为 $s$, 有一个重要的性质: 设两节点 $x$, $y$ 的 LCA $z$, $z$ 到 $x$ 链长 $a$, 到 $y$ 链长 $b$. 如果 $a$, $b$, $s$ 确定, 那么 $z$ 的位置唯一.

简单证明一下. 不妨令 $x < y$. 同时记 $z$ 在二进制表示下有 $t$ 位, 那么 $x$ 在二进制表示下有 $t + a$ 位, $y$ 在二进制表示下有 $t + b$ 位.

先考虑 $x$, $y$ 前 $t$ 位路径编号和 $s$ 的贡献. 即

$\left(\sum_{i = 0} ^ a 2 ^ i + \sum_{i = 0} ^ b 2 ^ i - 1\right)\cdot z = \left( 2 ^ {a + 1} + 2 ^ {b + 1} - 3 \right) \cdot z$

另外有 $x$ 后 $a$ 位, $y$ 后 $b$ 位的贡献. 考虑取最值的两种情况, 即在满足条件的情况下不断向左 / 右走, 可得最小值为 $2 ^ b - 1$, 最大值为 $\left(2 ^ a - 1 - a\right) + \left(2 ^ {b + 1} - 1 - b\right)$.

因此可将 $s$ 表示为 $s = vz + k$ 的形式, 其中 $v = 2 ^ {a + 1} + 2 ^ {b + 1} - 3$, $k \in [2 ^ b - 1, 2 ^ a + 2 ^ {b + 1} - a - b - 3]$. 从而有 $z = \lfloor \frac{s - k}{v} \rfloor$. 注意到 $k < v$, 因此 $z$ 和 $k$ 无关, $z$ 在 $a$, $b$ 确定后唯一.

此时枚举 $a$, $b$ 的取值, 求满足 $k = s - vz$ 的方案数即可. 根据前文的性质, 此时的问题可转化为, 给定一长为 $a - 1$ 的 0-1 串 $A$ 和一长为 $b$ 的 0-1 串 $B$, 求满足 $2A - \operatorname{popcount}(A) + 2B - \operatorname{popcount}(B) = k$ 的 $A$, $B$ 方案数.

DP 计算即可. 具体地, 首先枚举 $\operatorname{popcount}(A) + \operatorname{popcount}(B)$ 取值 $w$, 那么限制为 $2(A + B) = k + w$.

设 $f(i, j, k)$, $k \in \{0, 1\}$ 表示考虑前 $i$ 位, 共凑出 $j$ 个 $1$, 且当前位是否存在进位的方案数. 转移即为

$f(i, j + p + q, \lfloor \frac{p + q + k}{2} \rfloor) = \sum_{p,\ q} f(i - 1, j, k)$

实现时需要注意, 要强制 $A$ 的第 $a$ 位为 $0$, 以及 $B$ 的第 $b$ 位为 $1$, 同时要满足 $A + B$ 二进制表示下每一位和 $\frac{1}{2}(k + w)$ 相同.

时间复杂度 $O(d ^ 5)$.

代码实现

> 点击显示 / 隐藏

// LOJ #3109
// DeP
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;
const int MAXD = 5e2 + 5;

int d;
LL f[MAXD << 1][MAXD << 1][2];

inline LL Dist(const LL& x) {
  return 2 * x - __builtin_popcountll(x);
}
inline LL LCA(LL u, LL v) {
  while (u != v) {
    if (u < v) swap(u, v);
    u >>= 1;
  }
  return u;
}

inline int lg2(LL s) {
  int ret = 0;
  while (s > 0) s >>= 1, ++ret;
  return ret;
}

LL solve(const LL& s, const int& c, const int& a, const int& b) {
  int limit = max(lg2(s), max(a - 1, b));
  for (int i = 0; i <= limit; ++i)
    for (int j = 0; j <= c; ++j) f[i][j][0] = f[i][j][1] = 0;

  for (int p = 0; p <= 1; ++p) {
    if (a <= 1 && p == 1) continue;
    for (int q = 0; q <= 1; ++q) if (p + q <= c) {
      if (((p + q) & 1) != (s & 1)) continue;
      if ((b < 1 && q == 1) || (b == 1 && q == 0)) continue;
      ++f[0][p + q][(p + q) / 2];
    }
  }
  for (int i = 1; i <= limit; ++i) for (int j = 0; j <= c; ++j)
    for (int k = 0; k <= 1; ++k) if (f[i - 1][j][k] > 0) {
      for (int p = 0; p <= 1; ++p) {
        if (i >= a - 1 && p == 1) continue;
        for (int q = 0; q <= 1; ++q) if (j + p + q <= c) {
          if (((k + p + q) & 1) != ((s >> i) & 1)) continue;
          if ((i > b - 1 && q == 1) || (i == b - 1 && q == 0)) continue;
          f[i][j + p + q][(k + p + q) / 2] += f[i - 1][j][k];
        }
      }
    }

  return f[limit][c][0];
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  int Ti, c;
  scanf("%d", &Ti);
  while (Ti--) {
    LL x, y;
    scanf("%d%lld%lld%d", &d, &x, &y, &c);
    LL z = LCA(x, y), s = Dist(x) + Dist(y) - Dist(z) - Dist(z >> 1);
    if (c == 1)
      printf("%lld\n", s);
    else {
      LL ans = 0;
      for (int a = 0; a < d; ++a)
        for (int b = 0; b < d; ++b) {
          LL v = (1LL << (a + 1)) + (1LL << (b + 1)) - 3;
          if (v == 0) continue;
          z = s / v;
          if (z <= 0 || lg2(z) + max(a, b) > d) continue;
          LL k = s - v * z;
          for (int i = 0; i <= a + b; ++i)
            if ((k + i) % 2 == 0) ans += solve((k + i) / 2, i, a, b);
        }
      printf("%lld\n", ans - 1);
    }
  }
  return 0;
}

DepletedPrism's Blog

TJOI 2019 简要题解

「TJOI2019」甲苯先生的字符串

题目链接

解题思路

代码实现

「TJOI2019」甲苯先生的滚榜

题目链接

解题思路

代码实现

「TJOI2019」唱、跳、rap 和篮球

题目链接

解题思路

代码实现

「TJOI2019」大中锋的游乐场

题目链接

解题思路

代码实现

「TJOI2019」甲苯先生和大中锋的字符串

题目链接

解题思路

代码实现

「TJOI2019」甲苯先生的线段树

题目链接

解题思路

代码实现