A组大佬太强了不敢发，就发博客上了。
T1 排水系统
[NOIP2020] 排水系统
题目描述
对于一个城市来说，排水系统是极其重要的一个部分。
有一天，小 C 拿到了某座城市排水系统的设计图。排水系统由 \(n\) 个排水结点（它们从 \(1 \sim n\) 编号）和若干个单向排水管道构成。每一个排水结点有若干个管道用于汇集其他排水结点的污水（简称为该结点的汇集管道），也有若干个管道向其他的排水结点排出污水（简称为该结点的排出管道）。
排水系统的结点中有 \(m\) 个污水接收口，它们的编号分别为 \(1, 2, \ldots , m\)，污水只能从这些接收口流入排水系统，并且这些结点没有汇集管道。排水系统中还有若干个最终排水口，它们将污水运送到污水处理厂，没有排出管道的结点便可视为一个最终排水口。
现在各个污水接收口分别都接收了 \(1\) 吨污水，污水进入每个结点后，会均等地从当前结点的每一个排出管道流向其他排水结点，而最终排水口将把污水排出系统。
现在小 C 想知道，在该城市的排水系统中，每个最终排水口会排出多少污水。该城市的排水系统设计科学，管道不会形成回路，即不会发生污水形成环流的情况。
输入格式
第一个两个用单个空格分隔的整数 \(n, m\)。分别表示排水结点数与接收口数量。
接下来 \(n\) 行，第 \(i\) 行用于描述结点 \(i\) 的所有排出管道。其中每行第一个整数 \(d_i\) 表示其排出管道的数量，接下来 \(d_i\) 个用单个空格分隔的整数 \(a_1, a_2, \ldots , a_{d_i}\) 依次表示管道的目标排水结点。
保证不会出现两条起始结点与目标结点均相同的管道。输出格式
输出若干行，按照编号从小到大的顺序，给出每个最终排水口排出的污水体积。其中体积使用分数形式进行输出，即每行输出两个用单个空格分隔的整数 \(p\)，\(q\)，表示排出的污水体积为 \(\frac{p}{q}\)。要求 \(p\) 与 \(q\) 互素，\(q = 1\) 时也需要输出 \(q\)。
样例 #1
样例输入 #1
5 1 3 2 3 5 2 4 5 2 5 4 0 0样例输出 #1
1 3 2 3样例 #2
样例输入 #2
见附件中的 water/water2.in样例输出 #2
见附件中的 water/water2.ans样例 #3
样例输入 #3
见附件中的 water/water3.in样例输出 #3
见附件中的 water/water3.ans提示
【样例 #1 解释】
\(1\) 号结点是接收口，\(4, 5\) 号结点没有排出管道，因此是最终排水口。
\(1\) 吨污水流入 \(1\) 号结点后，均等地流向 \(2, 3, 5\) 号结点，三个结点各流入 \(\frac{1}{3}\) 吨污水。
\(2\) 号结点流入的 \(\frac{1}{3}\) 吨污水将均等地流向 \(4, 5\) 号结点，两结点各流入 \(\frac{1}{6}\) 吨污水。
\(3\) 号结点流入的 \(\frac{1}{3}\) 吨污水将均等地流向 \(4, 5\) 号结点，两结点各流入 \(\frac{1}{6}\) 吨污水。
最终，\(4\) 号结点排出 \(\frac{1}{6} + \frac{1}{6} = \frac{1}{3}\) 吨污水，\(5\) 号结点排出 \(\frac{1}{3} + \frac{1}{6} + \frac{1}{6} = \frac{2}{3}\) 吨污水。【数据范围】
测试点编号 \(n \le\) \(m \le\) \(1 \sim 3\) \(10\) \(1\) \(4 \sim 6\) \({10}^3\) \(1\) \(7 \sim 8\) \({10}^5\) \(1\) \(9 \sim 10\) \({10}^5\) \(10\) 对于全部的测试点，保证 \(1 \le n \le {10}^5\)，\(1 \le m \le 10\)，\(0 \le d_i \le 5\)。
数据保证，污水在从一个接收口流向一个最终排水口的过程中，不会经过超过 \(10\) 个中间排水结点（即接收口和最终排水口不算在内）。
拓扑模板题，注意 __int128。
/**
* @file 排水系统.cpp
* @tag: #GMOJ#拓扑
* @author: ZnPdCo
* @date: 2024-01-18 20:43:55
* @problem: https://gmoj.net/senior/#main/show/6922
**/
#include <cstdio>
#include <queue>
#define ll long long
#define uint128 unsigned __int128
#define N 100010
using namespace std;
uint128 gcd(uint128 a, uint128 b) {
if(b == 0) return a;
return gcd(b, a%b);
}
uint128 lcm(uint128 a, uint128 b) {
return a / gcd(a, b) * b;
}
struct frac {
uint128 mom, son;
void fun() {
uint128 g = gcd(mom, son);
mom /= g;
son /= g;
}
friend frac operator +(const frac &x, const frac &y) {
frac z;
z.mom = lcm(x.mom, y.mom);
z.son = z.mom / x.mom * x.son + z.mom / y.mom * y.son;
z.fun();
return z;
}
friend frac operator /(const frac &x, const ll &y) {
frac z;
z.mom = x.mom * y;
z.son = x.son;
z.fun();
return z;
}
} a[N];
ll n, m;
ll num[N];
ll head[N];
ll nxt[10*N];
ll to[10*N], cnt;
ll rd[N];
void addEdge(ll u, ll v) {
cnt++;
to[cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
rd[v]++;
}
void print(uint128 x) {
if(x >= 10) print(x / 10);
putchar(x % 10 + '0');
}
int main() {
freopen("water.in", "r", stdin);
freopen("water.out", "w", stdout);
scanf("%lld %lld", &n, &m);
for(ll i = 1; i <= n; i++) {
a[i].mom = 1;
scanf("%lld", &num[i]);
for(ll j = 1; j <= num[i]; j++) {
ll v;
scanf("%lld", &v);
addEdge(i, v);
}
}
queue<ll> que;
for(ll i = 1; i <= m; i++) {
que.push(i);
a[i].son = 1;
}
while(!que.empty()) {
ll u = que.front();
que.pop();
for(ll i = head[u]; i; i = nxt[i]) {
ll v = to[i];
a[v] = a[v] + a[u] / num[u];
rd[v]--;
if(!rd[v]) {
que.push(v);
}
}
}
for(ll i = 1; i <= n; i++) {
if(num[i] == 0) {
print(a[i].son);
putchar(' ');
print(a[i].mom);
putchar('\n');
}
}
}
T2 字符串匹配
[NOIP2020] 字符串匹配
题目描述
小 C 学习完了字符串匹配的相关内容，现在他正在做一道习题。
对于一个字符串 \(S\)，题目要求他找到 \(S\) 的所有具有下列形式的拆分方案数：
\(S = ABC\)，\(S = ABABC\)，\(S = ABAB \ldots ABC\)，其中 \(A\)，\(B\)，\(C\) 均是非空字符串，且 \(A\) 中出现奇数次的字符数量不超过 \(C\) 中出现奇数次的字符数量。
更具体地，我们可以定义 \(AB\) 表示两个字符串 \(A\)，\(B\) 相连接，例如 \(A = \texttt{aab}\)，\(B = \texttt{ab}\)，则 \(AB = \texttt{aabab}\)。
并递归地定义 \(A^1=A\)，\(A^n = A^{n - 1} A\)（\(n \ge 2\) 且为正整数）。例如 \(A = \texttt{abb}\)，则 \(A^3=\texttt{abbabbabb}\)。
则小 C 的习题是求 \(S = {(AB)}^iC\) 的方案数，其中 \(F(A) \le F(C)\)，\(F(S)\) 表示字符串 \(S\) 中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 \(A\)、\(B\)、\(C\) 中有至少一个字符串不同。
小 C 并不会做这道题，只好向你求助，请你帮帮他。
输入格式
本题有多组数据，输入文件第一行一个正整数 \(T\) 表示数据组数。
每组数据仅一行一个字符串 \(S\)，意义见题目描述。\(S\) 仅由英文小写字母构成。
输出格式
对于每组数据输出一行一个整数表示答案。
样例 #1
样例输入 #1
3 nnrnnr zzzaab mmlmmlo样例输出 #1
8 9 16样例 #2
样例输入 #2
5 kkkkkkkkkkkkkkkkkkkk lllllllllllllrrlllrr cccccccccccccxcxxxcc ccccccccccccccaababa ggggggggggggggbaabab样例输出 #2
156 138 138 147 194样例 #3
样例输入 #3
见附件中的 string/string3.in样例输出 #3
见附件中的 string/string3.ans样例 #4
样例输入 #4
见附件中的 string/string4.in样例输出 #4
见附件中的 string/string4.ans提示
【样例 #1 解释】
对于第一组数据，所有的方案为
- \(A=\texttt{n}\)，\(B=\texttt{nr}\)，\(C=\texttt{nnr}\)。
- \(A=\texttt{n}\)，\(B=\texttt{nrn}\)，\(C=\texttt{nr}\)。
- \(A=\texttt{n}\)，\(B=\texttt{nrnn}\)，\(C=\texttt{r}\)。
- \(A=\texttt{nn}\)，\(B=\texttt{r}\)，\(C=\texttt{nnr}\)。
- \(A=\texttt{nn}\)，\(B=\texttt{rn}\)，\(C=\texttt{nr}\)。
- \(A=\texttt{nn}\)，\(B=\texttt{rnn}\)，\(C=\texttt{r}\)。
- \(A=\texttt{nnr}\)，\(B=\texttt{n}\)，\(C=\texttt{nr}\)。
- \(A=\texttt{nnr}\)，\(B=\texttt{nn}\)，\(C=\texttt{r}\)。
【数据范围】
测试点编号 \(\lvert S \rvert \le\) 特殊性质 \(1 \sim 4\) \(10\) 无 \(5 \sim 8\) \(100\) 无 \(9 \sim 12\) \(1000\) 无 \(13 \sim 14\) \(2^{15}\) \(S\) 中只包含一种字符 \(15 \sim 17\) \(2^{16}\) \(S\) 中只包含两种字符 \(18 \sim 21\) \(2^{17}\) 无 \(22 \sim 25\) \(2^{20}\) 无 对于所有测试点，保证 \(1 \le T \le 5\)，\(1 \le |S| \le 2^{20}\)。
这是我在除模板题外第一次使用 exkmp。
首先枚举循环节长度 \(i\)，那么知道循环节次数 \(k\in[1,\lfloor\frac{i+z[i+1]}{i}\rfloor]\)。
设 \(f(i,j)\) 为区间内奇数字符的个数。对于 \(x\) 为奇数，\(x-1\) 是偶数，所以 \(f(i+1,ix)=0\)，发现 \(f(ix+1,n)=f(i,n)\)，可以实时处理；对于 \(x\) 为偶数，\(x\) 是偶数，所以 \(f(1,ix)=0\)，发现 \(f(ix+1,n)=f(1,n)\)，可以预处理。
那么对于统计 \(f(1,ix)\le f(ix+1,n)=\begin{cases}f(i+1,n) & x\in\mathbb{O}\\f(1,n) & x\in\mathbb{E}\end{cases}\)，可以使用树状数组实时维护。
/**
* @file 字符串匹配.cpp
* @tag: #GMOJ#exkmp#字符串#树状数组
* @author: ZnPdCo
* @date: 2024-01-18 20:43:55
* @problem: https://gmoj.net/senior/#main/show/6923
**/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
#define N ((1<<20)+10)
ll t, n;
char s[N];
ll z[N];
ll bef[30], aft[30];
ll suf, pre, all;
ll ans;
void Z() {
z[1] = n;
while(z[2] + 2 <= n && s[z[2]+1] == s[z[2]+2]) z[2]++;
ll p0 = 2, p1 = 2 + z[2] - 1;
for(ll k = 3; k <= n; k++) {
if(k + z[k-p0+1] - 1 < p1) z[k] = z[k-p0+1];
else {
z[k] = max(0ll, p1-k);
while(z[k] + k <= n && s[z[k]+1] == s[z[k]+k]) z[k]++;
p0 = k;
p1 = k + z[k] - 1;
}
}
}
ll a[N];
inline ll lowbit(ll x) {
return x & (-x);
}
inline void update(ll x, ll y) {
while(x <= 30) {
a[x] += y;
x += lowbit(x);
}
}
inline ll query(ll x) {
ll res = 0;
while(x) {
res += a[x];
x -= lowbit(x);
}
return res;
}
int main() {
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
scanf("%lld", &t);
while(t--) {
memset(z, 0, sizeof z);
memset(a, 0, sizeof a);
memset(s, 0, sizeof s);
memset(bef, 0, sizeof bef);
memset(aft, 0, sizeof aft);
all = suf = pre = ans = 0;
scanf("%s", s+1);
n = strlen(s+1);
Z();
for(ll i = 1; i <= n; i++) {
if(i + z[i] - 1 == n) z[i]--; // 留出c的位置
}
for(ll i = 1; i <= n; i++) {
if(aft[s[i]-'a'] % 2 == 1) all--;
else all++;
aft[s[i]-'a']++;
}
suf = all;
for(ll i = 1; i <= n; i++) {
if(aft[s[i]-'a'] % 2 == 1) suf--;
else suf++;
aft[s[i]-'a']--;
if(bef[s[i]-'a'] % 2 == 1) pre--;
else pre++;
bef[s[i]-'a']++;
if(i != 1 && i != n) {
ll t = z[i+1] / i + 1;
ll tj = t - t / 2;
ll to = t / 2;
ll t1 = query(suf + 1);
ll t2 = query(all + 1);
ans += tj * t1 + to * t2;
}
update(pre+1, 1);
}
printf("%lld\n", ans);
}
}
T3 移球游戏
[NOIP2020] 移球游戏
题目描述
小 C 正在玩一个移球游戏，他面前有 \(n + 1\) 根柱子，柱子从 \(1 \sim n + 1\) 编号，其中 \(1\) 号柱子、\(2\) 号柱子、……、\(n\) 号柱子上各有 \(m\) 个球，它们自底向上放置在柱子上，\(n + 1\) 号柱子上初始时没有球。这 \(n \times m\) 个球共有 \(n\) 种颜色，每种颜色的球各 \(m\) 个。
初始时一根柱子上的球可能是五颜六色的，而小 C 的任务是将所有同种颜色的球移到同一根柱子上，这是唯一的目标，而每种颜色的球最后放置在哪根柱子则没有限制。
小 C 可以通过若干次操作完成这个目标，一次操作能将一个球从一根柱子移到另一根柱子上。更具体地，将 \(x\) 号柱子上的球移动到 \(y\) 号柱子上的要求为：
- \(x\) 号柱子上至少有一个球；
- \(y\) 号柱子上至多有 \(m - 1\) 个球；
- 只能将 \(x\) 号柱子最上方的球移到 \(y\) 号柱子的最上方。
小 C 的目标并不难完成，因此他决定给自己加加难度：在完成目标的基础上，使用的操作次数不能超过 \(820000\)。换句话说，小 C 需要使用至多 \(820000\) 次操作完成目标。
小 C 被难住了，但他相信难不倒你，请你给出一个操作方案完成小 C 的目标。合法的方案可能有多种，你只需要给出任意一种，题目保证一定存在一个合法方案。
输入格式
第一行两个用空格分隔的整数 \(n, m\)。分别表示球的颜色数、每种颜色球的个数。
接下来 \(n\) 行每行 \(m\) 个用单个空格分隔的整数，第 \(i\) 行的整数按自底向上的顺序依次给出了 \(i\) 号柱子上的球的颜色。输出格式
本题采用自定义校验器（special judge）评测。
你的输出的第一行应该仅包含单个整数 \(k\)，表示你的方案的操作次数。你应保证 \(0 \le k \le 820000\)。
接下来 \(k\) 行每行你应输出两个用单个空格分隔的正整数 \(x, y\)，表示这次操作将 \(x\) 号柱子最上方的球移动到 \(y\) 号柱子最上方。你应保证 \(1 \le x, y \le n + 1\) 且 \(x \ne y\)。样例 #1
样例输入 #1
2 3 1 1 2 2 1 2样例输出 #1
6 1 3 2 3 2 3 3 1 3 2 3 2样例 #2
样例输入 #2
见附件中的 ball/ball2.in样例输出 #2
见附件中的 ball/ball2.ans样例 #3
样例输入 #3
见附件中的 ball/ball3.in样例输出 #3
见附件中的 ball/ball3.ans提示
【样例 #1 解释】
柱子中的内容为：按自底向上的顺序依次给出柱子上每个球的颜色。
操作 \(1\) 号柱子 \(2\) 号柱子 \(3\) 号柱子 初始 \(1\ 1\ 2\) \(2\ 1\ 2\) \(1\ 3\) \(1\ 1\) \(2\ 1\ 2\) \(2\) \(2\ 3\) \(1\ 1\) \(2\ 1\) \(2\ 2\) \(2\ 3\) \(1\ 1\) \(2\) \(2\ 2\ 1\) \(3\ 1\) \(1\ 1\ 1\) \(2\) \(2\ 2\) \(3\ 2\) \(1\ 1\ 1\) \(2\ 2\) \(2\) \(3\ 2\) \(1\ 1\ 1\) \(2\ 2\ 2\) 【数据范围】
测试点编号 \(n \le\) \(m \le\) \(1 \sim 2\) \(2\) \(20\) \(3 \sim 5\) \(10\) \(20\) \(6 \sim 8\) \(50\) \(85\) \(9 \sim 14\) \(50\) \(300\) \(15 \sim 20\) \(50\) \(400\) 对于所有测试点，保证 \(2 \le n \le 50\)，\(2 \le m \le 400\)。
【校验器】
为了方便选手测试，在附件中的
ball目录下我们下发了checker.cpp文件，选手可以编译该程序，并使用它校验自己的输出文件。但请注意它与最终评测时所使用的校验器并不完全一致。你也不需要关心其代码的具体内容。编译命令为：
g++ checker.cpp −o checker -std=c++11。
checker的使用方式为：checker <inputfile> <outputfile>，参数依次表示输入文件与你的输出文件。若你输出的数字大小范围不合法，则校验器会给出相应提示。若你的输出数字大小范围正确，但方案错误，则校验器会给出简要的错误信息：
A x，表示进行到第 \(x\) 个操作时不合法。B x，表示操作执行完毕后第 \(x\) 个柱子上的球不合法。若你的方案正确，校验器会给出
OK。
构造题。
首先可以非常容易想到 \(n=2\) 的解法，把 \(1\) 看作黑球，\(2\) 看作白球，\(x\) 作为第一列，\(y\) 作为第二列，\(n+1\) 作为多出的一列：
-
初始状态。
121121 122212 -
将 \(x\) 中的黑球个数 \(cx\) 统计下来，把 \(y\) 中 \(cx\) 个球移动到 \(n+1\)。
121121 12 2122 -
将 \(x\) 中的黑球放到 \(y\)，白球放到 \(n+1\)。
121111 212222 -
把 \(n+1\) 中的 \(m-cx\) 个原属于 \(x\) 的白球移动回 \(x\)。
22 121111 2122 -
把 \(y\) 中的 \(cx\) 个原属于 \(x\) 的黑球移动回 \(x\)。（\(x\) 现在前面是白球，后面是黑球）
221111 12 2122 -
把 \(n+1\) 中的 \(cx\) 个原属于 \(y\) 的球移动回 \(y\)。
221111 122212 -
把 \(x\) 中的 \(cx\) 个黑球放到 \(n+1\)（\(x\) 现在只有白球）
22 122212 1111 -
把 \(y\) 中的黑球放到 \(n+1\)，白球放到 \(x\)。
222222 111111 -
把 \(n+1\) 中的黑球放回 \(y\)。
222222 111111
上面其实就是将第二列作为黑球的储存地，第三列作为白球的储存地。
然后我又想，可以枚举颜色，将每一列作为一种颜色的储存地，如当 \(n=5\)，枚举到第一列，那么第二列为颜色 \(1\) 的储存地，第三列为颜色 \(2\) 的储存地，第四列为颜色 \(3\) 的储存地，第五列为颜色 \(4\) 的储存地，第六列为颜色 \(5\) 的储存地。
这就是我在训练时的想法，操作次数是 \(7n^2m\) 的。
但是我赛时并没有打出来，一方面是都想到这里了，我想追求正解，另一方面是没给数据范围，不敢打。（哈哈）
其实和正解很接近。
不妨利用分治思想，分治一个 \(mid\)，将小于等于 \(mid\) 的看作黑球，大于 \(mid\) 的看作白球。然后把颜色在 \([l,r]\) 内的两两相邻的做 \(n=2\) 的操作。
但是我们会发现，黑球的个数 \(w\) 可能会大于或小于 \(m\)，这会导致在进行如上相同操作时，\(y\) 列不够多放到 \(n+1\) 列。
所以当 \(w<m\) 时，我们随机选择一些白球染成黑球；当所以当 \(w>m\) 时，我们随机选择一些黑球染成白球。
因为我们会在下一次分治时进一步分类，所以不用担忧黑球和白球会混在一起。
最坏情况是 \(7nm\log n\le800000\)，可以过。
/**
* @file 移球游戏.cpp
* @tag: #GMOJ#构造#分治
* @author: ZnPdCo
* @date: 2024-01-18 20:43:55
* @problem: https://gmoj.net/senior/#main/show/6924
**/
#include <cstdio>
#include <vector>
using namespace std;
#define ll long long
#define N 60
#define M 410
#define debug false
ll n, m;
ll top[N];
ll num[N][M]; // 某一行某种颜色的个数
ll a[N][M]; // 给定的颜色分布
bool b[N][M]; // 黑白球规定
struct node {
ll x, y;
} ans[820010];
ll cnt;
void show() {
for(ll i = 1; i <= n+1; i++) {
for(ll j = 1; j <= top[i]; j++) {
printf("%lld ", a[i][j]);
}
printf("\n");
}
printf("\n");
}
void mov(ll x, ll y) {
ans[++cnt].x = x;
ans[cnt].y = y;
a[y][++top[y]] = a[x][top[x]--];
if(debug) show();
}
void fun(ll x, ll y, ll mid) {
ll numx = 0, numy = 0;
for(ll i = 1; i <= m; i++) {
if(a[x][i] <= mid) numx++, b[x][i] = 1;
else b[x][i] = 0;
if(a[y][i] <= mid) numy++, b[y][i] = 1;
else b[y][i] = 0;
}
// 1.如果太多黑球则取反
if(numx + numy > m) {
numx = m - numx, numy = m - numy;
for(ll i = 1; i <= m; i++) b[x][i] ^= 1, b[y][i] ^= 1;
}
// 2.如果太少则添加虚拟黑球（把黑球放到y）
for(ll i = 1; i <= m; i++) {
if(!b[x][i] && numx + numy < m) {
numx++;
b[x][i] = 1;
}
}
// 3.把y中的numx个取到n+1中
if(debug) printf("把y中的numx个取到n+1中\n");
for(ll i = 1; i <= numx; i++) {
mov(y, n+1);
}
// 4.把x中的黑球放到y，白球放到n+1
if(debug) printf("把x中的黑球放到y，白球放到n+1\n");
for(ll i = 1; i <= m; i++) {
if(b[x][top[x]]) {
mov(x, y);
} else {
mov(x, n+1);
}
}
// 5.把n+1中的m-numx个白球放回到x
if(debug) printf("把n+1中的m-numx个白球放回到x\n");
for(ll i = 1; i <= m-numx; i++) mov(n+1, x);
// 6.把y中的numx个黑球放回到x（x现在前面是白球，后面是黑球）
if(debug) printf("把y中的numx个黑球放回到x（x现在前面是白球，后面是黑球）\n");
for(ll i = 1; i <= numx; i++) mov(y, x);
// 7.把n+1中的numx放回到y（y现在不变）
if(debug) printf("把n+1中的numx放回到y（y现在不变）\n");
for(ll i = 1; i <= numx; i++) mov(n+1, y);
// 8.把x中的numx个黑球放到n+1（x现在只有白球）
if(debug) printf("把x中的numx个黑球放到n+1（x现在只有白球）\n");
for(ll i = 1; i <= numx; i++) mov(x, n+1);
// 9.把y中的黑球放到n+1，白球放到x
if(debug) printf("把y中的黑球放到n+1，白球放到x\n");
for(ll i = 1; i <= m; i++) {
if(b[y][top[y]]) {
mov(y, n+1);
} else {
mov(y, x);
}
}
// 10.把n+1中的黑球放回y
if(debug) printf("把n+1中的黑球放回y\n");
for(ll i = 1; i <= m; i++) {
mov(n+1, y);
}
}
void solve(ll l, ll r) {
if(debug) printf("===%lld %lld===\n", l, r);
if(l == r) return;
ll mid = (l + r) >> 1;
vector<ll> now;
for(ll i = 1; i <= n; i++) {
if(l <= a[i][1] && a[i][1] <= r) {
now.push_back(i);
}
}
for(ll i = 0; i < now.size() - 1; i++) {
fun(now[i], now[i+1], mid);
}
solve(l, mid);
solve(mid+1, r);
}
int main() {
freopen("ball.in", "r", stdin);
freopen("ball.out", "w", stdout);
scanf("%lld %lld", &n, &m);
for(ll i = 1; i <= n; i++) {
for(ll j = 1; j <= m; j++) {
scanf("%lld", &a[i][j]);
num[i][a[i][j]]++;
}
top[i] = m;
}
solve(1, n);
printf("%lld\n", cnt);
for(ll i = 1; i <= cnt; i++) {
printf("%lld %lld\n", ans[i].x, ans[i].y);
}
// show();
}
T4 微信步数
[NOIP2020] 微信步数
题目描述
小 C 喜欢跑步，并且非常喜欢在微信步数排行榜上刷榜，为此他制定了一个刷微信步数的计划。
他来到了一处空旷的场地，处于该场地中的人可以用 \(k\) 维整数坐标 \((a_1, a_2, \ldots , a_k)\) 来表示其位置。场地有大小限制，第 \(i\) 维的大小为 \(w_i\)，因此处于场地中的人其坐标应满足 \(1 \le a_i \le w_i\)（\(1 \le i \le k\)）。
小 C 打算在接下来的 \(P = w_1 \times w_2 \times \cdots \times w_k\) 天中，每天从场地中一个新的位置出发，开始他的刷步数计划（换句话说，他将会从场地中每个位置都出发一次进行计划）。
他的计划非常简单，每天按照事先规定好的路线行进，每天的路线由 \(n\) 步移动构成，每一步可以用 \(c_i\) 与 \(d_i\) 表示：若他当前位于 \((a_1, a_2, \ldots , a_{c_i}, \ldots, a_k)\)，则这一步他将会走到 \((a_1, a_2, \ldots , a_{c_i} + d_i, \ldots , a_k)\)，其中 \(1 \le c_i \le k\)，\(d_i \in \{-1, 1\}\)。小 C 将会不断重复这个路线，直到他走出了场地的范围才结束一天的计划。（即走完第 \(n\) 步后，若小 C 还在场内，他将回到第 \(1\) 步从头再走一遍）。
小 C 对自己的速度非常有自信，所以他并不在意具体耗费的时间，他只想知道 \(P\) 天之后，他一共刷出了多少步微信步数。请你帮他算一算。
输入格式
第一行两个用单个空格分隔的整数 \(n, k\)。分别表示路线步数与场地维数。
接下来一行 \(k\) 个用单个空格分隔的整数 \(w_i\)，表示场地大小。
接下来 \(n\) 行每行两个用单个空格分隔的整数 \(c_i, d_i\)，依次表示每一步的方向，具体意义见题目描述。输出格式
仅一行一个整数表示答案。答案可能很大，你只需要输出其对 \({10}^9 + 7\) 取模后的值。
若小 C 的计划会使得他在某一天在场地中永远走不出来，则输出一行一个整数 \(-1\)。样例 #1
样例输入 #1
3 2 3 3 1 1 2 -1 1 1样例输出 #1
21样例 #2
样例输入 #2
5 4 6 8 6 5 3 1 2 1 1 1 2 1 2 -1样例输出 #2
10265样例 #3
样例输入 #3
见附件中的 walk/walk3.in样例输出 #3
见附件中的 walk/walk3.ans样例 #4
样例输入 #4
见附件中的 walk/walk4.in样例输出 #4
见附件中的 walk/walk4.ans提示
【样例 #1 解释】
从 \((1, 1)\) 出发将走 \(2\) 步，从 \((1, 2)\) 出发将走 \(4\) 步，从 \((1, 3)\) 出发将走 \(4\) 步。
从 \((2, 1)\) 出发将走 \(2\) 步，从 \((2, 2)\) 出发将走 \(3\) 步，从 \((2, 3)\) 出发将走 \(3\) 步。
从 \((3, 1)\) 出发将走 \(1\) 步，从 \((3, 2)\) 出发将走 \(1\) 步，从 \((3, 3)\) 出发将走 \(1\) 步。
共计 \(21\) 步。【数据范围】
测试点编号 \(n \le\) \(k \le\) \(w_i \le\) \(1 \sim 3\) \(5\) \(5\) \(3\) \(4 \sim 6\) \(100\) \(3\) \(10\) \(7 \sim 8\) \({10}^5\) \(1\) \({10}^5\) \(9 \sim 12\) \({10}^5\) \(2\) \({10}^6\) \(13 \sim 16\) \(5 \times {10}^5\) \(10\) \({10}^6\) \(17 \sim 20\) \(5 \times {10}^5\) \(3\) \({10}^9\) 对于所有测试点，保证 \(1 \le n \le 5 \times {10}^5\)，\(1 \le k \le 10\)，\(1 \le w_i \le {10}^9\)，\(d_i \in \{-1, 1\}\)。
先统计第一轮 \(n\) 个操作。考虑统计每一维的最右最左端 \(r_i,l_i\)，那么这一维度的死亡人数为 \(r_i-l_i\)，存活人数为 \(w_i-(r_i-l_i)\)。
对于 \(-1\) 的情况很好统计，一轮后仍在原地且 \(r_i-l_i< w_i\)。
然后发现后面的轮肯定是在慢慢往一个方向移动，所以从第二轮开始只有移动方向的位置才会死人，而且每次死的人数一致。
实际上就是求 \(\sum_{x=1}^{t}\sum_{i=1}^n\prod_{j=1}^k(a_j-(x-1)b_j-f_{i,j})\)。其中 \(t\) 是可以执行的整轮数量，有 \(t=\min\lfloor\frac{a_i}{b_i}\rfloor\)，\(a\) 是这个维度经过第一轮活下来的人数，\(b\) 是第二轮开始每轮死的人数，\(f_i\) 是最后不到一轮的剩余人数（我们分开计算）。
然后展开求值对我不太友好，所以我后面看到题解里可以用插值。
这个式子明显是两个 \(k\) 项多项式相乘得到一个 \(k+1\) 项的多项式，所以可以直接暴力求 \(k+2\) 项然后拉格朗日插值。
然后暴力处理最后一轮就过了。
/**
* @file 微信步数.cpp
* @tag: #GMOJ#推式子#插值
* @author: ZnPdCo
* @date: 2024-01-18 20:43:55
* @problem: https://gmoj.net/senior/#main/show/6925
**/
#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
#define K 20
#define N 500010
#define P 1000000007
ll n, k, ans = 1;
ll w[K];
ll c[N], d[N];
ll l[K], r[K], p[K], a[K];
ll f[N][K], g[N];
ll t;
inline ll fun(ll x) {
return (x % P + P) % P;
}
ll qpow(ll x, ll y) {
if(y == 0) return 1;
if(y % 2 == 1) return x * qpow(x, y - 1) % P;
ll tmp = qpow(x, y/2);
return tmp * tmp % P;
}
ll calc(ll x) {
if(x <= k+1) return g[x];
ll res = 0;
for(ll i = 0; i <= k+1; i++) {
ll s = g[i];
for(ll j = 0; j <= k+1; j++) {
if(i == j) continue;
(s *= fun(x - j) * qpow(fun(i - j), P - 2) % P) %= P;
}
(res += s) %= P;
}
return res;
}
int main() {
// freopen("C:\\Users\\Administrator\\Downloads\\walk7.in", "r", stdin);
// freopen("walk.in", "r", stdin);
// freopen("walk.out", "w", stdout);
scanf("%lld %lld", &n, &k);
for(ll i = 1; i <= k; i++) {
scanf("%lld", &w[i]);
}
for(ll i = 1; i <= n; i++) {
scanf("%lld %lld", &c[i], &d[i]);
}
for(ll i = 1; i <= k; i++) {
(ans *= w[i]) %= P;
}
// 第一轮
for(ll i = 1; i <= n; i++) {
p[c[i]] += d[i];
l[c[i]] = min(l[c[i]], p[c[i]]);
r[c[i]] = max(r[c[i]], p[c[i]]);
if(r[c[i]] - l[c[i]] > w[c[i]]) {
return printf("%lld", ans), 0;
}
ll s = 1;
for(ll j = 1; j <= k; j++) {
(s *= (w[j] - (r[j] - l[j]))) %= P;
}
(ans += s) %= P;
}
for(ll i = 1; i <= k; i++) {
a[i] = p[i];
}
// 无限
bool forever = true;
for(ll i = 1; i <= k; i++) {
if(p[i] != 0) {
forever = false;
break;
}
if(r[i] - l[i] >= w[i]) {
forever = false;
break;
}
}
if(forever) {
return printf("-1"), 0;
}
// 第二轮
for(ll i = 1; i <= n; i++) {
p[c[i]] += d[i];
for(ll j = 1; j <= k; j++) f[i][j] = f[i-1][j];
if(a[c[i]] > 0) { // 每次向右移动
f[i][c[i]] = max(f[i][c[i]], p[c[i]] - r[c[i]]);
} else { // 每次向左移动
f[i][c[i]] = max(f[i][c[i]], l[c[i]] - p[c[i]]);
}
}
for(ll i = 1; i <= k; i++) {
w[i] -= (r[i] - l[i]);
a[i] = abs(a[i]);
}
t = 1e15;
for(ll i = 1; i <= k; i++) {
if(a[i]) t = min(t, w[i] / a[i]);
}
for(ll x = 1; x <= k+1; x++) {
ll sum = 0;
for(ll i = 1; i <= n; i++) {
ll s = 1;
for(ll j = 1; j <= k; j++) {
s = ((s * (w[j] - (x-1) * a[j] % P - f[i][j])) % P + P) % P;
}
(sum += s) %= P;
}
g[x] = (g[x - 1] + sum) % P;
}
(ans += calc(t)) %= P;
for(ll i = 1; i <= k; i++) {
w[i] -= t * a[i];
}
for(ll i = 1; i <= n; i++) {
if(f[i][c[i]] > w[c[i]]) break;
ll s = 1;
for(ll j = 1; j <= k; j++) {
(s *= (w[j] - f[i][j])) %= P;
}
(ans += s) %= P;
}
printf("%lld", ans);
return 0;
}