考前的小知识积累

快考试了,整理一下最近学到的细碎的东西。东西很杂,也有一些叫不上名字来,简单写写吧……

max+ 矩阵乘法

定义一类新矩阵乘法:
$$ C= A * B\Leftrightarrow C_{i,j}=\max\limits_{i,j,k}A_{i,k}+B_{k,j} $$ 为矩阵的 max+ 乘法。注意到这类乘法是满足结合律的,因此可以快速幂优化。这类乘法的本质类似于一轮 Floyd 传递闭包。

相关题目:Hamsters

max+ 卷积

定义一类新的序列卷积:
$$ C=A*B\Leftrightarrow C_k=\max\limits_{i+j=k}A_i+B_j $$ 这类卷积很难做到低于 $O(n^2)$ 的复杂度内计算,但是如果 $A,B$ 都是离散意义下的凸函数的话,可以做到 $O(n\log n)$ 计算,方法如下:

把序列 $A,B$ 分别排序后差分,把得到的增量合并到一个序列中降序排序,这会得到一个长度为 $2n-2$ 的新序列,记为 $\text{d}$。注意到必然有 $C_0=A_0+B_0$,我们下一步需要按从大到小的顺序把增量加进去,即有 $C_1=C_0+\text{d}_0, C_i=C_{i-1}+\text{d}_{i - 1}$,于是就还原出了卷积后的结果 $C$,时间复杂度只有排序的 $O(n\log n)$。

这种做法的正确性在于:对于凸函数而言,增量 $\text{d}$ 的可取范围与其大小是相应变化的。那么如果做凹函数的 min+ 卷积的时候,也可以适用类似的做法。

斜率优化

有一种普适性的在亚线性时间复杂度内,解决一类距离最值问题的方法,通俗的叫法好像叫做斜率优化。

这类问题的一般模型是:定义一类新的距离 $\text{dist}(i,j)=A_i+B_j+C_iD_j$,求 $\min\limits_{i,j}\text{dist}(i,j)$。注意到关于 $i, j$ 的下标运算是二次的,因此无法拆开来简单维护。

考虑枚举 $i$,转化为求如下式的值:$p + \min\limits_{1\le j\le n} B_j+kD_j$,设有 $l_j=B_j+kD_j$,得到 $B_j=-kD_j+l_j$,这是一条过定点 $(D_j, B_j)$,斜率为 $-k$ 的直线,而我们要最小化的东西是这条直线的截距 $l_j$。

那么现在等价于给出一堆点 $(D_1,B_1),(D_2,B_2),…,(D_n,B_n)$ 和一个斜率 $-k$,让我们求一条直线使得截距最小。显然,所求点必然在这些点形成的下凸壳上,那么维护出下凸壳二分即可。
有时斜率给出的性质特殊,则可以单调维护;当点的选取范围有要求时,可以结合单调栈 / 线段树。

给出一个示例:求 $\min\limits_{i,j}a_i+b_j+(i-j)^2$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
stk[++top] = 1; 
for(int i = 2; i <= n; i++){
int u, v;
while(top > 1){
u = stk[top], v = stk[top - 1];
if(1ll * (b[u] - b[v]) * (i - u) < 1ll * (b[i] - b[u]) * (u - v)) break;
top--;
}
stk[++top] = i;
}
int p = 1, ans = 0x3f3f3f3f;
for(int i = 1; i <= n; i++){
int u = stk[p], v = stk[p + 1];
while(p < top && b[v] - 2 * i * v < b[u] - 2 * i * u)
p++, u = v, v = stk[p + 1];
u = stk[p], ans = min(ans, a[i] + b[u] - 2 * i * u);
}

相关题目:Thief

常幂展开在贡献法中的应用

看一道好题:

给出简单无向图 $G=(V,E)$,设 $S=(V_S,E_S)$ 为 $G$ 的某个导出子图,求 $\sum\limits_{S\subseteq G}|E_S|^k$。
$|V|,|E|\le 10^5, 1\le k\le 3$

显然,当 $k=1$ 时,我们可以运用贡献法考虑每条边对答案的贡献,因此得到答案即是 $|E|2^{|V|-2}$。

