洛谷2022七月月赛

A#

题目描述#

15B03 的座位非常拥挤，可以看成一张的网格，每个小正方形代表一张桌子。

根据规定，考场上任何两张桌子不得相邻。这里相邻指含有 公共点。严格定义两张桌子和相邻当且仅当且。

布置考场的任务落在小 A 头上，他希望撤去最少的桌子满足上述要求。

小 A 认为这样太简单了，因此他添加了限制：在保证撤去桌子最少的前提下，最大化剩余每张桌子到距离它最远的桌子的距离之和。这里距离指 欧几里得 距离：桌子和的距离为。

平行时空中 15B03 的规模不尽相同：多组测试数据。

数据范围#

测试点 #1（15 points）：均为奇数。
测试点 #2（20 points）：。
测试点 #3（25 points）：。
测试点 #4（30 points）：为奇数。依赖测试点 #1，#2。
测试点 #5（10 points）：无特殊限制。依赖测试点 #3，#4。

对于的数据：

Sol#

第一问的答案是。选择奇数行和奇数列的所有交点，可以使得每个的小正方形都存在一个格子被选。当或是奇数时，边界处小正方形不满。这种讨论是平凡的。

这样的构造是上界，因为每个小正方形至多选出一个格子。

对于第二问，我们有如下构造：若横坐标为奇数则横坐标固定，若为偶数则当时选奇数行，否则选偶数行。对于纵坐标同理。这样，四个角均被占用，并且每个位置都取到了它所能贡献的最大值。证明方法是观察到每个的小正方形当中只能恰好放一个，而恰好放的这一个取到了贡献的最大值，具体证明细节略去。

需要特判或的情况。

根据构造算答案即可，时间复杂度。

据验题人反应，第二问难度较大。我们给第一问分以达到送分的目的。

参考代码#

#include <bits/stdc++.h>
#include <quadmath.h>
using namespace std;
bool Mbe;
bool Med;
int main() {
  fprintf(stderr, "%.3lf\n", (&Mbe - &Med) / 1048576.0);
#ifdef ALEX_WEI
  freopen("0.in", "r", stdin);
  freopen("0.out", "w", stdout);
#endif
  int S, T;
  cin >> S >> T;
  while(T--) {
    int n, m;
    double ans = 0;
    cin >> n >> m;
    cout << n * m - (n + 1 >> 1) * (m + 1 >> 1) << " ";
    if(n > 2 || m > 2) {
      if(m == 2) swap(n, m);
      for(int i = 1; i <= n + 1 >> 1; i++)
        for(int j = 1; j <= m + 1 >> 1; j++) {
          int x = i * 2 - 1, y = j * 2 - 1;
          if(n % 2 == 0 && x > n / 2) x++;
          if(m % 2 == 0 && y > m / 2) y++;
          int dx = max(x - 1, n - x);
          int dy = max(y - 1, m - y);
          ans += sqrt(dx * dx + dy * dy);
        }
    }
    printf("%.10lf\n", ans);
  }
  return 0;
}

cpp

B#

题目描述#

小 A 有个的幂。他要在这些数之间插入个异或运算符和个或运算符，组成一个表达式。保证。

表达式越大，越有可能炸掉小 T 的博客。小 A 希望 从左往右 计算表达式时它的值最大。他想知道表达式最大可能的取值是多少，用二进制表示。他还希望你构造出这样的表达式，因为他懒得自己构造了。

若存在多组构造方案，输出任意一组。

多组测试数据。

数据范围#

测试点 #1（10 points）：所有互不相等。
测试点 #2（20 points）：所有相等。
测试点 #3（30 points）：。
测试点 #4（25 points）：。依赖测试点 #3。
测试点 #5（15 points）：无特殊限制。依赖测试点 #1，#2，#4。

对于的数据：

。
。
，。
，即。

Sol#

核心观察：或比异或更厉害。无论之前结果如何，只要在最后一次出现之前放上或就能让这一位变成。

对每个出现偶数次的位，在最后分配一个或就能变为。而出现奇数次的位就算不分配也是。

按位从大到小贪心，时间复杂度。

构造方案：在选择分配或的位的最后一次出现之前放上或。对于多于的或，从后往前填入所有空隙，容易发现不影响答案。剩余空隙放入异或。

参考代码#

#include <bits/stdc++.h>
using namespace std;
bool Mbe;
constexpr int N = 2.5e4 + 5;
constexpr int W = 1 << 16;
int n, x, y, a[N], op[N];
int buc[W], ans[W], lst[W];
bool Med;
int main() {
  fprintf(stderr, "%.3lf\n", (&Mbe - &Med) / 1048576.0);
#ifdef ALEX_WEI
  freopen("0.in", "r", stdin);
  freopen("0.out", "w", stdout);
#endif
  int S, T;
  cin >> S >> T;
  while(T--) {
    memset(op, 0, sizeof(op));
    memset(buc, 0, sizeof(buc));
    memset(ans, 0, sizeof(ans));
    cin >> n >> x >> y;
    for(int i = 1; i <= n; i++) cin >> a[i], buc[a[i]]++, lst[a[i]] = i;
    for(int i = W - 1; ~i; i--)
      if(buc[i] & 1) ans[i] = 1;
      else if(y && buc[i]) ans[i] = op[lst[i]] = 1, y--;
    for(int i = n; y; i--) if(!op[i]) op[i] = 1, y--;
    bool flag = 0;
    for(int i = W - 1; ~i; i--) if(ans[i] || flag) cout << ans[i], flag = 1;
    if(!flag) cout << '0';
    cout << '\n';
    for(int i = 2; i <= n; i++) cout << (op[i] ? '|' : '^');
    cout << '\n';
  }
  return 0;
}

