platelet's blog

在无数久的 🐦咕咕咕 后一个博客它建成了！

一些有用的网站：

• uDebug
• Codeforces Official
• Codeforces m2
• LaTeX 各种命令，符号
• graph editor

关于我：

• QQ: 2465478971
• E-Mail: 2465478971qq@gmail.com
• Codeforces ID：platelet platelets
• Atcoder ID：songjiaxing platelets
• 洛谷 ID：plate_let

1
2
3
4
5

  _|_|                              _|  _|    _|  
_|    _|  _|  _|_|  _|_|_|_|        _|  _|  _|    
_|    _|  _|_|          _|          _|  _|_|      
_|    _|  _|          _|      _|    _|  _|  _|    
  _|_|    _|        _|_|_|_|    _|_|    _|    _|

懒得分开写咕咕咕。

TC13459

“1”的限制分两种，在同一行或在同一列，但 “1” 的数量很多，不能枚举每个“1”是哪一种，设“在同一行”的边为白边，“在同一列的”的边为黑边，考虑边之间的约束关系。

考虑两条边 \((i,j),(i,k)\)，当边 \((j,k)\) 存在时说明 \((i,j)\) 和 \((i,k)\) 的颜色相同，反之亦然。

这样就可以表示出所有的约束，必要性显然，充分性是因为合法解中同色边一定构成了若干不含公共边的团，这种对于相邻两条边的约束关系就很充分了。

在所有的约束条件下，所有的边及其约束关系构成类似二分图的结构，对于每个连通块，设它一部分的所有边形成了 \(x\) 个点连通块，另一部分的所有边形成了 \(y\) 个点连通块，那么它可以占用 \(x\) 行 \(y\) 列或 \(y\) 行 \(x\) 列。

最后可以通过简单 DP 计算答案。

复杂度 \(O(n^3)\)。

TC12909

任意时刻局面的样子都是若干个连续段，我们只关心每个连续段的样子和它们在环上的相对顺序，而不关心空白的位置，因为只要知道前者的方案数，当前局面的方案数是可以算的。

题目链接

对于 \(n\times m\) 的 \(01\) 矩阵 \(mat\)，定义序列 \(A,B,C\)：

• \(A_i(1\le i \le n)\) 表示最小的 \(j\) 满足 \(mat_{i,j}=1\)（如果没有则为 \(m+1\)​）。

• \(B_i(1\le i \le m)\) 表示最小的 \(j\) 满足 \(mat_{j,i}=1\)（如果没有则为 \(n+1\)​）。 ​

• \(C_i(1\le i \le n)\) 表示最大的 \(j\) 满足 \(mat_{j,i}=1\)（如果没有则为 \(0\)​）。

有多少种不同的三元组 \((A,B,C)\)？模 \(998244353\)。

\(n \le 8000,m\le 200\)

设 \(dp_{m,n}\) 表示 强制 每行至少有一个黑格时 \(n\times m\) 矩阵的答案。

那么答案就是 \(\sum_{i=0}^N\binom Nidp_{M,i}\)。

转移考虑哪些行的第一个黑格在最后一列，分两种情况：

• 没有任何一行的第一个黑格在最后一列，那么最后一列可以没有黑格，可以恰好有一个，也可以多于一个，三种的方案对应的情况数分别是 \(1,n,\binom n2\)，转移系数为 \(1+n+\binom n2\)。

• 有 \(k(k\ge 1)\) 行的第一个黑格在最后一列，相当于最后一列已经事先填好了 \(k\) 个黑格，设这些黑格中自上到下第一个在第 \(a\) 行，最后一个在 倒数 第 \(b\) 行，这种方案对应的情况数是 \(ab\)，转移系数为

\[ \sum_{a,b}\binom a1\binom{n-a-b}{k-2}\binom b1=\binom{n+2}{k+2}=\binom{n+2}{n-k} \]

综上，转移式为

\[ dp_{m,n}=dp_{m-1,n}(1+n+\binom n2)+\sum_{k=0}^{n-1}dp_{m-1,k}\binom{n+2}k \]

转移可以使用 NTT 优化，复杂度 \(O(NM\log N)\)，下面有复杂度更低的做法。

