NOIP2020 题解
T1. 排水系统
Solution
将每个 “ 排水节点 “ 看成是一个 “ 点 “,将每个 “ 单向排水管道 “ 看成是一条 “ 单向边 “。
不难发现,得到的图是一张 DAG。
直接模拟题意即可。依次松弛每个节点的蓄水量,直至到达最终排水口。需要注意的是,在松弛任意一个节点 v 的蓄水量时,需要保证:对于图中的每一条有向边 (u, v),u 的蓄水量都被松弛过了。
发现可以通过拓扑序来转移。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define u128 __int128
using namespace std;
inline void print(u128 x) {
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
u128 gcd(u128 a, u128 b) {
if (!b) return a;
return gcd(b, a % b);
}
const int N = 400100;
struct Node {
u128 x, y;
} a[N];
Node operator + (Node a, Node b) {
Node c;
c.y = a.y * b.y;
c.x = a.x * b.y + b.x * a.y;
u128 S = gcd(c.x, c.y);
if (!S) {
c.x = 0;
c.y = 1;
} else {
c.x /= S;
c.y /= S;
}
return c;
}
Node operator / (Node a, int num) {
Node b;
b.x = a.x;
b.y = 1ll * a.y * num;
u128 S = gcd(b.x, b.y);
if (!S) {
b.x = 0;
b.y = 1;
} else {
b.x /= S;
b.y /= S;
}
return b;
}
int n, m;
vector<int> to[N];
int deg[N];
void topsort() {
queue<int> q;
for (int i = 1; i <= n; i ++)
if (deg[i] == 0) q.push(i);
while (q.size()) {
int u = q.front(); q.pop();
if (to[u].size() == 0) continue;
Node give = a[u] / to[u].size();
for (int i = 0; i < (int)to[u].size(); i ++) {
int v = to[u][i];
a[v] = a[v] + give;
if (-- deg[v] == 0) q.push(v);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1, S; i <= n; i ++) {
scanf("%d", &S);
while (S --) {
int x;
scanf("%d", &x);
to[i].push_back(x);
}
}
for (int i = 1; i <= m; i ++)
a[i].x = 1, a[i].y = 1;
for (int i = m + 1; i <= n; i ++)
a[i].x = 0, a[i].y = 1;
for (int i = 1; i <= n; i ++)
for (int j = 0; j < (int)to[i].size(); j ++) {
int v = to[i][j];
deg[v] ++;
}
topsort();
for (int i = 1; i <= n; i ++)
if (to[i].size() == 0) {
print(a[i].x);
printf(" ");
print(a[i].y);
puts("");
}
return 0;
}
// I hope changle_cyx can pray for me.T2. 字符串匹配
Solution
算法一
部分分:n \leq 2^{17}。
一个较为简单的做法,基本不用怎么思考。
注意到答案是要求将字符串划分成 S = (AB)^iC 的形式。
记 F(S) 的表示字符串 S 中出现奇数次的字符的数量。需要先预处理出:
- 每一个前缀 S_{1 .. i} 出现奇数次的字符的数量,即 F(S_{1..i})。
- 每一个后缀 S_{i .. n} 出现奇数次的字符的数量,即 F(S_{i .. n})。
考虑枚举 T = (AB),那相当于是枚举一个前缀。此基础上,再从小到大枚举一个 i,使用 hash 判断子串是否完全相等。
此时整个字符串的划分结构就已经是确定的了。F(C) 已经预处理好了,那这种情况对答案的贡献,相当于要在 T 里数出有多少个真前缀 A 满足 F(A) \leq F(C),那直接用树状数组动态维护一下即可。
时间复杂度 \mathcal{O}(n \log n + n \log |\sum|),其中 \sum 表示字符集。期望得分 84 \sim 100。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2000000;
const unsigned long long P = 13331;
int n;
char S[N];
// suf & pre
bool exist[30];
int num;
int suf[N];
int pre[N];
int c[N][30];
// hash
unsigned long long power[N];
unsigned long long hash[N];
unsigned long long H(int l, int r) {
return hash[r] - hash[l - 1] * power[r - l + 1];
}
void work() {
scanf("%s", S + 1);
n = strlen(S + 1);
// suf
for (int i = 0; i < 26; i ++)
exist[i] = 0;
num = 0;
for (int i = n; i >= 1; i --) {
int ch = S[i] - 'a';
exist[ch] ^= 1;
if (exist[ch]) num ++;
else num --;
suf[i] = num;
}
// pre
for (int i = 0; i < 26; i ++)
exist[i] = 0;
num = 0;
for (int i = 1; i <= n; i ++) {
int ch = S[i] - 'a';
exist[ch] ^= 1;
if (exist[ch]) num ++;
else num --;
pre[i] = num;
}
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= 26; j ++)
c[i][j] = c[i - 1][j];
for (int j = pre[i]; j <= 26; j ++)
c[i][j] ++;
}
// hash
for (int i = 1; i <= n; i ++)
hash[i] = hash[i - 1] * P + (S[i] - 'a');
// work
long long ans = 0;
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n / i; j ++) {
int l = (j - 1) * i + 1, r = j * i;
if (H(1, i) != H(l, r)) break;
if (r + 1 > n) break;
ans += c[i - 1][suf[r + 1]];
}
}
printf("%lld\n", ans);
}
int main() {
power[0] = 1;
for (int i = 1; i <= 1500000; i ++) power[i] = power[i - 1] * P;
int T; scanf("%d", &T);
while (T --) work();
return 0;
}
// I hope changle_cyx can pray for me.算法二
「算法一」没有怎么用到题目中的一些性质,还是考虑枚举 T = (AB) = S_{1 .. x}。
对于当前枚举到的一个 x。考虑计算出一个最大的 i,使得 S 可以被划分成 (AB)^iC 的形式,记这个量为 k。
引理:若一个长度为 n 的字符串 S 的前 n - m 位和后 n - m 是相等的且 m \mid n,则 S 有一个长度为 m 的整除循环节。
根据该引理,考虑求出字符串 S 的 Z 函数,其中 Z_i 表示:后缀 S_{i .. n} 与 S 的最长公共前缀(LCP)的长度。
注意到若 S 可以被划分成 (AB)^iC 的形式,则必满足 x(i - 1) \leq Z_{x + 1} 且 xi < n。解得
则
接下来考虑 F\left((AB)^i\right) 的重复性,注意到:
-
当 i 为奇数时 F\left( (AB)^i \right) 均等。当 i 为奇数时,对于每个 (AB)^i 划分出来的 C,都有 F(C) = F(S_{x + 1 .. n})。
-
当 i 为偶数时 F\left( (AB)^i \right) = 0。当 i 为偶数时,对于每个 (AB)^i 划分出来的 C,都有 F(C) = F(S)。
那么我们可以知道,划分出来的 F(C) 的也就只有两种情况,要么是 F(S_{x + 1 .. n}) 要么是 F(S)。其中 \left\lceil \frac{k}{2} \right\rceil 个 i 为奇数,\left\lfloor \frac{k}{2} \right\rfloor 个 i 为偶数。
F(S_{x + 1 .. n}) 在枚举 x 的时候顺便处理一下即可,F(S) 直接处理即可。
那么现在就是要分别数出 T 中有多少个真前缀 A 满足 F(A) \leq F(S_{x + 1 .. n}),F(A) \leq F(S)。
注意到 F(S) 是不变的,那么在枚举的时候直接判断一下即可。至于 F(S_{x + 1 .. n}),当 x 加 1 的时候也只会导致 F(S_{x + 1 .. n}) 变化 1,稍微判断一下补补贡献即可。
时间复杂度 \mathcal{O}(n)。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = (1 << 20) + 1000;
int T;
int n;
char s[N];
int Z[N];
void Z_algorithm() {
for (int i = 1; i <= n; i ++) Z[i] = 0;
for (int i = 2, l = 0, r = 0; i <= n; i ++) {
if (i <= r) Z[i] = min(Z[i - l + 1], r - i + 1);
while (i + Z[i] <= n && s[1 + Z[i]] == s[i + Z[i]])
Z[i] ++;
if (i + Z[i] - 1 > r)
l = i, r = i + Z[i] - 1;
}
}
int pre, suf, Fs;
int cnt[26];
bool flag1[26], flag2[26];
int cur1, cur2;
long long ans;
void work() {
scanf("%s", s + 1);
n = strlen(s + 1);
Z_algorithm();
memset(flag1, 0, sizeof(flag1));
memset(flag2, 0, sizeof(flag2));
for (int i = 1; i <= n; i ++) {
int ch = s[i] - 'a';
flag2[ch] ^= 1;
}
Fs = 0;
for (int i = 0; i < 26; i ++)
if (flag2[i]) Fs ++;
pre = 0, suf = Fs;
ans = 0, cur1 = cur2 = 0;
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i < n; i ++) {
int ch = s[i] - 'a';
flag1[ch] ^= 1, flag2[ch] ^= 1;
if (flag1[ch]) pre ++;
else pre --;
if (flag2[ch]) suf ++, cur1 += cnt[suf];
else cur1 -= cnt[suf], suf --;
int k = min((Z[i + 1] / i) + 1, (n - 1) / i);
int odd = (k + 1) / 2, even = k / 2;
ans += 1ll * odd * cur1;
ans += 1ll * even * cur2;
cnt[pre] ++;
if (pre <= suf) cur1 ++;
if (pre <= Fs) cur2 ++;
}
printf("%lld\n", ans);
}
int main() {
scanf("%d", &T);
while (T --) work();
return 0;
}
// I hope changle_cyx can pray for me.T3. 移球游戏
Solution
算法一
部分分:n = 2。
现在有三个柱子 x, y, z。 其中 x 号柱与 y 号柱是满的,z 号柱是空的。这 2m 个球中有 m 个关键球,现在要将所有关键球移动到同一根柱子上。
设 x 柱上有 c 个关键球,操作如下:
-
(1):将 y 号柱上的 c 个球移动到 z 号柱上。
-
(2):依次考虑 x 号柱里的每一个球。
若该球为关键球,则将其移动到 y 号柱。
若该球不为关键球,则将其移动到 z 号柱。 -
(3):将 z 号柱上方的 m - c 个球移回 x 号柱。
-
(4):将 y 号柱上方的 c 个球移动到 x 号柱。
-
(5):将 z 号柱里的 c 个球移动到 y 号柱。
-
(6):将 x 号柱上方的 c 个球移动到 z 号柱。
-
(7):依次考虑 y 号柱里的每一个球。
若该球为关键球,则将其移动到 z 号柱。
若该球不为关键球,则将其移动到 x 号柱。
此时 n = 2 就做完了,复杂度是 \mathcal{O(m)} 的。
「算法一」是本题中最基本的操作。
算法二
部分分:n \leq 50,m \leq 300。
可以一个颜色一个颜色来考虑。假设考虑到第 n 个颜色,现在要将所有颜色为 n 的球移动到同一根柱子上:
-
枚举 i = 1 \to (n - 1),将 i 号柱里所有颜色为 n 的球都移动到 i 号柱子的最顶端。记 i 号柱共有 c_i 个颜色为 n 的球,操作如下:
-
(1):将 n 号柱移出 c_i 个空位。
-
(2):依次考虑 i 号柱里的每一个球。
若该球的颜色为 n,则将其移动到 n 号柱。
若该球的颜色不为 n,则将其移动到 n + 1 号柱。 -
(3):将 n + 1 号柱上方的 m - c_i 个球移回 i 号柱。
-
(4):将 n 号柱上方的 c_i 个球移回 i 号柱。
-
(5):将 n + 1 号柱上方的 c_i 个球移回 n 号柱。
-
-
枚举 i = 1 \to (n - 1),将 i 号柱子最顶端所有颜色为 n 的球都移动到 n + 1 号柱上。
-
依次考虑 n 号柱子里的每一个球。
若该球的颜色为 n,则将其移动到 n + 1 号柱。
若该球的颜色不为 n,则将其补到 1 至 n - 1 号柱里的一个空位上。
这样的话就得到了一个规模为 n - 1 的子问题,直接递归即可。
复杂度是 \mathcal{O}(n^2m) 的。可以计算得出该算法最坏情况下的严格操作数为 m(n - 1)(n + 4)。
发现刚好可以过掉 70 分。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read() {
int x = 0, f = 1; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
return x * f;
}
const int N = 60, M = 450;
int n, m;
int top[N], a[N][M];
int cnt[N][M];
int t;
pair<int, int> ans[820001];
void move(int x, int y) {
ans[++ t] = make_pair(x, y);
int u = a[x][top[x]];
cnt[x][u] --;
cnt[y][u] ++;
a[y][++ top[y]] = a[x][top[x] --];
}
void solve(int u) {
if (u == 1)
return;
for (int i = 1; i < u; i ++) {
int c = cnt[i][u];
for (int j = c; j; j --)
move(u, u + 1);
for (int j = m; j; j --)
if (a[i][j] == u) move(i, u);
else move(i, u + 1);
for (int j = m - c; j; j --)
move(u + 1, i);
for (int j = c; j; j --)
move(u, i);
for (int j = c; j; j --)
move(u + 1, u);
}
for (int i = 1; i < u; i ++)
while (a[i][top[i]] == u)
move(i, u + 1);
int p = 1;
for (int j = top[u]; j; j --) {
if (a[u][j] == u) move(u, u + 1);
else {
while (top[p] >= m) p ++;
move(u, p);
}
}
solve(u - 1);
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i ++) {
top[i] = m;
for (int j = 1; j <= m; j ++)
a[i][j] = read(), cnt[i][a[i][j]] ++;
}
solve(n);
printf("%d\n", t);
for (int i = 1; i <= t; i ++)
printf("%d %d\n", ans[i].first, ans[i].second);
return 0;
}
// I hope changle_cyx can pray for me.算法三
注意到「算法二」中,一个颜色一个颜色来考虑有点浪费。可不可以多个颜色一起考虑呢?这启发我们分治。
定义分治函数 solve(l, r),取中点 \text{mid} = \left\lfloor \frac{l + r}{2} \right\rfloor。
在每一轮中我们的目的是:将所有 “ 颜色 \leq \text{mid} 的球 “ 与 “ 颜色 > \text{mid} 的球 “ 区分开来。
即:经过一系列操作过后,不存在一根柱子上同时有 “ 颜色 \leq \text{mid} 的球 “ 和 “ 颜色 > \text{mid} 的球 “。
随后调用 solve(l, mid) 与 solve(mid + 1, r)。
问题的关键在于如何区分。
在每一轮中,我们将这 r - l + 1 根柱子取出来。每次我们可以挑出两根柱子:
- (1):如果 “ 颜色 \leq \text{mid} 的球 “ 超过了 m 个。
则选取任意 m 个 “ 颜色 \leq \text{mid} 的球 “ 作为关键球,进行「算法一」中的基本操作。 - (2):如果 “ 颜色 > \text{mid} 的球 “ 超过了 m 个。
则选取任意 m 个 “ 颜色 > \text{mid} 的球 “ 作为关键球,进行「算法一」中的基本操作。
这样进行 r - l 次,这 r - l + 1 根柱子也就达到了每一轮的目的,递归下去解决即可。
考虑分治树的结构,共有 \mathcal{O(\log n)} 层。对于每层的所有节点,进行上述的基本操作的复杂度是 \mathcal{O(nm)} 的。
时间复杂度为 \mathcal{O(nm \log n)}。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
inline int read() {
int x = 0, f = 1; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
return x * f;
}
const int N = 60, M = 410;
int n, m;
int top[N], a[N][M];
int em;
int t;
pair<int, int> ans[820001];
void move(int x, int y) {
ans[++ t] = make_pair(x, y);
a[y][++ top[y]] = a[x][top[x] --];
}
bool impx[M], impy[M];
int merge(int x, int y, int mid) {
int cx = 0, cy = 0;
for (int i = 1; i <= m; i ++)
impx[i] = a[x][i] <= mid,
impy[i] = a[y][i] <= mid;
for (int i = 1; i <= m; i ++)
cx += impx[i], cy += impy[i];
if (cx + cy > m) {
cx = m - cx, cy = m - cy;
for (int i = 1; i <= m; i ++)
impx[i] ^= 1, impy[i] ^= 1;
}
for (int i = 1; i <= m; i ++)
if (!impx[i] && cx + cy < m)
impx[i] = 1, cx ++;
for (int i = cx; i; i --)
move(y, em);
for (int i = m; i; i --)
if (impx[i]) move(x, y);
else move(x, em);
for (int i = m - cx; i; i --)
move(em, x);
for (int i = cx; i; i --)
move(y, x);
for (int i = cx; i; i --)
move(em, y);
for (int i = cx; i; i --)
move(x, em);
for (int i = m; i; i --)
if (impy[i]) move(y, em);
else move(y, x);
int p = em; em = y;
return p;
}
void solve(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
vector<int> now;
for (int i = 1; i <= n + 1; i ++) {
if (i == em) continue;
if (l <= a[i][1] && a[i][1] <= r) now.push_back(i);
}
for (int i = 0; i + 1 < (int)now.size(); i ++)
now[i + 1] = merge(now[i], now[i + 1], mid);
solve(l, mid), solve(mid + 1, r);
}
int main() {
n = read(), m = read();
em = n + 1;
for (int i = 1; i <= n; i ++) {
top[i] = m;
for (int j = 1; j <= m; j ++)
a[i][j] = read();
}
solve(1, n);
printf("%d\n", t);
for (int i = 1; i <= t; i ++)
printf("%d %d\n", ans[i].first, ans[i].second);
return 0;
}
// I hope changle_cyx can pray for me. T4. 微信步数
Solution
算法一
部分分:w_i \leq 10^6。
不难想到,可以考虑计算 “ 走完了第 i 步后恰好走出场地 “ 的所有点对答案的贡献。
为了方便叙述,约定:
- 一个周期:前 n 步组成的路线。
- L_i:在第 i 个维度上,当前仍然在场地内的点的坐标的最小值。
- R_i:在第 i 个维度上,当前仍然在场地内的点的坐标的最大值。
- \overrightarrow{v}:经过了一个周期后的位移向量;v_i:位移向量 \overrightarrow{v} 在第 i 个维度上的位移。
引理 1
若会出现某一个点死循环,则满足以下两个条件。
(1):经过了一个周期后,存在一个点没有走出场地。
(2):\overrightarrow{v} = \overrightarrow{0}。
证明
必要性:显然。
充分性:考虑满足(1)的点,因为 \overrightarrow{v} = \overrightarrow{0},所以无论走了多少个周期,该点始终呆在原地,也不会在走周期的过程中走出场地。故出现死循环。
故命题得证,QED。
考虑一下什么情况下会对答案造成贡献。
引理 2
若第 i 步对答案有贡献,则当前在第 c_i 维上的位移,一定是向 “ 正方向 “ 走或向 “反方向 “ 走的历史位移最大值(即可以更新 L_{c_i} 或 R_{c_i})。
证明
考虑 L_i 和 R_i 的定义,不难发现:在第 c_i 维中,所有离开场地的点的坐标一定在 [1, L_{c_i}) \ \bigcup \ (R_{c_i}, w_{c_i}] 内。
那么,若第 i 步后 L_{c_i} 或 R_{c_i} 没有得到更新,那么 [1, L_{c_i}) \ \bigcup \ (R_{c_i}, w_{c_i}] 是不会变的,故离开场地的点的集合也没变。故在该种情况下,第 i 步不对答案造成贡献。
进一步分析可知:若第 i 步后 L_{c_i} 或 R_{c_i} 得到了更新,那么这一批离开场地的点的坐标均为更新后的 L_{c_i} - 1 或 R_{c_i} + 1。
故命题得证,Q.E.D
考虑一下该种情况下会造成多少贡献。
引理 3
若第 i 步对答案有贡献,则该贡献值为 i \times \prod\limits_{j \neq c_i} (R_j - L_j + 1)。
证明
对于第 c_i 维,这一批离开场地的点的坐标均为更新后的 L_{c_i} - 1 或 R_{c_i} + 1。
对于除了第 c_i 维的任意一个维度,现在考虑第 p 维。
显然,这一批离开场地的点的坐标可以在 [L_p, R_p] 中任意做选择。
根据乘法原理,这一批离开场地的点共有:
即为:
将上式乘上 i,即为第 i 步对答案的贡献值。
故命题得证,Q.E.D
至此,我们已经有方法可以计算出正确的答案。只不过,要是直接枚举 i 的话,时间复杂度是不能接受的。
我们还没有利用到移动路线的 “ 周期性 “,接下来就来讨论一下 “ 周期性 “ 在本题中的特殊效果。为了方便叙述,我们称可以对答案造成贡献的一步为 ” 特殊步 “。
引理 4
(1):当第一周期中的第 i 步为 “ 特殊步 “ 时:
- 则第二周期中的第 i + n 步,第三周期中的第 i + 2n 步,…,均不一定为 “ 特殊步 “。
(2):当第一周期中的第 i 步为 “ 特殊步 “,且第二周期中的第 i + n 步也为 “ 特殊步 “ 时:
- 第三周期中的第 i + 2n 步,第四周期中的第 i + 3n 步,…,一定均为 “ 特殊步 “。
引理 4 的推论
第一周期中 “ 特殊步 “ 的分布是特殊的; 第二、三、四、… 周期中 “ 特殊步 “ 的分布是相同的。
根据引理 4 的推论,我们可以先计算出第一周期中 “ 特殊步 “ 对答案的贡献。
对于第二、三、四、… 周期,考虑步数模 n 的结果,对于模 n 的所有同余类 \overline{1}, \overline{2}, \cdots, \overline{n - 1}, \overline{0},我们可以分别计算每个同余类对答案的贡献。
引理 5
设当前进行到了第 i 步,若进行到了第 i + n 步时,该点还在场地内,对于第 j 维的变化是:
(1):若 v_j > 0,则 L_j \gets L_j + |v_j|。
(2):若 v_j < 0,则 R_j \gets R_j - |v_j|。
(3):对于 R_j - L_j + 1,其值将会变化为:
证明
不难发现,若 “ 进行到第 i + n 步时,该点还在场地内 “。
则 “ 前 i 步组成的路径 “ 与 “ 前 i + n 步组成的路径 “ 之间只差了一个周期位移向量 \overrightarrow{v}。
(在该情况下,位移的先后顺序不影响最终结果)
那么,在只考虑第 j 维的情况下。
相当于进行到了第 i 步,然后又经过了一个周期后,坐标值被加上了 v_j。
故命题得证,Q.E.D
引理 5 的推论
对于第二周期中的第 i 步(其中 n < i \leq 2n),若第 i 步是一个 “ 特殊步 “。
考虑第 n \ast x + (i - n) 步,若该步也是一个 “ 特殊步 “,则该步对答案的贡献为:
即:
至此,已经有了一个初步的做法。
枚举 i = 1 \to n,先计算出第一周期中 “ 特殊步 “ 对答案的贡献。
再枚举 i = (n + 1) \to 2n,计算每个模 n 的同余类 \overline{i - n} 对答案的贡献。具体地,根据引理 5 的推论,在循环内部再枚举一个 x 即可。
时间复杂度玄学,上界是 \mathcal{O}(nk \times \max\limits_{1\leq i\leq k} \left\{w_i\right\}),但实际上远不能达到上界,所以可以拿到可观的 80 分。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read() {
int x = 0, f = 1; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
return x * f;
}
const int N = 500100, SIZE = 11;
const int mod = 1e9 + 7;
int n, k;
int w[SIZE];
int c[N], d[N];
int L[SIZE], R[SIZE];
int v[SIZE];
int u[SIZE];
int cur[SIZE];
int ans;
int main() {
n = read(), k = read();
for (int i = 1; i <= k; i ++)
w[i] = read();
for (int i = 1; i <= n; i ++)
c[i] = read(), d[i] = read();
// judgment has no answer.
for (int i = 1; i <= k; i ++)
L[i] = 1, R[i] = w[i];
for (int i = 1; i <= n; i ++) {
v[c[i]] += d[i];
if (v[c[i]]) {
if (v[c[i]] > 0) {
int val = v[c[i]];
if (w[c[i]] - val < R[c[i]]) R[c[i]] = w[c[i]] - val;
} else {
int val = -v[c[i]];
if (val + 1 > L[c[i]]) L[c[i]] = val + 1;
}
}
}
bool flag1 = 1;
for (int i = 1; i <= k; i ++)
if (L[i] > R[i]) flag1 = 0;
bool flag2 = 1;
for (int i = 1; i <= k; i ++)
if (v[i]) flag2 = 0;
if (flag1 && flag2) {
puts("-1");
return 0;
}
// work
for (int i = 1; i <= k; i ++)
L[i] = 1, R[i] = w[i];
for (int i = 1; i <= n; i ++) {
int C = c[i], D = d[i];
u[C] += D;
bool great = 0;
if (u[C]) {
if (u[C] > 0) {
int val = u[C];
if (w[C] - val < R[C])
R[C] = w[C] - val, great = 1;
} else {
int val = -u[C];
if (val + 1 > L[C])
L[C] = val + 1, great = 1;
}
}
if (great) {
int val = 1;
for (int j = 1; j <= k; j ++) {
if (j == C) continue;
val = 1ll * val * (R[j] - L[j] + 1) % mod;
}
ans = (ans + 1ll * val * i) % mod;
if (L[C] > R[C]) {
printf("%d\n", ans);
return 0;
}
}
}
for (int i = n + 1; i <= 2 * n; i ++) {
int C = c[i - n], D = d[i - n];
u[C] += D;
bool great = 0;
if (u[C]) {
if (u[C] > 0) {
int val = u[C];
if (w[C] - val < R[C])
great = 1;
} else {
int val = -u[C];
if (val + 1 > L[C])
great = 1;
}
}
if (great) {
int mul = i;
for (int j = 1; j <= k; j ++) cur[j] = R[j] - L[j] + 1;
bool keep = 1;
while (keep) {
int val = 1;
for (int j = 1; j <= k; j ++) {
if (j == C) continue;
val = 1ll * val * cur[j] % mod;
}
ans = (ans + 1ll * val * mul) % mod;
mul = (mul + n) % mod;
for (int j = 1; j <= k; j ++) {
cur[j] -= abs(v[j]);
if (cur[j] <= 0) {
keep = 0;
break;
}
}
}
}
if (u[C]) {
if (u[C] > 0) {
int val = u[C];
if (w[C] - val < R[C])
R[C] = w[C] - val;
} else {
int val = -u[C];
if (val + 1 > L[C])
L[C] = val + 1;
}
}
if (L[C] > R[C]) {
printf("%d\n", ans);
return 0;
}
}
printf("%d\n", ans);
return 0;
}
// I hope changle_cyx can pray for me. 算法二
特殊性质:w_i \leq 10^9。
看起来「算法一」非常有前途,考虑优化。优化的重点其实在于计算模 n 的所有同余类 \overline{1}, \overline{2}, \cdots, \overline{n - 1}, \overline{0} 对答案的贡献。
对于第二周期中的第 i 步(其中 n < i \leq 2n),若第 i 步是一个 “ 特殊步 “。
考虑第 n \ast x + (i - n) 步,若该步也是一个 “ 特殊步 “,则不难发现,该步对答案的贡献是一个与 x 有关的多项式,可以考虑用 f(x) 表示:
注意到 f(x) 的每个乘积项,都是关于 x 的一次二项式。
可以考虑将这 k 个乘积项卷在一起,即可得到一个 k 次多项式 f(x)。至于计算出 f(x) 的系数,直接暴力卷即可,因为 k 很小,所以复杂度肯定是可以接受的。
多项式乘法(卷积):
- 给定两个多项式 f(x) 与 g(x):
- 要计算多项式 Q(x) = f(x) \times g(x):
考虑计算贡献。设模 m 的同余类 \overline{i} 从第二周期开始,最多要计算到第 E 轮,不难得到:
此时贡献为:
将 f(x) 用 \sum\limits_{i = 0}^k a_i \times x^i 替换,得:
交换枚举顺序,得:
至于要快速计算函数 S_k(n) = \sum\limits_{i = 1}^n i^k,是一个非常经典的问题。详见 CF622F The Sum of the k-th Powers。
本篇题解中,代码给出的是 “ 拉格朗日插值 “。
代码中并没有直接拉格朗日插值,而是使用拉格朗日插值先预处理出 S_k(n) 所对应的关于 n 的 k + 1 次多项式,然后再代入 x 进行计算。
时间复杂度 \mathcal{O}(nk^2)。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int read() {
int x = 0, f = 1; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -f; s = getchar(); }
while (s >= '0' && s <= '9') { x = x * 10 + s - '0'; s = getchar(); }
return x * f;
}
int power(int a, int b, int p) {
int ans = 1;
for (; b; b >>= 1) {
if (b & 1) ans = 1ll * ans * a % p;
a = 1ll * a * a % p;
}
return ans;
}
const int N = 500100, SIZE = 20;
const int mod = 1e9 + 7;
int n, k;
int w[SIZE];
int c[N], d[N];
int L[SIZE], R[SIZE];
int v[SIZE];
int u[SIZE];
struct polynomial {
int m;
int num[SIZE];
polynomial() {
m = 0;
memset(num, 0, sizeof(num));
}
polynomial(int a, int b, int c) { m = a, num[0] = b, num[1] = c; }
};
polynomial operator + (polynomial a, polynomial b) {
polynomial c;
c.m = a.m;
for (int i = 0; i <= a.m; i ++)
c.num[i] = (a.num[i] + b.num[i]) % mod;
return c;
}
polynomial operator * (polynomial a, polynomial b) {
polynomial c;
c.m = a.m + b.m;
for (int i = 0; i <= a.m; i ++)
for (int j = 0; j <= b.m; j ++)
c.num[i + j] = ((c.num[i + j] + 1ll * a.num[i] * b.num[j]) % mod + mod) % mod;
return c;
}
int calc(polynomial a, int x) {
int ans = 0;
for (int i = 0, val = 1; i <= a.m; i ++, val = 1ll * val * x % mod)
ans = (ans + 1ll * a.num[i] * val) % mod;
return ans;
}
polynomial g[SIZE];
int val[SIZE];
void Lagrange(int K) {
val[0] = 0;
for (int i = 1; i <= K + 2; i ++) val[i] = (val[i - 1] + power(i, K, mod)) % mod;
g[K].m = K + 1;
for (int i = 1; i <= K + 2; i ++) {
polynomial p = polynomial(0, 1, 0);
int q = 1;
for (int j = 1; j <= K + 2; j ++) {
if (i == j) continue;
p = p * polynomial(1, mod - j, 1);
q = 1ll * q * (((i - j) + mod) % mod) % mod;
}
p = p * polynomial(0, power(q, mod - 2, mod), 0);
p = p * polynomial(0, val[i], 0);
g[K] = g[K] + p;
}
}
int ans;
int main() {
n = read(), k = read();
for (int i = 1; i <= k; i ++)
w[i] = read();
for (int i = 1; i <= n; i ++)
c[i] = read(), d[i] = read();
// judgment has no answer.
for (int i = 1; i <= k; i ++)
L[i] = 1, R[i] = w[i];
for (int i = 1; i <= n; i ++) {
v[c[i]] += d[i];
if (v[c[i]]) {
if (v[c[i]] > 0) {
int val = v[c[i]];
if (w[c[i]] - val < R[c[i]]) R[c[i]] = w[c[i]] - val;
} else {
int val = -v[c[i]];
if (val + 1 > L[c[i]]) L[c[i]] = val + 1;
}
}
}
bool flag1 = 1;
for (int i = 1; i <= k; i ++)
if (L[i] > R[i]) flag1 = 0;
bool flag2 = 1;
for (int i = 1; i <= k; i ++)
if (v[i]) flag2 = 0;
if (flag1 && flag2) {
puts("-1");
return 0;
}
// work
for (int i = 1; i <= k; i ++)
L[i] = 1, R[i] = w[i];
for (int i = 1; i <= n; i ++) {
int C = c[i], D = d[i];
u[C] += D;
bool great = 0;
if (u[C]) {
if (u[C] > 0) {
int val = u[C];
if (w[C] - val < R[C])
R[C] = w[C] - val, great = 1;
} else {
int val = -u[C];
if (val + 1 > L[C])
L[C] = val + 1, great = 1;
}
}
if (great) {
int val = 1;
for (int j = 1; j <= k; j ++) {
if (j == C) continue;
val = 1ll * val * (R[j] - L[j] + 1) % mod;
}
ans = (ans + 1ll * val * i) % mod;
if (L[C] > R[C]) {
printf("%d\n", ans);
return 0;
}
}
}
for (int i = 0; i <= k; i ++)
Lagrange(i);
for (int i = n + 1; i <= 2 * n; i ++) {
int C = c[i - n], D = d[i - n];
u[C] += D;
bool great = 0;
if (u[C]) {
if (u[C] > 0) {
int val = u[C];
if (w[C] - val < R[C])
great = 1;
} else {
int val = -u[C];
if (val + 1 > L[C])
great = 1;
}
}
if (great) {
int Round = 0x3f3f3f3f;
for (int j = 1; j <= k; j ++) {
if (!v[j]) continue;
Round = min(Round, ((R[j] - L[j]) / abs(v[j])) + 1);
}
polynomial f = polynomial(0, 1, 0);
f = f * polynomial(1, i - n, n);
for (int j = 1; j <= k; j ++) {
if (j == C) continue;
f = f * polynomial(1, R[j] - L[j] + 1 + abs(v[j]), mod - abs(v[j]));
}
for (int j = 0; j <= k; j ++)
ans = (ans + 1ll * f.num[j] * calc(g[j], Round)) % mod;
}
if (u[C]) {
if (u[C] > 0) {
int val = u[C];
if (w[C] - val < R[C])
R[C] = w[C] - val;
} else {
int val = -u[C];
if (val + 1 > L[C])
L[C] = val + 1;
}
}
if (L[C] > R[C]) {
printf("%d\n", ans);
return 0;
}
}
printf("%d\n", ans);
return 0;
}
// I hope changle_cyx can pray for me.