cpp

C#

题目描述#

小 A 一共有道题目没有补。评估后，他认为第题的难度为。

同时，他对自己的水平有评估值。他的水平会波动，因此会改变。

小 A 认为补难度和自己水平相近的题目（相差不超过）能带来收益；相反，如果相差过大（相差超过）则浪费了时间，导致负收益。因此，补第道题的收益为

保证且。

此外，小 A 有一些喜欢和讨厌的题。如果他没有补任何喜欢的题，或补了任何讨厌的题，就会不高兴。

小 A 将选择一段编号连续的题目进行补题。他希望补每道题的收益之和最大，并且补完题目后不会不高兴。请你告诉他这个最大值。

数据范围#

Subtask #1（7 points）：。
Subtask #2（12 points）：。依赖 Subtask #1。
Subtask #3（20 points）：。依赖 Subtask #2。
Subtask #4（25 points）：。
Subtask #5（11 points）：，。
Subtask #6（15 points）：。依赖 Subtask #4。
Subtask #7（10 points）：无特殊限制。依赖 Subtask #3，#5，#6。

对于的数据：

。
，且不大于上界的一半。
。
，，。
保证，递增，且一组询问每个下标至多出现一次。

Sol 1#

考虑。

容易发现，讨厌的题将序列割成若干连续段。连续段之间独立，因此单独考虑一个连续段。

对于当前区间，枚举其所有子区间，检查是否有喜欢的题落在其中并更新答案。

时间复杂度。

Sol 2#

考虑。

注意到对于每个位置，合法的右端点形成一段区间，从右边第一个喜欢的题开始，第一个讨厌的题结束。

将区间求和差分转化为端点最值，每次改变时暴力重新求前缀和，区间最值用线段树或 ST 表维护。

时间复杂度。

Sol 3#

考虑。

回答询问考虑直接枚举包含的喜欢的题，则对应的合法区间左右端点均为一段区间（被讨厌的题所限制）。区间查询前缀和最大最小值即可。

可能的仅有种取值。对每种的取值的对应序列建线段树维护之。

时间复杂度。

Sol 4#

考虑正解。

当从增大到时，仅有次改变某个位置上的贡献的操作。

单点修改相当于对前缀和区间修改，将所有询问离线回答，用线段树维护区间加法区间最值。

时间复杂度，空间复杂度线性。

参考代码#

#include <bits/stdc++.h>
using namespace std;
bool Mbe;
constexpr int N = 1e5 + 5;
int S, n, q, w, b1, b2, inc, dec;
struct event {
  int type, x, id, dt;
  bool operator < (const event &rhs) {
    if(x != rhs.x) return x < rhs.x;
    return type < rhs.type;
  }
} c[N * 5];
int cnt, ans[N];
vector<int> l[N], h[N];
int laz[N << 2], mx[N << 2], mn[N << 2];
void tag(int x, int v) {laz[x] += v, mx[x] += v, mn[x] += v;}
void down(int x) {if(laz[x]) tag(x << 1, laz[x]), tag(x << 1 | 1, laz[x]), laz[x] = 0;}
void push(int x) {
  mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
  mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
}
void build(int l, int r, int x) {
  if(l == r) return mx[x] = mn[x] = ::dec * l, void();
  int m = l + r >> 1;
  build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
  push(x);
}
void modify(int l, int r, int ql, int qr, int x, int v) {
  if(ql <= l && r <= qr) return tag(x, v);
  int m = l + r >> 1;
  down(x);
  if(ql <= m) modify(l, m, ql, qr, x << 1, v);
  if(m < qr) modify(m + 1, r, ql, qr, x << 1 | 1, v);
  push(x);
}
int query(int l, int r, int ql, int qr, int x, int type) {
  int ans = type ? -1e9 : 1e9;
  if(ql > qr) return ans;
  if(ql <= l && r <= qr) return type ? mx[x] : mn[x];
  int m = l + r >> 1;
  down(x);
  if(ql <= m) ans = query(l, m, ql, qr, x << 1, type);
  if(m < qr) {
    int v = query(m + 1, r, ql, qr, x << 1 | 1, type);
    ans = type ? max(ans, v) : min(ans, v);
  }
  return ans;
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf\n", (&Mbe - &Med) / 1048576.0);
#ifdef ALEX_WEI
  freopen("0.in", "r", stdin);
  freopen("0.out", "w", stdout);
#endif
  cin >> S;
  cin >> n >> q >> w >> b1 >> b2 >> inc >> ::dec;
  for(int i = 1, x; i <= n; i++) {
    cin >> x;
    c[++cnt] = {1, x - b2, i, -::dec};
    c[++cnt] = {1, x - b1, i, inc};
    c[++cnt] = {1, x + b1 + 1, i, -inc};
    c[++cnt] = {1, x + b2 + 1, i, ::dec};
  }
  for(int i = 1; i <= q; i++) {
    int op, L, H, il, ih;
    cin >> op;
    if(op == 2) {cin >> w; continue;}
    cin >> L >> H;
    while(L--) cin >> il, l[i].push_back(il);
    while(H--) cin >> ih, h[i].push_back(ih);
    c[++cnt] = {2, w, i};
  }
  sort(c + 1, c + cnt + 1);
  build(0, n, 1);
  for(int i = 1; i <= cnt; i++) {
    event t = c[i];
    if(t.type == 2) {
      int id = t.id, res = -1e9, lst = 0, pt = 0;
      h[id].push_back(n + 1);
      for(int it : l[id]) {
        while(it > h[id][pt]) lst = h[id][pt++];
        res = max(res, query(0, n, it, h[id][pt] - 1, 1, 1) - query(0, n, lst, it - 1, 1, 0));
      }
      ans[id] = res;
    }
    else modify(0, n, t.id, n, 1, t.dt);
  }
  for(int i = 1; i <= q; i++) if(l[i].size()) printf("%d\n", ans[i]);
  return 0;
}

