gym103469

A.

给出集合 $a_i…a_j, 1 \leq i \leq j \leq n$ 的 and 值构成的集合 $b$，构造一个 $k \leq 5n$ 且满足条件的序列。

考虑合法条件一定是 $a_i$ 都是 $\min{b}$ 的超集，否则全局不符合条件。

所以构造 $b_0, b_i$ 交替即可。

void solve() {
  int n;
  cin >> n;
  vi a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(all(a));
  bool ok = true;
  for (int i = 0; i < n; i++) {
    if ((a[i] & a[0]) == a[0]) {
    } else {
      ok = false;
      break;
    }
  }
  if (!ok) {
    cout << -1 << "\n";
    return;
  }
  cout << 2 * n << "\n";
  for (int i = 0; i < n; i++) {
    cout << a[i] << " " << a[0] << " \n"[i + 1 == n];
  }
}

B.

$\sum \lfloor \frac{i^k \times b_i}{w}\rfloor$，其中 $b$ 是 $a$ 排好序的序列，$a$ 单点修改，q 次询问全局答案，答案对 998244353 取模。

$k \leq 5, w \leq 5$

首先维护 $(\sum i^k \times b_i) - \sum (i^k \times b_i) mod w $，最后乘上逆元。

考虑如何维护 $i^k \times b_i$。

建立值域线段树，在值域 $[l, m]$ 的区间排名不变，在 $[m+1,r]$ 的区间排名加上 $[l,m]$ 的数字个数，假设有 $sz$ 个，那么右边会变成 $\sum (rk+sz)^k = \sum rk^i sz^{k-i} \binom{k}{i}$。

所以维护 $rk_i, i \leq k$ 即可。

另外记录一个 $s2_{i,j}$ 表示 $pos\ mod\ w = i$ 且 $val \ mod\ w = j$ 的有多少个。

容易合并，合并的时候右边的 pos 加上左边的 sz 即可。

int n, k, w, q;
const int N = 131072;
const int P = 998244353;
int cnt[N * 2], s[N * 2][6], s2[N * 2][6][6];
int c[6][6], pw[N][6];

int power(int x, int y) {
  int res = 1;
  while (y) {
    if (y % 2 == 1) {
      res = 1ll * res * x % P;
    }
    x = 1ll * x * x % P;
    y /= 2;
  }
  return res;
}

int inverse(int x) { return power(x, P - 2); }

void md(int &x) {
  if (x >= P) {
    x -= P;
  }
}

void pu(int x) {
  int sz = cnt[x * 2];
  cnt[x] = cnt[x * 2] + cnt[x * 2 + 1];
  memcpy(s[x], s[x * 2], sizeof s[x]);
  for (int i = 0; i <= k; i++) {
    for (int j = 0; j <= i; j++) {
      md(s[x][i] += 1ll * s[x * 2 + 1][j] * c[i][j] % P * pw[sz][i - j] % P);
    }
  }
  memcpy(s2[x], s2[x * 2], sizeof s2[x]);
  for (int i = 0; i < w; i++) {
    for (int j = 0; j < w; j++) {
      md(s2[x][(i + sz) % w][j] += s2[x * 2 + 1][i][j]);
    }
  }
}
void upd(int x, const int &v) {
  int X = x + N;
  int &c = cnt[X];
  if (v == 1) {
    c += 1;
    for (int i = 0; i <= k; i++) {
      md(s[X][i] += 1ll * pw[c][i] * x % P);
    }
    s2[X][c % w][x % w] += 1;
  } else {
    for (int i = 0; i <= k; i++) {
      md(s[X][i] += P - 1ll * pw[c][i] * x % P);
    }
    s2[X][c % w][x % w] -= 1;
    c -= 1;
  }
  while (X >>= 1) {
    pu(X);
  }
}

void solve() {
  cin >> n >> k >> w;
  vi a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    upd(a[i], 1);
  }
  cin >> q;
  const int ivw = inverse(w);
  while (q--) {
    int x, y;
    cin >> x >> y;
    --x;
    upd(a[x], -1);
    upd(a[x] = y, 1);
    int ans = s[1][k];
    for (int i = 1; i < w; i++) {
      for (int j = 1; j < w; j++) {
        int c = s2[1][i][j];
        md(ans += P - 1ll * c * (1ll * pw[i][k] * j % w) % P);
      }
    }
    cout << 1ll * ans * ivw % P << "\n";
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  for (int i = 0; i < N; i++) {
    pw[i][0] = 1;
    for (int j = 1; j < 6; j++) {
      pw[i][j] = 1ll * pw[i][j - 1] * i % P;
    }
  }
  for (int i = 0; i < 6; i++) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j < i; j++) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
    }
  }
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