但是当 $k\ge 2$ 时,因为乘幂运算的缘故,直接使用贡献法是不可以的。根据常幂展开公式,我们可以这样给柿子变形:
$$ \begin{aligned}\sum\limits_{S\subseteq G}|E_S|^k= \sum\limits_{i=0}^k \begin{Bmatrix}k\newline i\end{Bmatrix}i!\sum\limits_{S\subseteq G}\dbinom{|E_S|}{i} \end{aligned} $$ 注意到这是求和,因此贡献法又适用了,那我们可以考虑求后面的 $\sum\limits_{S\subseteq G}\dbinom{|E_S|}{i}$。
考虑这个柿子的意义,我们可以等价于在原图中任意钦点 $i$ 条边出来,统计所有情况下包含 $i$ 条边的导出子图的数量。即我们考虑钦点一个组合数选出来的东西,然后考虑它的贡献,即它被选到的次数。

我们分类讨论。设边数为 $m$,点数为 $n$,对于 $k=2(i=(0),1,2)$ 的情况,可以这样分类:

  1. $i=1$,即选一条边,显然是 $m2^{n-2}$;
  2. $i=2$,即选两条边。注意到两条边可以共用一个端点,或者有四个独立的端点。我们只需要对这两种情况分别统计“方案数x被导出子图包含的次数”即可。

$k=3$ 的情况也可以类似的进行分类,于是就可以完成了。复杂度的瓶颈在于 $k=3$ 时的三元环计数,因此复杂度 $O(m^{1.5})$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int P = 1e9 + 7;
const int CN = 1e5 + 50;
const int i2 = 5e8 + 4;
const int i3 = 333333336;
int read(){
int s = 0, ne = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') ne = -1; c = getchar();}
while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
return s * ne;
}
int add(int x, int y) {return x + y >= P ? x + y - P : x + y;}
int C(int x) {return 1ll * (1ll * x * (x - 1) % P) * i2 % P;}
int n, m, k, pw[CN], du[CN];
namespace sub1 {void work(){printf("%lld", 1ll * m * pw[n - 2] % P);}}
namespace sub2 {
void work(){
int ans = 1ll * m * pw[n - 2] % P, s1 = 0, s2 = 0; // i = 1
for(int i = 1; i <= m; i++){
int x = read(), y = read(); du[x]++, du[y]++;
}
for(int i = 1; i <= n; i++) s1 = add(s1, C(du[i]));
s2 = add(C(m), P - s1);
if(n >= 3) s1 = 1ll * s1 * pw[n - 3] % P; else s1 = 0;
if(n >= 4) s2 = 1ll * s2 * pw[n - 4] % P; else s2 = 0;
s1 = add(s1, s2);
ans = add(ans, add(s1, s1));
printf("%d", ans);
}}
namespace sub3 {
int X[CN], Y[CN], col[CN]; vector<int> G[CN];
bool le(int i, int j) {return du[i] ^ du[j] ? du[i] < du[j] : i < j;}
void work(){
int ans = 0, cnt1 = 1ll * m * pw[n - 2] % P, cnt2 = 0, cnt3 = 0;
for(int i = 1; i <= m; i++){
int x = read(), y = read();
du[x]++, du[y]++, X[i] = x, Y[i] = y;
}
int s1 = 0, s2 = 0, s3 = 0, s4 = 0;
/* cnt2 */
for(int i = 1; i <= n; i++) s1 = add(s1, C(du[i]));
s2 = add(C(m), P - s1);
if(n >= 3) s1 = 1ll * s1 * pw[n - 3] % P;
else s1 = 0;
if(n >= 4) s2 = 1ll * s2 * pw[n - 4] % P;
else s2 = 0;
cnt2 = add(s1, s2);
/* cnt3 */
s1 = s2 = s3 = s4 = 0;
for(int i = 1; i <= m; i++){
int u = X[i], v = Y[i];
if(le(u, v)) G[v].pb(u); // v > u : v -> u
else G[u].pb(v);
}
for(int i = 1; i <= n; i++){
for(int l = G[i].size(), j = 0; j < l; j++) col[G[i][j]] = i;
for(int l = G[i].size(), t = 0; t < l; t++){
int j = G[i][t];
for(int ll = G[j].size(), tt = 0; tt < ll; tt++)
if(col[G[j][tt]] == i) s1++;
}
}
for(int i = 1; i <= m; i++) s2 = add(s2, 1ll * (du[X[i]] - 1) * (du[Y[i]] - 1) % P);
s2 = add(s2, P - (3ll * s1 % P));
for(int i = 1; i <= n; i++) s3 = add(s3, 1ll * C(du[i]) * (m - du[i]) % P);
s3 = add(s3, P - add(3ll * s1 % P, 2ll * s2 % P));
for(int i = 1; i <= n; i++){
int cur = 1ll * C(du[i]) * (du[i] - 2) % P; cur = 1ll * cur * i3 % P;
s2 = add(s2, cur);
}
s4 = 1ll * C(m) * (m - 2) % P, s4 = 1ll * s4 * i3 % P;
s4 = add(s4, P - add(add(s1, s2), s3));
if(n >= 3) s1 = 1ll * s1 * pw[n - 3] % P; else s1 = 0;
if(n >= 4) s2 = 1ll * s2 * pw[n - 4] % P; else s2 = 0;
if(n >= 5) s3 = 1ll * s3 * pw[n - 5] % P; else s3 = 0;
if(n >= 6) s4 = 1ll * s4 * pw[n - 6] % P; else s4 = 0;
cnt3 = add(add(s1, s2), add(s3, s4));
/* answer */
cnt2 = 6ll * cnt2 % P, cnt3 = 6ll * cnt3 % P;
ans = add(cnt1, add(cnt2, cnt3)), printf("%d", ans);
}}
int main()
{
n = read(), m = read(), k = read();
pw[0] = 1; for(int i = 1; i <= n; i++) pw[i] = add(pw[i - 1], pw[i - 1]);
if(k == 1) sub1 :: work();
if(k == 2) sub2 :: work();
if(k == 3) sub3 :: work();
return 0;
}