cpp

D#

题目描述#

以下是简化后的扫雷游戏规则：

定义连通为 八连通。
如果打开雷，所有雷全部爆炸，游戏结束。
如果打开空地，若其周围没有雷，则递归打开周围八个空地。
如图 ↗，点开任意红色框内方块均形成当前局面。

给定一张的初始地图。小 A 决定搜出所有可能的局面，并找到最优鼠标点击顺序，从而速通这张地图。

为设置合适的数组大小，小 A 需要知道有多少种不同局面。对取模。

如果方块是雷，它有爆炸和未爆炸两种状态；如果方块是空地，它有打开和未打开两种状态。
两个局面不同，当且仅当存在方块状态不同。
保证周围无雷的空地形成不超过个连通块。

数据范围#

设周围无雷的空地形成个连通块。

Subtask #1（15 points）：。
Subtask #2（4 points）：地图中只有一个雷。
Subtask #3（5 points）：。
Subtask #4（6 points）：。
Subtask #5（7 points）：。
Subtask #6（8 points）：。依赖 Subtask #1，#2，#3，#4，#5。
Subtask #7（9 points）：。依赖 Subtask #6。
Subtask #8（16 points）：。依赖 Subtask #7。
Subtask #9（17 points）：。依赖 Subtask #8。
Subtask #10（13 points）：无特殊限制。依赖 Subtask #9。

对于的数据：

。
。
不保证 地图中有雷或空地。

Sol 1#

考虑。

称「有雷空地」为周围有雷的空地，「无雷空地」为周围无雷的空地。

地图中没有无雷空地，每个空地的状态独立。设共有个有雷空地，根据乘法原理，答案为，其中表示是否存在雷。

直接枚举空地及其周围空地求出，时间复杂度为。

将不计入雷的局面数乘即可得到计入雷的局面数。
为叙述方便，下文中提到的局面均不计入点到雷的局面。

Sol 2#

考虑。

若空地周围存在无雷空地，当无雷空地打开时，该空地也同时打开。空地之间的状态并不独立。

设打开无雷空地形成的连通块将打开个有雷空地。当连通块未打开时，个有雷空地的状态独立，有种局面；当连通块打开时，个有雷空地同时被打开，剩余个有雷空地的状态独立，有种局面。

存在初始地图中没有雷的情况，此时答案为；否则答案为。

容易 dfs 求出，时间复杂度为。

Sol 3#

考虑。

将无雷空地形成的两个八连通块标上序号。设打开第个连通块时打开的有雷空地个数为。

讨论连通块的状态：

若连通块都未打开，共有种局面。
若连通块打开，连通块未打开，沿用的做法，共有种局面。
同理，若连通块打开，连通块未打开，共有种局面。
若连通块都打开，共有种局面。

分析第四种情况：直接按照这种思路写甚至过不了样例，因为两个连通块可能打开相同的有雷空地。如的网格，左上角和右下角均为雷，则左下角和右上角的两个连通块同时打开中心空地。

设打开两个连通块时打开的相同有雷空地个数为。

在计算连通块影响到的有雷空地个数时，上述结论多统计了个空地。此时应仅有个有雷空地被打开，其余个有雷空地的状态独立。

答案为。

dfs 求出与，时间复杂度为。

Sol 4#

考虑。

设表示恰好同时被连通块集合打开的有雷空地数，可以 dfs 求出。

枚举打开的连通块集合，则答案为。

直接枚举子集，时间复杂度。

Sol 5#

考虑。

用 FMT 优化上式，时间复杂度。

Sol 6#

考虑。

枚举子集的复杂度无法做到更优，考虑挖掘性质。

结论：一个有雷空地至多被两个连通块打开。

证明：

若一个有雷空地同向的两个角落的方块均为无雷空地，则这两个无雷空地一定在同一连通块，因为它们中间的方块是无雷空地。
一个有雷空地的上下和左右两个方块不可能均为无雷空地，否则该有雷空地为无雷空地。

根据上述限制，一个有雷空地最多被三个连通块打开，且其周围状态只能为：

? 0 ?
0 * ?
? ? 0

plaintext

其中 * 表示有雷空地，0 表示无雷空地，? 表示不重要的方块。

根据周围三个无雷空地的限制，中间的有雷空地为无雷空地，矛盾。得证。

因此仅在处有值。在此基础上得以求出。

对于，设为中编号最小的连通块，则。可以 lowbit 求得。

综上，时空复杂度。

进一步地，可以将空间复杂度优化至。

时间复杂度仍然是。如果不放心，利用主定理求解，解得。

Sol 7#

考虑。

根据 Sol 6 的结论，将连通块抽象成点，令两个节点之间的权值为它们同时打开的空地数。若视之间连边。

每次枚举度数最大的节点的两种状态，考虑它对剩余节点的影响，并删掉该点。形成的连通块之间独立，分别暴搜。可以通过本题，但不会分析复杂度的算法不适合当正解。

我们给出优于的 确定性 做法：

整张地图是二维平面，所以建出的图是平面图。根据四色定理，的最大独立集不小于。最大独立集可以在或的时间内求得，以下做法摘自 pb 的《浅谈信息学竞赛中的独立集问题》学习笔记 ↗。