D.

考虑枚举最大值，然后判定是否合法。

考虑定义一个左闭右开的 $[l, r)$，若 $[l, r)$ 合法， 则 $ok_{l, r} = ok2_{r,l} = 1$，方便左右扩展，每次就看能否加入，然后 $bfs$ 扩展即可。

const int N = 4005;
ll dp[N][N], a[N][N];
bitset<N> ok[N], ok2[N];
pii b[N * N / 4];
bool t[N][N];
 
void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j += 2) {
      cin >> a[i][j];
      b[a[i][j]] = make_pair(i, j + 1);
    }
  }
  for (int i = 1; i <= n + 1; i++) {
    ok[i][i] = ok2[i][i] = 1;
  }
  for (int val = 1; val <= n * n / 4; val++) {
    auto [i, j] = b[val];
    t[i][j] = 1;
    if (ok[i][j]) {
      continue;
    }
    if (ok[i + 1][j - 1]) {
      ok[i][j] = ok2[j][i] = 1;
    }
    if (!ok[i][j]) {
      continue;
    }
    queue<pii> q;
    q.emplace(i, j);
    while (!q.empty()) {
      auto [x, y] = q.front();
      q.pop();
      if (!ok[x - 1][y + 1] && x > 0 && t[x - 1][y + 1]) {
        ok[x - 1][y + 1] = ok2[y + 1][x - 1] = 1;
        q.emplace(x - 1, y + 1);
      }
      if (!ok[x - 2][y] && x > 1 && t[x - 2][x]) {
        ok[x - 2][y] = ok2[y][x - 2] = 1;
        q.emplace(x - 2, y);
      }
      if (!ok[x][y + 2] && y + 1 <= n && t[y][y + 2]) {
        ok[x][y + 2] = ok2[y + 2][x] = 1;
        q.emplace(x, y + 2);
      }
      auto tmp = (ok[y] & (~ok[x]));
      for (auto t = tmp._Find_first(); t <= n + 1; t = tmp._Find_next(t)) {
        ok[x][t] = ok2[t][x] = 1;
        q.emplace(x, t);
      }
      tmp = (ok2[x] & (~ok2[y]));
      for (auto t = tmp._Find_first(); t <= n + 1; t = tmp._Find_next(t)) {
        ok[t][y] = ok2[y][t] = 1;
        q.emplace(t, y);
      }
    }
    if (ok[1][n + 1]) {
      cout << val << "\n";
      return;
    }
  }
}

E.

60 次询问，每次询问可以知道一个集合内部的边数，问全局有无欧拉回路。

欧拉回路的条件是每个点度数为偶数。

首先记录全局的边数为 total。

• 随机把所有点分成俩集合 $A, B$，查询 $A, B$ 内的边数。
• 如果集合 $A$ 和集合 $B$ 之间的集合只有奇数条边，说明没有欧拉回路。

每次的判断成功的概率是 $1/2$，所以错误率为 $1/2^{29}$。

void solve() {
  int n;
  cin >> n;
  cout << "? " << n;
  rep(i, n) cout << " " << i + 1;
  cout << endl;
  int all;
  cin >> all;
  rep(i, 29) {
    vi a, b;
    int A, B;
    rep(j, n)(rng() & 1 ? a : b).pb(j);
    cout << "? " << sz(a);
    for (auto j : a)
      cout << " " << j + 1;
    cout << endl;
    cin >> A;
    cout << "? " << sz(b);
    for (auto j : b)
      cout << " " << j + 1;
    cout << endl;
    cin >> B;
    if ((all - A - B) % 2 == 1) {
      cout << "! NO" << endl;
      return;
    }
  }
  cout << "! YES" << endl;
}

F.

首先 $a+b = c+d(mod\ m)$ 有解。

手玩会发现，操作 k 次的话，会变成 $(xa - yb, (1-x)a + (1+y)b)$。

其中 $|x|+|y| = |1-x|+|1+y|=2^k$。

然后只需要知道 $a’ = x a + y b = c$，且 $x-y = 2^k$，也就是 $0 < x \leq 2^k$。

$xa + (x-2^k)b = c (mod\ m)$，也就是 $x(a+b) = c + 2^k b(mod\ m)$。

$x = \frac{c + 2^k b}{a+b}$，若 $x = 0$ 时调整成 $m$，只需要判定 $x \leq 2^k$。