Lorem Ipsum

一个新的技巧:

众所周知,将 $m$ 划分为 $n$ 个非负整数有 $\dbinom{m+n-1}{n-1}$ 种方案。对于任意方案 $P$,我们定义 $val_k(P)$ 表示该划分中第 $k$ 大的数(降序排序后的第 $k$ 个)。设 $S$ 为总方案集,现在给定 $m,n,k$,请求出 $\sum\limits_{P\in S}val_k(P)$。
$n,m\le 5000$

设 $f[k,l]$ 表示一个划分中至少有 $k$ 个数字 $\ge l$ 的划分的数量。首先有等式:
$$ \sum\limits_{P\in S} val_k(P) =\sum\limits_{l=1}^mf[k,l] $$ 这个可以这样理解:我们考虑对于任意一个方案中第 $k$ 大的数,设它是 $p$,那么对于 $\forall l\le p$ 的 $f[k,l]$,$p$ 都会在 $f[k,l]$ 中被累加一次,一共累加 $p$ 次,因此这样是正确的。

那么现在的问题是求出“至少有 $k$ 个数字 $\ge l$ 的划分数”,这是一个“至少”限制,因此不可以直接选出来。可以这样理解:直接拿组合数选出来的是“钦定某 $k$ 个数字 $\ge l$ 的划分数”,而我们要求的是“有任意至少 $k$ 个数字 $\ge l$ 的划分数”。

形式化的说,设 $g[k,l]$ 为“恰好 $k$ 个数字 $\ge l$ 的划分数”,$h[k,l]$ 为“钦定 $k$ 个数字 $\ge l$ 的划分数”,$f[k,l]$ 为“至少有 $k$ 个数字 $\ge l$ 的划分数”,那么有:
$$ \begin{align} h[k,l]&=\dbinom{n}{k}\dbinom{m-kl+n-1}{n-1}\newline &=\sum\limits_{j=k}^n\dbinom{j}{k}g[j,l] \newline \Leftrightarrow g[k,l]&=\sum\limits_{j=k}^n(-1)^{j-k}\dbinom{j}{k}\dbinom{n}{k}\dbinom{m-kl+n-1}{n-1} \end{align}$$ 即是二项式反演,注意到这里实现了“钦定”到“恰好”的转化。“恰好”到“至少”的转化也可以类似的表示:
$$ \begin{align} f[k,l]&=\sum\limits_{j=k}^n g[j,l]\newline \Leftrightarrow g[k,l]&=f[k,l]-f[k+1,l] \end{align} $$ 总结来说,二项式反演联系了“钦定”与“恰好”限制,前/后缀和和差分联系了“至少”和“恰好”限制。