设表示点集上的最大独立集，令为中编号最大的节点，有。因为前层只有种递归的可能，后层中最大节点不超过，所以总共只有种状态，对这些状态记忆化即可做到。

对做 Sol 6，内所有点的状态独立，可以考虑。

时间复杂度，空间复杂度。

Sol 8#

考虑正解。

中的点一旦独立，即可直接考虑贡献，不需要等到确定所有节点的状态后再计算。因此，令的一个排列的代价为，表示内所有节点以的顺序独立的时间代价：独立时，均独立，需要删去内所有节点。

当较小时，枚举其所有排列并求出代价，否则随机足够多的排列使代价尽可能小。

得到最优排列后，求出对应删点顺序，并在对应时刻计算内某些节点的代价。

对于而言，的最小值为，此时可以全排列求最小代价。在卡到最小值的图中几乎不可能使得大于（出题人尝试构建这样的图，均无法保证）。若更大，则变小，随机排列足够优秀。

复杂度可近似看做。

本题出题人即笔者。一开始的想法是从 windows 的经典游戏中获取灵感，出了两道月赛 D 难度的题目。一道关于蜘蛛纸牌，已经放在了 SWTR-07，另一道是本题。

本题考察了选手对乘法原理，容斥原理，状压 DP 和随机乱搞的运用能力，以及将问题从实际情境中抽离却不脱离实际情境的能力。本题将优化掉并获得更优时间复杂度的关键结论隐藏在背景当中。

最初正解的复杂度为，提交审核时，粉兔指出本题有无脑 FMT 做法，大幅拉低本题水准，故撤下。出题人抓住关键性质，不断思考后得到做法。同时，出题人认为验题人 chenxia25 给出的空间做法具有一定启发性，故二次加强了本题。

进一步地，验题人 asmend 给出复杂度玄学的暴搜做法，出题人实现后发现效率惊人。不仅因为题目的实际意义限制了造出强的数据非常困难，而且是平面图。

对于完全图而言暴搜不可行，但甚至不存在和，所以暴搜本身复杂度可能就是正确的，加上一点随机化难以卡掉。

出题人请教 EI 后，他指出可以通过删去最大独立集以外的所有顶点实现较多节点的独立。结合平面图四色定理（最大独立集不小于点集的四分之一）与求解一般图最大独立集，出题人得到本题正解的基本思路。

出题人尝试卡掉暴力无果，实现 Sol 7 后发现速度太慢，无法通过且卡到最小值的数据。尝试优化后得到最终正解。

出题人实现的基于随机化的最优秀暴力需要 2.1s，而 Sol 8 在出题人造出的最劣数据下仅需要 1.6s。因为难以估计 Sol 8 的复杂度上界，所以出题人将时间限制设为 3s。

也许这是第一次四色定理和最大独立集被应用在正经 OI 题当中。因为这一点，出题人认为本题是一道非常新颖有趣的问题，可惜暴力搜索可以通过。

单论本题正解，其难度堪比 Div.1 C 或 D。出题人将其放在 Div.2 D / Div.1 B 的位置，因为暴力搜索被定位为 intended solution。按照其难度判断，本题放在 2D / 1B 比较合适。

参考代码#

#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
bool Mbe;
constexpr int N = 500 + 5;
constexpr int D = 37 + 5;
constexpr int mod = 998244353;
constexpr int dx[8] = {-1, 0, 0, 1, -1, -1, 1, 1};
constexpr int dy[8] = {0, -1, 1, 0, -1, 1, -1, 1};

int S, n, m, cmine, pw2[N * N];
int cur, mine, open[D], e[D][D];
namespace MAP {
  int label[N][N];
  bool hmine[N][N], vis[N][N];
  char mp[N][N];
  void dfs_map(int i, int j) {
    vis[i][j] = 1;
    for(int dir = 0; dir < 8; dir++) {
      int x = i + dx[dir], y = j + dy[dir];
      if(mp[x][y] != '.') continue;
      if(hmine[x][y] && label[x][y] != cur) {
        if(label[x][y] != -1) e[label[x][y]][cur]++;
        label[x][y] = cur, open[cur]++;
      }
      if(!vis[x][y] && !hmine[x][y]) dfs_map(x, y);
    }
  }
  void solve() {
    for(int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);
    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= m; j++)
        if(mp[i][j] == '.') {
          for(int dir = 0; dir < 8; dir++) hmine[i][j] |= mp[i + dx[dir]][j + dy[dir]] == '*';
          cmine += hmine[i][j];
        }
        else mine = 1;
    memset(label, -1, sizeof(label));
    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= m; j++)
        if(mp[i][j] == '.' && !hmine[i][j] && !vis[i][j])
          dfs_map(i, j), cur++;
    for(int i = 0; i < cur; i++)
      for(int j = 0; j < i; j++)
        e[i][j] = e[j][i];
    for(int i = 0; i < cur; i++)
      for(int j = 0; j < cur; j++)
        open[i] -= e[i][j];
    for(int i = 0; i < cur; i++) cmine -= open[i];
    for(int i = 0; i < cur; i++)
      for(int j = i; j < cur; j++)
        cmine -= e[i][j];
  }
}

ll ar[D], I;
namespace MIS {
  int f[1 << 19];
  ll get(ll x, ll y) {return __builtin_popcountll(x) > __builtin_popcountll(y) ? x : y;}
  ll dfs_I(ll S) {
    if(!S) return 0;
    int bit = 63 - __builtin_clzll(S);
    ll x = S ^ (1ll << bit), y = x ^ (x & ar[bit]); 
    if(S >= (1 << 19)) return get(dfs_I(x), dfs_I(y) ^ (1ll << bit));
    else {
      if(f[S] != -1) return f[S];
      return f[S] = get(dfs_I(x), dfs_I(y) ^ (1ll << bit));
    }
  }
  void solve() {
    for(int i = 0; i < cur; i++)
      for(int j = 0; j < cur; j++)
        if(e[i][j])
          ar[i] |= 1ll << j;
    memset(f, -1, sizeof(f));
    I = dfs_I((1ll << cur) - 1);
  }
}