void solve() {
  int p, q;
  cin >> p >> q;
  while (q--) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if ((a + b) % p != (c + d) % p) {
      cout << -1 << "\n";
      continue;
    }
    ll bin = 1;
    int l = (a + b) % p;
    int inv = power(l, p - 2, p);
    for (int ans = 0;; ans++) {
      int r = (c + bin * b) % p;
      int x = 1ll * r * inv % p;
      if (x == 0) {
        x = p;
      }
      // debug(l, x, r);
      if (x <= bin) {
        cout << ans << "\n";
        break;
      }
      bin = 2 * bin;
    }
  }
}

G.

考虑枚举 $(i,j)$，不失一般性，假设 $(i,j)$ 为 1 边

• 我们需要找到 $(i, k) (i, l)(j, k)(j, l)$ 都为 0 边，$(k,l)$ 之间的边若为 0 的话，那么符合 Y 条件。
• 我们需要找到 $(i, k)(j, l)$ 为 0 边，$(i, l)(j,k)$ 为 1 边，$(k, l)$ 之间的边若为 0 的话，那么符合 A 条件。

思考为什么是 $(Y - A)$，当 $(k, l)$ 为 1 的时候，两个图是同构的。

所以只需要忽略 $(k, l)$ 的颜色来计算即可。复杂度 $n^3/w$。

ll two(int x) { return 1ll * x * (x - 1) / 2; }

const int N = 2048;
bitset<N> b[N], y[N];
void solve() {
  int n;
  cin >> n;
  rep(i, n) {
    rep(j, n) {
      char c;
      cin >> c;
      
      if (i == j)
        continue;
      if (c == 'B') {
        b[i][j] = 1;
      } else {
        y[i][j] = 1;
      }
    }
  }
  array<ll, 2> ans;
  ans[0] = ans[1] = 0;
  rep(i, n) {
    rep(j, i + 1, n) {
      if (b[i][j]) {
        int c = (y[i] & y[j]).count();
        ans[0] += two(c);
      } else {
        int c = (b[i] & b[j]).count();
        ans[0] += two(c);
      }
      ans[1] += 1ll * (b[i] & y[j]).count() * (b[j] & y[i]).count();
    }
  }
  ans[1] /= 2;
  cout << ans[1] - ans[0] << "\n";
}

H.

构造一个完全图外面套个环。

void solve() {
  int k;
  cin >> k;
  if (k == 1) {
    cout << "2 1" << "\n";
    cout << "1 2" << "\n";
    return;
  }
  if (k == 2) {
    cout << "4 4" << "\n";
    cout << "1 2" << "\n";
    cout << "3 1" << "\n";
    cout << "2 3" << "\n";
    cout << "3 4" << "\n";
    return;
  }
  if (k <= 20) {
    cout << k << " " << k << "\n";
    rep(i, 1, k) cout << i << " " << i + 1 << "\n";
    cout << k << " " << 1 << "\n";
    return;
  }
  for (int a = 2; a <= 17; a++) {
    for (int b = 3; b <= 20 - a; b++) {
      int cnt = b * (b - 1) / 2 - 1 + a - 1 + 2 * (b - 1);
      if (cnt == k) {
        cout << a + b << " " << b * (b - 1) / 2 + a + 1 << "\n";
        rep(i, 1, a) cout << i << " " << i + 1 << "\n";
        for (int i = 1; i <= b; i++) {
          for (int j = i + 1; j <= b; j++) {
            cout << i + a << " " << j + a << "\n";
          }
        }
        cout << 1 << " " << a + 1 << "\n";
        cout << a << " " << a + 2 << "\n";
        return;
      }
    }
  }
}

M.

考虑 $a_i^2 + a_j$ 为完全平方数，首先 $a_i^2 +a_i$ 一定不会是完全平方数，不需要纳入考虑。

否则 $a_j$ 一定形如 $2(a_i + 1) + 2(a_i + 2) + …$，而这种不会超过 $\sqrt W$ 个，其中 $W$ 为值域，所以复杂度 $n \sqrt W$。

ll a[1048576];
int cnt[1048576];
void solve() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    cnt[a[i]] += 1;
  }
  long long ans = 0;
  for (int i = 0; i < n; i++) {
    int x = a[i];
    for (int j = 2 * x + 1; j < 1048576; j += 2 * x + 1) {
      ans += cnt[j];
      x += 1;
    }
  }
 
  cout << ans << "\n";
}