转移时乘的是组合数，考虑写成 EGF：记 \(F_m(x)=\sum dp_{m,n}\frac{x^n}{n!}\)。

如果一个 \(N\times M\) 的矩阵 \(A\) 满足四边形不等式： \[ \forall i_1<i_2,j_1<j_2,A_{i_1,j_1}+A_{i_2,j_2}\le A_{i_1,j_2}+A_{i_2,j_1} \] 则称矩阵 \(A\) 是完全单调的。

SMAWK 算法解决的问题是求 \(A\) 每行的最小值，这个问题当然可以用基于决策单调性的分治法做，但 SMAWK 的复杂度更为优秀。假设可以 \(O(1)\) 计算矩阵 \(A\) 中的一个元素，SMAWK 的复杂度为 \(O(N+M)\)​。

矩阵 \(A\) 的一个性质是决策单调性，即每行取到最小值的列编号随行编号递增。证明不困难，考虑 \[ A_{i,j}+A_{i+1,j+1}\le A_{i,j+1}+A_{i+1,j}\Rightarrow A_{i,j+1}-A_{i,j}\ge A_{i+1,j+1}-A_{i+1,j} \] 即 \(A_{*,j}\) 比 \(A_{*,j+1}\) 随行数增加得更快，如果第 \(i\) 行的最小值在第 \(j\) 列取到，那么在 \(i\) 之后的行，\(j\) 之前的列都比第 \(j\) 列劣。

SWAWK 的核心操作是 reduce，可以去掉一些没用的列，使得剩余列数不超过行数。

reduce 操作维护一个存列编号的栈，它的性质为：对于栈内自底向上第 \(i\) 个元素 \(x\) 和第 \(i+1\) 个元素 \(y\)，满足 \(A_{i,x}< A_{i,y}\)。初始栈为空，然后从小到大插入每一列。假设当前要插入 \(c\)，栈顶元素为 \(top\)，栈的大小为 \(size\)，如果 \(A_{size,top}\ge A_{size,c}\)，那么可以弹掉 \(top\)，原因：假设 \(top\) 在栈中的前一个元素为 \(x\)，由于 \(A_{size-1,x}< A_{size-1,top}\)，在第 \(1\rightarrow size-1\) 行中 \(top\) 没有 \(x\) 优秀，同理，在第 \(size\rightarrow n\) 行中 \(top\) 没有 \(c\) 优秀，故第 \(top\) 列是没用的。

弹掉没用的元素之后，如果当前栈的大小为 \(n\)，说明此时 \(A_{n,top}< A_{n,c}\)，元素 \(c\) 就不用插入了。否则就插入 \(c\)，这不会破环栈的性质。最后栈内的剩余元素就是可能有用的列。