int limit, mark[D];
namespace LAB {
  int p[D], q[D], best[D], te[D][D], to[D];
  void solve() {
    limit = cur - __builtin_popcountll(I);
    int cnt = 0, minc = 1 << 30;
    for(int i = 0; i < cur; i++)
      if(I >> i & 1)
        q[cnt++] = i;
    int T = 1e6;
    while(T--) {
      shuffle(q, q + cnt, rnd);
      int cost = 0;
      long long msk = 0;
      for(int i = 0; i < cnt; i++) {
        msk |= ar[q[i]];
        cost += 1ll << __builtin_popcountll(msk);
      }
      if(cost < minc) {
        minc = cost;
        for(int i = 0; i < cnt; i++) best[i] = q[i];
      }
    }
    int index = 0;
    long long msk = 0;
    for(int i = 0; i < cnt; i++) {
      for(int j = 0; j < cur; j++)
        if((msk >> j & 1 ^ 1) && (ar[best[i]] >> j & 1))
          p[index] = j, mark[++index] = i;
      msk |= ar[best[i]];
    }
    for(int i = 0; i < cur; i++)
      if((msk | I) >> i & 1 ^ 1)
        p[index] = i, mark[++index] = cnt;
    for(int i = 1; i <= cnt; i++) p[index++] = best[cnt - i];
    for(int i = 0; i < cur; i++)
      for(int j = 0; j < cur; j++)
        te[i][j] = e[p[i]][p[j]];
    for(int i = 0; i < cur; i++)
      for(int j = 0; j < cur; j++)
        e[i][j] = te[i][j];
    for(int i = 0; i < cur; i++) to[i] = open[p[i]];
    for(int i = 0; i < cur; i++) open[i] = to[i];
  }
}

int dfs_ans(int p) {
  if(p == limit) {
    int res = 1;
    for(int i = p; i < cur - mark[p]; i++) res = 1ll * res * (pw2[open[i]] + 1) % mod;
    return res;
  }
  int res = dfs_ans(p + 1);
  for(int i = p + 1; i < cur - mark[p + 1]; i++) open[i] += e[p][i];
  res = (res + 1ll * pw2[open[p]] * dfs_ans(p + 1)) % mod;
  for(int i = p + 1; i < cur - mark[p + 1]; i++) open[i] -= e[p][i];
  if(mark[p + 1] != mark[p])
    for(int x = mark[p] + 1; x <= mark[p + 1]; x++)
      res = 1ll * res * (pw2[open[cur - x]] + 1) % mod;
  return res;
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf\n", (&Mbe - &Med) / 1048576.0);
#ifdef ALEX_WEI
  freopen("0.in", "r", stdin);
  freopen("0.out", "w", stdout);
#endif
  cin >> S >> n >> m;
  for(int i = pw2[0] = 1; i <= n * m; i++) pw2[i] = pw2[i - 1] * 2 % mod;
  MAP::solve();
  MIS::solve();
  LAB::solve();
  cout << (mine ? 2ll : 1ll) * dfs_ans(0) * pw2[cmine] % mod << endl;
  return 0;
}

cpp

E#

题目描述#

给定一张个点，条边的无向图。每条边标有 D 或 d。

定义无序点对是「铁的」，当且仅当且之间存在同时出现 D 和 d 的简单路径。

小 A 深知自由组合定律 DdTt 的重要性，所以他让你对这样的点对计数。

注意：

简单路径定义为不经过重复节点的路径。
保证图无自环，连通，可能有重边。

数据范围#

Subtask #1（6 points）：，。
Subtask #2（16 points）：，。依赖 Subtask #1。
Subtask #3（17 points）：。
Subtask #4（18 points）：。
Subtask #5（19 points）：，。依赖 Subtask #2。
Subtask #6（24 points）：无特殊限制。依赖 Subtask #3，#4，#5。

对于的数据：

，。
。
。
保证图无自环，连通，可能有重边。

Sol#

补集转化变成不存在同时出现 D（1）和 d（0）的简单路径。

如果点对之间不存在出现的路径，只有以下三种情况：

只有路径。
只有路径。
同时有路径和路径。

接下来的推导需多次应用如下基本事实：

性质 1：对于点数的点双，任给两点，存在经过的简单环。

点双基本性质。若不直接相连，由门杰定理 ↗ 的特殊情形可证。若直接相连，若删去后不连通，不妨设所在连通块大小，则为原图割点，矛盾，因此删去后连通，从而得到经过的简单环。证毕。

Part 1#

对于只有路径的情况，考虑点双，容易猜测若存在边则经过的点对不合法。

性质 2：对于点数的点双，任给一点与一边，存在经过的简单环。

证明：将拆成和不影响点双连通性。据性质 1，存在经过的简单环。因仅与相连，故在环上，将其替换为可得经过的简单环。证毕。

不影响点双连通性的证明：删去或，因与或连通且删去或后连通可知不是割点；删去以外的点时，将和视为，连通；删去相当于删去，若图不连通则在上为割边，当点数时或在上为割点，矛盾，故连通。

性质 3：对于点数的点双，点双内任给两点与一边，存在的简单路径。