用 set 维护线段覆盖

看这样一个问题:

给出 $n$ 条线段 $[l_1,r_1],…[l_n,r_n]$,$q$ 次询问编号在 $[a,b]$ 内的线段覆盖的总长度是多少。
$n,q\le 10^5, l_i, r_i \le 10^9$

首先离线询问,把每个询问挂在询问区间的右端点上。考虑枚举询问的右端点 $b$,并用数据结构来维护每个 $i(i\le b)$ 的答案。

考虑怎样能快速地维护。如果对数轴上的每一个点维护一下它最后一次被覆盖是在什么时候(没覆盖就是 0),那么可以发现数轴会被划分成若干值相同的连续段。注意到同一时刻连续段的数量只有 $O(n)$ 种,那么我们考虑用 set 去维护这个东西。

具体来说,我们可以维护一个二元组 $(r,t)$,其中 $r$ 是当前连续段的分界点(右端点),$t$ 是当前连续段最晚被覆盖的时间。我们考虑新加入一个段 $(r_i,i)$,那么首先所有与其有交的连续段都会受到影响。具体来说,会有一些连续段被完全覆盖,即等价于删除,还有至多两个连续段会被分裂成两部分,其中一部分被保留,另一部分被替代。

我们考虑如果删除了一个连续段 $(r’,t’)$,它的长度是 $l$,那么左端点在 $[t’+1,i]$ 内区间的答案都会被加上 $l$,因为当前连续段的影响从 $t’$ 扩大到了 $i$。那么我们需要一个数据结构,支持区间加和单点求值,那么套一个 BIT 就可以解决了。时间复杂度是 $O(n\log n)$。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define iter set<PAIR> :: iterator
const int CN = 1e5 + 50;
int read(){
int s = 0, ne = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') ne = -1; c = getchar();}
while(c >= '0' && c <= '9') s = (s << 1) + (s << 3) + c - '0', c = getchar();
return s * ne;
}
class PAIR {
public: int x, y;
bool operator < (const PAIR &o) const {return x ^ o.x ? x < o.x : y < o.y;}
};
PAIR mp(int a, int b) {PAIR o; o.x = a, o.y = b; return o;}
set<PAIR> S; vector<PAIR> Q[CN];
int n, m, L[CN], R[CN], ans[CN];
class BIT {
public: int d[CN];
void add(int p, int x) {while(p <= n) d[p] += x, p += p & (-p);}
void md(int l, int r, int x) {add(l, x), add(r + 1, -x);}
int qu(int p) {int r = 0; while(p) r += d[p], p -= p & (-p); return r;}
} D;
int main()
{
n = read(), m = read();
for(int i = 1; i <= n; i++) L[i] = read(), R[i] = read();
for(int i = 1; i <= m; i++){
int l = read(), r = read();
Q[r].pb(mp(l, i));
}
S.insert(mp(1e9, 0));
for(int i = 1; i <= n; i++){
int l = L[i], r = R[i], fst = -1, prv = l - 1;
iter it = S.lower_bound(mp(l, 0));
while(1){
if(it == S.end()) break;
int cur = (*it).x, p = (*it).y, len;
if(fst < 0) fst = p;
len = min(cur, r) - prv, D.md(p + 1, i, len);
if(cur <= r){
prv = cur;
iter pit = it; it++, S.erase(pit);
}
else break;
}
if(l > 1) S.insert(mp(l - 1, fst));
S.insert(mp(r, i));
for(int l = Q[i].size(), j = 0; j < l; j++)
ans[Q[i][j].y] = D.qu(Q[i][j].x);
}
for(int i = 1; i <= m; i++) printf("%d", ans[i]), puts("");
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×