platelet's blog

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

一些有用的网站：

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

关于我：

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

1
2
3
4
5

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

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 自动机即可。

懒得分开写咕咕咕。

TC13459

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

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

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

在所有的约束条件下，所有的边及其约束关系构成类似二分图的结构，联通块分两类，一类是整个连通块一定同色，另一类是一定包含两种颜色。

设第一类连通块有 \(x\) 个，第二类连通块有 \(y\) 个，枚举第一类连通块有 \(i\) 个白色，即可得到答案： \[ \sum_{i=0}^x\binom xi2^yn^{\underline{i+y}}n^{\underline{x-i+y}} \] 复杂度 \(O(n^3)\)（DFS 求连通块）或 \(O(n^3\alpha(n^2))\)（并查集求连通块）。

TC12909

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

设 \(f_{i,j}\) 表示当前已经来了 \(i\) 个朋友，共构成 \(j\) 个连续段的方案数，转移分三种：

有 \(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\) 的余数。

积和式定义 \[ \text{perm }A = \sum_{p}A_{i,p_i} \] 当 \(A\) 是 \(01\) 矩阵时，有 \[ \text{prem} A = (-1)^n\sum_{x_i \in \{0,1\}}(-1)^{x1+x2+\cdots+x_n}\prod_{i=1}^n(Ax)_i \] 证明可以考虑容斥：枚举哪些行=列一定没有被选。

观察到式子中间有一个 \(\prod\) ，由于我们要求这个东西模 \(4\) 的余数，因此 \((Ax)_i\) 至多只能有一个位置模 \(2\) 为 \(0\)。

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

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

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

对这个矩阵做一些变换。 \[ \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} \] 这个矩阵的积和式等于原矩阵的积和式。

随机选取 \(v\)，则期望 \(O(1)\) 组解。

建议在编程中尝试使用 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

函数返回类型推导。

Barrett reduction 取模优化

计算 \(ab\bmod m(0\le a,b<m<2^{31})\)。

如果 \(m\) 在编译时已知，那么编译器就会帮你完成这个优化，否则你可以自己实现。

首先，设 \(m^{-1}\) 表示浮点数形式的 \(\frac 1m\)。 \[ ab\bmod m=ab-\lfloor ab\cdot m^{-1}\rfloor m \] 即使预处理了 \(m^{-1}\)，由于浮点数乘法比整数除法快不了多少，考虑进一步优化，取 \(\frac {m'}{2^k}\approx m^{-1}\)，然后 \[ \lfloor ab\cdot m^{-1}\rfloor \approx \lfloor \frac{abm'}{2^k}\rfloor \] 计算右边就快多了，因为只有整数乘法和右移，如何合理选取 \(m'\) 和 \(k\)？

令 \(k=2\lceil \log_2 m\rceil,m'=\lceil \frac{2^k}m\rceil\)，下面分析误差：

• 设 \(m'm=2^k+r(0\le r<m)\)
• 设 \(ab=cm+d(0\le c,d<m)\)
• \(abm'=(cm+d)m'=cm'm+dm'=c2^k+cr+dm'\)
• \(cr+dm'<(m-1)^2+m'm<(m-1)^2+2^k+(m-1)=2^k+m(m-1)<2^k\cdot 2\)
• \(\lfloor \frac{abm'}{2^k}\rfloor=c\ \text{or}\ c+1\)

设真实答案为 \(ans\)，那么 \(ab-\lfloor \frac{abm'}{2^k}\rfloor m=ans\ \text{or}\ ans-m\)。

更一般的结论是只要 \(c \ge \max(a, b^2)\)，\(\lfloor \frac{a\lfloor \frac cb\rfloor}c\rfloor=\lfloor \frac ab\rfloor\ \text{or}\ \lfloor \frac ab\rfloor+1\) 成立。

实践中可以令 \(k=64\)，可以用 ~0ull / m + 1 来计算 \(m'\)。

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

using uint = unsigned int;
using ull = unsigned long long;
struct barrett {
    uint m; ull im;
    barrett(uint m) :m(m), im(~0ull / m + 1) {}
    uint mul(uint a, uint b) const {
        ull z = (ull)a * b;
        ull x = (unsigned __int128)z * im >> 64;
        uint v = z - x * m;
        return m <= v ? v + m : v;
    }
};