证明：由性质 2，存在经过的简单环，若显然成立，否则令为任意路径，考虑与的第一个交点，存在使得的，否则为割点：删去后无法到达剩余节点。令接上通过环上有的一侧到的路径，则为的简单路径。证毕。

令为边，对点双内任意两点应用性质 3，结合的平凡情况，可得

结论 1：若点双内存在边，则经过该点双的点对不合法。

因此，删去有边的点双内部所有边，剩余连通块大小选之和即为所求。

对于只有路径的情况同理。

Part 2#

同时有路径和路径的点对是本题重点，下称「合法点对」。

结论 2：若两点之间存在割点，则不合法。

证明：设间存在割点。考虑和的所有路径，它们仅在处相交，否则与为割点矛盾。若同时存在路径和路径，将在的部分和在的部分相接得到路径，不合法。证毕。

可以推出合法点对属于相同点双，考虑点双，感性猜测内部最多有一对合法对，接下来证明这一点。

考虑合法点对。令所有路径覆盖点集，所有路径覆盖点集。

结论 3.1：除以外，与无交。

证明：若有交，则可通过与第一个交点调整得到路径。证毕。

结论 3.2：与之间无边。

证明：若有边满足，则为路径。证毕。

性质 4：对于点数的点双，任给不同三点，存在经过且以为端点的简单路径。

证明：由性质 1，存在经过的简单环，若显然成立，否则令为任意路径，考虑与的第一个交点，存在使得的，否则为割点：删去后无法到达剩余节点。令接上通过环上有的一侧到的路径，则为经过且以为端点的简单路径。证毕。

结论 3.3：。

证明：对任意应用性质 4，证毕。

考虑，且。

结论 4：存在分别到或的两条仅经过的不交路径。

证明：若或与或相等，显然。否则考虑仅经过的的任意有序路径，的任意有序路径，令它们的交点为。若或，可得同时经过的路径且分别在两端，显然。否则将按照在中的出现顺序标号，注意。令两侧与距离最近的两个交点分别为与，则令

这样，与的所有交点按顺序出现，即令与的交点为，将按照在中的出现顺序标号为，则上出现顺序也为。设两侧与距离最近的两个交点分别为与，为与。当时，令，，合法。当时只需反过来构造即可。证毕。

因此，对于任意，存在分别到或的两条仅经过的不交路径。将这两条路径通过之间的全路径连起来，得之间不合法。

同理，对于任意，之间不合法。

而，且之间显然不合法。

综上，内部最多有一对合法对。

考虑充要条件，其等价于点双内恰好存在两个点满足同时有出边。

充分性：考虑令唯二的两个点分别为。根据性质 4，考虑任意，路径必然纯色，否则考虑切换颜色的点，该点同时存在出边。因同时有出边，故存在全路径和全路径。

必要性：当合法时，根据结论 3.2 可知仅有同时有出边。

问题在的时间内解决。

参考代码#

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
bool Mbe;
constexpr int N = 1e6 + 5;
struct solver {
  int cnt, hd[N], nxt[N << 1], to[N << 1];
  void add(int u, int v) {
    nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v;
    nxt[++cnt] = hd[v], hd[v] = cnt, to[cnt] = u;
  }
  int sz, vis[N];
  void dfs(int id) {
    vis[id] = 1, sz++;
    for(int i = hd[id]; i; i = nxt[i]) if(!vis[to[i]]) dfs(to[i]);
  }
  long long solve(int n) {
    long long ans = 0;
    for(int i = 1; i <= n; i++)
      if(!vis[i]) {
        sz = 0, dfs(i);
        ans += 1ll * sz * (sz - 1) / 2;
      }
    return ans;
  }
} D, d;
char c[N];
int S, n, m, node, u[N], v[N];
int dn, dfn[N], low[N], top, stc[N];
vector<int> e[N], g[N];
void tarjan(int id) {
  dfn[id] = low[id] = ++dn, stc[++top] = id;
  for(int it : e[id]) {
    if(!dfn[it]) {
      tarjan(it), low[id] = min(low[id], low[it]);
      if(low[it] >= dfn[id]) {
        g[++node].push_back(id);
        g[id].push_back(node);
        for(int x = 0; x != it; ) {
          g[node].push_back(x = stc[top--]);
          g[x].push_back(node);
        }
      }
    }
    else low[id] = min(low[id], dfn[it]);
  }
}
int have[N], fa[N];
long long ans;
gp_hash_table<int, int> mp[N];
void dfs(int id, int ff) {
  fa[id] = ff;
  for(int it : g[id]) if(it != ff) dfs(it, id);
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0);
#ifdef ALEX_WEI
  freopen("0.in", "r", stdin);
  freopen("0.out", "w", stdout);
#endif
  cin >> S >> n >> m, node = n;
  ans = 1ll * n * (n - 1) / 2;
  for(int i = 1; i <= m; i++) {
    cin >> u[i] >> v[i] >> c[i];
    e[u[i]].push_back(v[i]), e[v[i]].push_back(u[i]);
  }
  tarjan(1), dfs(node, 0);
  auto get = [&](int id, int it) {
    if(fa[id] == fa[it]) return fa[id];
    if(fa[fa[id]] == it) return fa[id];
    return fa[it];
  };
  for(int i = 1; i <= m; i++) {
    int bcc = get(u[i], v[i]), msk = 1 << (c[i] == 'D');
    mp[bcc][u[i]] |= msk, mp[bcc][v[i]] |= msk;
    have[bcc] |= msk;
  }
  for(int i = 1; i <= m; i++) {
    int bcc = get(u[i], v[i]);
    if((have[bcc] & 1) ^ 1) D.add(u[i], v[i]);
    if((have[bcc] & 2) ^ 2) d.add(u[i], v[i]);
  }
  ans -= D.solve(n) + d.solve(n);
  for(int i = n + 1; i <= node; i++) {
    int cnt = 0;
    for(auto it : mp[i]) cnt += it.second == 3;
    ans -= cnt == 2;
  }
  cout << ans << endl;
  return 0;
}