reduce 操作之后先求出偶数行的最小值和取到最小值的列，这是一个子问题，之后可以通过决策单调性 \(O(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

int ans[MAXROW]; // 存每一行的最小值在哪一列
int A(int x, int y) {
    // O(1) 计算 A[x][y]
}
// 求第 0, k, 2k, 3k, ... 行的最小值
void SMAWK(int k, const vector<int>& row, const vector<int>& col) {
    vector<int> Stack;
    for(int c : col) {
        while(!Stack.empty()) {
            int r = Stack.size() - 1;
            if(A(r, c) > A(r, Stack.back())) break;
            Stack.pop_back();
        }
        if(Stack.size() < row.size()) Stack.push_back(c);
    }
    // ↑ reduce
    if(k < row.size()) SMAWK(k << 1, row, Stack);
    int r = k, c = 0;
    auto chkmin = [&]() {
        if(A(r, Stack[c]) < A(r, ans[r])) ans[r] = Stack[c];
    };
    while(r + k < row.size()) {
        while(Stack[c] < ans[r + k]) chkmin(), c++;
        r += k << 1;
    }
    if(r < row.size()) while(c < Stack.size()) chkmin(), c++;
}

AUOJ1760

有 \(n\) 个物品，其中可能有一个次品，它的质量与其他物品有差异。你需要多次使用天平后回答谜题：是否存在次品？次品是偏轻还是偏重？称量时，在天平两边放相同数量的物品，以得知那边更重。

构造一个能够解决谜题且称量次数最少的固定称量方案。

\(n \le 10^6\)

考虑什么样的称量方案能够解决谜题。

假设称量次数为 \(m\)，定义矩阵 \(A\)： \[ A_{i,j}= \begin{cases} -1 &(第 j 次称量物品 i 在天平左边)\\ 0 &(第 j 次称量物品 i 不在天平上)\\ 1 &(第 j 次称量物品 i 在天平右边) \end{cases} \] 首先怎么判断有没有次品：如果有物品没上过天平，哪无论如何都不能判断，否则可以判断，不存在次品当且仅当每次天平都平衡。

得到条件一：\(A_i\ne \{0,0,\cdots, 0\}\)。

确定了有次品，怎么确定是哪一个：先考虑已知次品偏重时怎么确定，根据每次天平的倾斜情况，可以得到每次称量时次品在天平的哪一边或不在天平上，定义序列 \(B\)： \[ B_i= \begin{cases} -1 &(第 i 次称量次品在天平左边)\\ 0 &(第 i 次称量次品不在天平上)\\ 1 &(第 i 次称量次品在天平右边) \end{cases} \] 然后看 \(B\) 和 \(A_?\) 相等就可以确定次品是哪一个。

但是并不知道次品偏重还是偏轻，上面说了假设次品偏重可以得到一个序列 \(B\)，类似地假设次品偏轻可以得到一个序列 \(C\)，并且满足 \(C=-B\)（元素对于互为相反数），可以解决谜题的条件是 \(B\) 和 \(C\) 不能同时和某个 \(A_i\) 相等。

得到条件二：\(\forall i \ne j, A_i\ne A_j \land A_i \ne -A_j\)。

由于每次称量时两边放相同数量的物品。

得到条件三：\(\forall j\in[1,m],\sum_{i=1}^nA_{i,j}=0\)。

URAL2118

给定前 \(k\) 个字母的 \(01\) 前缀编码（不存在一个编码是另一个编码的前缀）。

给定字符串 \(s\)，设其解码后的 \(01\) 串为 \(S\)，求最多能将 \(S\) 划分为多少段使得每一段都无法解码，无解输出 \(-1\)。

\(k \le 52, n\le 10^6\)

首先考虑两种特殊情况：

• 编码中既有 \(0\)，也有 \(1\)，那 \(S\) 无论怎么划分都可以解码。
• 编码中既没 \(0\)，也没 \(1\)，那么答案为 \(|S|\)。

剩下的情况为：有 \(0\) 无 \(1\) 和有 \(1\) 无 \(0\)，由于对称性，只考虑有 \(0\) 无 \(1\)。

首先答案的上界为 \(1\) 的个数，因为全 \(0\) 的一段是可以被解码的。

如果最后一位为 \(1\)，那么在每个 \(1\) 后面断开，就可以取到这个上界。

如果最后一位为 \(0\)，假设最后一段 \(T\)，可以说明存在最优解满足 \(T\) 前面是 \(1\)：假设 \(T\) 前面有 连续 的 \(x\) 个 \(0\)，前面总共有 \(y\) 个 \(1\)。那么答案的上界为 \(y+1\)，把这 \(x\) 个 \(0\) 加入 \(T\)，然后在 \(T\) 前面的每个 \(1\) 后面断开就可以到达这个上界。

如果 \(T\) 前面有 \(y\) 个 \(1\)，最大段数就是 \(y+1\)，问题就是求最大的 \(y\)，假设 \(T'\) 是最短的无法被解码的后缀，可以说明最大的 \(y\) 等于 \(T'\) 前面 \(1\) 的个数：由于 \(|T|\ge |T'|\)，所以 \(y\) 不会超过 \(T'\) 前面 \(1\) 的个数，另外，令 \(T=T'前面极长的一段0+T'\)，\(y\) 就可以取到这个上界。

问题转化成了求 \(T'\)，那么 \(T'\) 的任何前缀都无法解码，否则 \(T'\) 不是最短的，记 \(suffix(i)\) 表示 \(S\) 长度为 \(i\) 的后缀，问题就是依次判断 \(suffix(1),suffix(2),suffix(3),\cdots\) 是否有前缀可以被解码，AC 自动机即可。

有 \(n\) 个数，每个数都是不超过 \(m\) 的质数，问有多少种情况它们的异或和等于 \(0\)。

答案对给定的模数 \(p\) 取模。

\(n \le 10^9, m \le 3 \cdot 10^6\)，保证 \(p\) 是奇数。

定义一个位向量 \(A\)，满足 \[ A_i = \begin{cases} 1 &(i \le m \land i \in \text{Prime})\\ 0 &(otherwise) \end{cases} \] 定义乘法为异或卷积，那么 \((A^n)_0\) 就是答案。

用 FWT + 快速幂可以做到 \(O(m \log m\log n)\)。

但如果先 FWT，再把每个位置上的值变成它的 \(n\) 次方，最后 IFWT，复杂度 \(O(m(\log n + \log m))\)。

但还不足以通过此题，因为模数是变量，快速幂极慢，调用 \(O(m)\) 次会 TLE。

考虑 FWT 的定义： \[ FWT(A)_i = \sum_{2\ |\ pop(j \& i)}A_j - \sum_{2\ \not|\ pop(j \& i)}A_j \] 可以知道 \(|FWT(A)_i| \le \sum_iA_i\)，以及 \(FWT(A)_0 = \sum_iA_i\)。

\(\sum_iA_i\) 即 \(m\) 以内质数个数，是 \(O(\frac m {\log m})\) 级别的，可以预处理这 \(O(\frac m {\log m})\) 个值的 \(n\) 次方。

这样就只需要做 \(O(\frac m {\log m})\) 次快速幂。

代码：

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

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define pb push_back

using namespace std;

typedef long long ll;
const int N = 1 << 22;

int n, m; ll P;
int pid, f[N], g[N], prm[216900], b, lim = 1;

ll Pow(ll a, int n, ll r = 1) {
    for(; n; n /= 2, a = a * a % P)
    if(n & 1) r = r * a % P;
    return r;
}
void FWT(int a[]) {
    For(i, 0, b) For(S, 0, lim) if(S >> i & 1) {
        int& x = a[S ^ 1 << i], y = a[S];
        a[S] = x - y, x += y;
    }
}

int main() {
    cin >> n >> m >> P;
    if(P == 1) puts("0"), exit(0);
    while(lim <= m) lim *= 2, b++;
    rep(i, 2, m) {
        if(!f[i]) prm[++pid] = i;
        for(int j = 1; i * prm[j] <= m; j++) {
            f[i * prm[j]] = 1;
            if(i % prm[j] == 0) break;
        }
    }
    mem(f, 0);
    rep(i, 1, pid) f[prm[i]]++, g[i] = Pow(i, n);
    FWT(f);
    int as = 0;
    For(S, 0, lim) (as += (f[S] < 0 && n % 2 ? -1 : 1) * g[abs(f[S])]) %= P;
    cout << (as + P) * Pow(P / 2 + 1, b) % P;
    return 0;
}

题目链接

有 \(n\) 个人和 \(m\) 个限制，以及 \(T +1\) 个时刻。限制分两种：

• 如果 \(x\) 在 \(t\) 时刻是死亡状态，则 \(y\) 在 \(t+1\) 时刻是死亡状态。
• 如果 \(x\) 在 \(t\) 时刻是生存状态，则 \(y\) 在 \(t\) 时刻是死亡状态。

对于每个人 \(i\)，求出其他人中有多少个人 \(j\) 满足 \(i\) 与 \(j\) 能够同时存活到最后。

\(n \le 5 \cdot 10^4,m \le 10^5,t \le T \le 10^6\)

对于每个人每个时刻，建生死两个点。

对于第一种限制，连有向边 \(Dead(x,t) \rightarrow Dead(y,t+1),Alive(y,t+1) \rightarrow Alive(x,t)\)。

对于第二种限制，连有向边 \(Alive(x,t) \rightarrow Dead(y,t),Alive(y,t) \rightarrow Dead(x,t)\)。

另外，由于每个人不能复活，连有向边 \(Dead(x,t) \rightarrow Dead(x,t+1),Alive(x,t+1) \rightarrow Alive(x,t)\)。

首先有一些 \(x\) 满足 \(Alive(x,T+1)\) 能到 \(Dead(x, T+1)\)，删除 \(Alive(x,T+1)\) 和 \(Dead(x, T+1)\)。

如果从 \(Dead(x,T+1)\) 不能到达 \(Dead(y,T+1)\)，则 \(y\) 对 \(x\) 造成贡献。

建图时其实只有所有的 \((x,t)\) 和所有 \((x,T+1)\) 有用，\((x,t)\) 向 \((y,t')\) 连边，其中 \((y,t')\) 是横坐标为 \(y\) 的点中第一个纵坐标大于（等于）的点，取决于是哪种限制，然后 \(Dead(x,t)\) 向后继连边，\(Alive(x,t)\) 向前驱连边。

求 \(Dead(x,T+1)\) 能到达多少 \(Dead(y,T+1)\) 可以用 bitset 优化 DP。

但空间开不下，bitset 只能开 \(10000\)，因此需要每 \(10000\) 个点做一次 DP。

题目链接

给定一个两边各有 \(n\) 个点的二分图，判断完美匹配的个数是否是 \(4\) 的倍数。

\(n \le 300\)

完美匹配的个数即积和式。

来自论文的算法：求积和式模 \(4\) 的余数。

积和式定义：考虑所有选 \(n\) 个不同行、不同列的数的方案，对每个方案中 \(n\) 个数的乘积求和。 \[ \text{perm} A = \sum_{p}A_{i,p_i} \] 当 \(A\) 是 \(01\) 矩阵时，有 \[ \text{prem} A = (-1)^n\sum_{x \in \{0,1\}^n}(-1)^{x1+x2+\cdots+x_n}\prod_{i=1}^n(Ax)_i \] 证明可以考虑容斥：钦定某些列没有数被选。

观察到式子中间有一个 \(\prod\) ，由于我们要求这个东西模 \(4\) 的余数，如果它要造成贡献的话，\(Ax\) 就至多有一个位置模 \(2\) 为 \(0\)。

考虑 \(Ax\) 每一项模 \(2\) 的余数，由于至多只能有一个 \(0\)，因此可以枚举这个东西的取值，它只有 \(n+1\) 种。

对于每种取值，通过高斯消元解出满足条件的所有 \(x\)，再将每一组 \(x\) 代入刚刚的式子中求出答案。

问题是，合法的 \(x\) 的个数可能很大，因为需要枚举自由元的取值。

对这个矩阵做一些变换，记为 \(A'\)。 \[ \begin{bmatrix} A_{1,1}&A_{1,2}&\cdots &A_{1,n}&v_1\\ A_{2,1}&A_{2,2}&\cdots &A_{2,n}&v_2\\ \vdots&&&&\vdots\\ A_{n,1}&A_{n,2}&\cdots &A_{n,n}&v_n\\ 0&0&\cdots&0&1 \end{bmatrix} \] 显然 \(\text{perm} A' = \text{perm} A\)。

随机选取 \(v\)，则期望 \(O(1)\) 组解：一组 \(x\) 要有贡献，\(x_{n+1}=1\)（注意这一点，不能枚举 \(x_{n+1}=0\)，否则复杂度会假），因此翻转 \(v\) 中的任意一位，\(A'x\) 也会翻转对应的一位，所以对于一个确定的 \(A'x\)，每一组 \(x\) 成为它的解的概率都是 \(\frac 1{2^n}\)。

建议在编程中尝试使用 C++17，可以一定程度上简化代码编写，提高编程效率。

从 C++11 到 C++14 和 C++17 的部分实用特性：

lambda 的泛型参数和捕获的增强。

允许 lambda 函数的形式参数声明中使用 auto。

1
2

auto lambda = [](auto x, auto y) { return x + y; };
// since C++14

允许 lambda 函数的捕获部分中定义变量同时初始化。

1
2
3

int a = 1, b = 2, c = 3;
auto lambda1 = [value = a + b] { return value + c; };
// since C++14

允许成员函数中的 lambda 函数以拷贝的方式捕获 *this。

1
2
3
4
5
6
7
8
9
10
11
12

struct node { int value; void func(); };
int node::func() {
    auto lambda = [this]() { return ++value; }; // by reference
    return lambda();
}
// since C++11
struct node { int value; void func(); };
int node::func() {
    auto lambda = [*this]() { return ++value; }; // by copy
    return lambda();
}
// since C++17

函数返回类型推导。