cpp

F#

题目描述#

如果小 A 是一个，一个一个一个毒瘤，他会让你求解套了十层甚至九层娃的幂塔方程，但他不是。

他想让你求解：

保证的最大质因子不超过，且与互质。

你需要保证得到的解为范围内的整数。若该范围内无解，输出；若存在多解，输出任意一个。

多组测试数据。

数据范围#

Subtask #1（5 points）：。
Subtask #2（8 points）：。依赖 Subtask #1。
Subtask #3（11 points）：是质数，。
Subtask #4（15 points）：，。
Subtask #5（9 points）：，。依赖 Subtask #4。
Subtask #6（13 points）：，。
Subtask #7（7 points）：，。依赖 Subtask #3，#6。
Subtask #8（6 points）：。依赖 Subtask #2。
Subtask #9（16 points）：，。
Subtask #10（10 points）：无特殊限制。依赖 Subtask #5，#7，#8，#9。

对于的数据：

。
。
，。
。

Sol 0#

验题人 chenxia25 给出了一个假做法：将分解质因数，对于每个可以单独求解。然后 excrt 合并。

问题在于很大，且可能不互质，但对于单独求解的得到的解互质（因为有多解），导致同余方程合并时无解。

Sol 1#

考虑。

令为和的解，容易发现存在。

Sol 2#

考虑。

考虑 增量法构造。

设。考虑如何推到。

容易发现令仍然可行，因此设。

考虑求出。因为，所以。

因为和互质，所以必然和互质，所以和互质，故和互质。欧拉定理可以用。

因为，所以，因此。

这是一个 n 次剩余的形式。但是太大，无法使用 BSGS 求解。

注意到的大于次方等于，考虑 二项式展开。

令，则，即。

因为，所以是的倍数。设，则，显然，因此在模意义下的逆元存在，据此可求出。

注意到，因此，构造出的解远小于这一上界，算法可行。

时间复杂度约为。

Sol 3#

考虑是 square free number。

考虑 增量法构造。

设的质因子分别为，令，。

设，考虑如何从推到。

如法炮制，发现令仍然可行，因此设。但是再走二项式展开的老路就行不通了，因为。

怎么办呢？注意到若需保证，因为必然有且，根据中国剩余定理，只需保证。发现还是很不好做，因为同时在底数和指数上，而且。

考虑化去指数上的。

尝试改变定义，令，因为，这为接下来寻找逆元奠定基础（如果令，实际上相当于给加上的循环节的倍数的倍数，显然不可行，因为当且仅当已经符合要求时我们能找到合法的）且。

这样一来，上式化简为。求解该 n 次剩余，令为的任意原根，，则。

此时出现了一个严重的问题。分子的在模意义下求解，但和可能不互质。

尝试修补这个问题。即尝试令。

接下来是一步巧妙转化：令，使得。

但是又出现了问题，即可能和不互质。

给出引理：若，则对于任意，存在使得。

证明：将分解质因数成的形式。容易证明或。若非，说明和同时含有质因子，与假设矛盾。又因为若，显然，即在模意义下。根据中国剩余定理，得证。

我们发现这是一个递归形式的问题，即若 归纳假设 ，则能找到这样的使得，且上述引理给出了一个求解的方法，即对分解质因数并 CRT 合并。而 若条件满足，则结论满足，推出下一轮的条件仍满足：，又因为，所以。

同时，当在构造第一步时，Sol 2 满足归纳的初始条件，因为且，显然。

梳理一下上面的思路，发现添加限制之后，为了满足该性质所需进行的操作的正确性被该性质所保证，而一开始性质满足，故正确性得以保证。这是归纳法非常巧妙的应用。

这样，我们解决了可能无解的问题。

与互质，其在模意义下存在逆元。我们得以算出，从扩展至。

时间复杂度约为：预处理以内每个质数（约个）的原根（单次复杂度）。BSGS 求解离散对数方程时模数非常小，不需要 map 或哈希表，用数组记录即可。

由于均为级别，因此对应的和的一个粗略上界为，略小于的限制，符合要求。若担心超出上界，可以令对取模。

Sol 4#

结合 Sol 2 和 Sol 3，从小到大考虑所有质因子。若相邻两个质因子相同，则使用 Sol 2，将对应的换成；否则使用 Sol 3 即可。

接下来是一些细节讨论：

在 Sol 2 使用欧拉定理时，需要。考虑包含个质因子，则也包含个质因子（根据欧拉定理的计算式可得）。同时，所有形如的乘积项被消去，因此上式仍然成立。
在 Sol 2 二项式展开时，需要的大于次幂是的倍数。显然成立，因为。
在 Sol 2 求解时，需要在模意义下存在。由于分子，分母和模数均为的倍数，因此同除后分母和互质，这是因为显然和互质，且。
在 Sol 3 中的归纳假设需要在 Sol 2 中满足，因为我们会交替使用 Sol 2 和 Sol 3。因为 Sol 2 的初始条件成立，所以。因为相较于没有增加更多质因子，所以显然。

综上，时间复杂度，常数较大。

可以获得 100 分的好成绩。

接下来是一些补充：

在求解时，可以每次给加上直到符合要求而非 CRT 求解。因为每次加上可以看做从中随机选一个数，期望随机次（初始状态算一次）即可得到与互质的。
笔者认为本题是一道不可多得的数论好题。尽管其形式简单，但却涉及到了 exgcd 求逆元，CRT 合并同余方程，BSGS 求解离散对数和 n 次剩余问题。归纳法用得恰到好处。整个算法优美而简洁，思维难度极高。没有冗余步骤，只是纯粹的数论。

参考代码#

#include <bits/stdc++.h>
using namespace std;
bool Mbe;
using ll = long long;
using i128 = __int128;
inline ll read() {
  ll x = 0;
  char s = getchar();
  while(!isdigit(s)) s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return x;
}
inline void print(i128 x) {
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
constexpr int N = 1e5 + 5;
constexpr int W = 64;
namespace math {
  ll ksm(ll a, i128 b, ll p) {
    ll s = 1;
    while(b) {
      if(b & 1) s = (i128) s * a % p;
      a = (i128) a * a % p, b >>= 1;
    }
    return s;
  }
  i128 gcd(i128 x, i128 y) {return !y ? x : gcd(y, x % y);}
  void exgcd(int a, int b, int &x, int &y) {
    if(!b) return x = 1, y = 0, void();
    exgcd(b, a % b, y, x), y -= a / b * x;
  }
  int inv(int x, int p) {
    exgcd(x, p, x, *new int);
    return (x % p + p) % p;
  }
  int val[N];
  int BSGS(int a, int b, int p) {
    int A = 1, B = sqrt(p) + 1;
    for(int i = 0; i < B; i++) {
      val[1ll * A * b % p] = i;
      A = 1ll * A * a % p;
    }
    for(int i = 1, AA = A; i <= B; i++) {
      if(val[AA] != -1) {
        int ans = i * B - val[AA];
        for(int i = 0, A = 1; i < B; i++) {
          val[1ll * A * b % p] = -1;
          A = 1ll * A * a % p;
        }
        return ans;
      }
      AA = 1ll * AA * A % p;
    }
    return -1;
  }
}
int pc, vis[N], pr[N], g[N];
void sieve() {
  for(int i = 2; i < N; i++) {
    if(!vis[i]) pr[++pc] = i;
    for(int j = 1; j <= pc && i * pr[j] < N; j++) {
      vis[i * pr[j]] = 1;
      if(i % pr[j] == 0) break;
    }
    if(vis[i]) continue;
    static int pf[N];
    int cnt = 0, tmp = i - 1;
    for(int j = 2; j * j <= tmp; j++)
      if(tmp % j == 0) {
        pf[++cnt] = j;
        while(tmp % j == 0) tmp /= j;
      }
    if(tmp > 1) pf[++cnt] = tmp;
    for(int j = 1; j < i && !g[i]; j++) {
      bool ok = 1;
      for(int k = 1; k <= cnt; k++)
        ok &= math::ksm(j, (i - 1) / pf[k], i) != 1;
      if(ok) g[i] = j;
    }
  }
}
i128 ans;
ll n, D, P[W], Q[W];
int cnt, p[W];
void init() {
  P[0] = Q[0] = 1, cnt = 0;
  ll tmp = n;
  while(tmp > 1) {
    int pf = read();
    while(tmp % pf == 0) {
      p[++cnt] = pf, tmp /= pf;
      P[cnt] = P[cnt - 1] * pf;
      Q[cnt] = Q[cnt - 1] * (pf - 1);
    }
  }
  ll M = 1ll * p[1] * (p[1] - 1);
  ans = (D % p[1] * (p[1] - 1) * (p[1] - 1) + p[1]) % M;
}
#define mod p[i + 1]
void same(int i) {
  ll v = math::ksm(ans % P[i + 1], ans, P[i + 1]);
  i128 I = (D - v + P[i + 1]) % P[i + 1] / P[i];
  I = I * math::inv(Q[i] % mod * (v % mod) % mod, mod) % mod;
  ans += I * P[i] * Q[i];
}
void diff(int i) {
  i128 prod = (i128) P[i] * Q[i];
  while(math::gcd(ans, mod - 1) != 1) ans += prod;
  prod *= mod - 1;
  ll u = math::BSGS(g[mod], D % mod, mod);
  i128 I = math::ksm(g[mod], u * math::inv(ans % (mod - 1), mod - 1), mod);
  I = (I + mod - ans % mod) * math::inv(prod % mod, mod) % mod;
  ans += I * prod;
}
void solve() {
  n = read(), D = read(), init();
  for(int i = 1; i < cnt; i++) {
    p[i] == p[i + 1] ? same(i) : diff(i);
    ans %= (i128) P[i + 1] * Q[i + 1];
  }
  print(ans), putchar('\n');
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf\n", (&Mbe - &Med) / 1048576.0);
#ifdef ALEX_WEI
  freopen("0.in", "r", stdin);
  freopen("0.out", "w", stdout);
#endif
  sieve();
  memset(math::val, -1, sizeof(math::val));
  int S, T;
  cin >> S >> T;
  while(T--) solve();
  return cerr << clock() << endl, 0;
}

cpp

A#

题目描述#

数据范围#

Sol#

参考代码#

B#

题目描述#

数据范围#

Sol#

参考代码#

C#

题目描述#

数据范围#

Sol 1#

Sol 2#

Sol 3#

Sol 4#

参考代码#

D#

题目描述#

数据范围#

Sol 1#

Sol 2#

Sol 3#

Sol 4#

Sol 5#

Sol 6#

Sol 7#

Sol 8#

参考代码#

E#

题目描述#

数据范围#

Sol#

Part 1#

Part 2#

参考代码#

F#

题目描述#

数据范围#

Sol 0#

Sol 1#

Sol 2#

Sol 3#

Sol 4#

参考代码#

Comments