Hello World!
在无数久的 🐦咕咕咕 后一个博客它建成了!
一些有用的网站:
关于我:
- QQ: 2465478971
- E-Mail: 2465478971qq@gmail.com
- Codeforces ID:platelet platelets
- Atcoder ID:songjiaxing platelets
- 洛谷 ID:plate_let
1 | _|_| _| _| _| |
在无数久的 🐦咕咕咕 后一个博客它建成了!
一些有用的网站:
关于我:
1 | _|_| _| _| _| |
懒得分开写咕咕咕。
“1”的限制分两种,在同一行或在同一列,但 “1” 的数量很多,不能枚举每个“1”是哪一种,设“在同一行”的边为白边,“在同一列的”的边为黑边,考虑边之间的约束关系。
考虑两条边 \((i,j),(i,k)\),当边 \((j,k)\) 存在时说明 \((i,j)\) 和 \((i,k)\) 的颜色相同,反之亦然。
这样就可以表示出所有的约束,必要性显然,充分性是因为合法解中同色边一定构成了若干不含公共边的团,这种对于相邻两条边的约束关系就很充分了。
在所有的约束条件下,所有的边及其约束关系构成类似二分图的结构,对于每个连通块,设它一部分的所有边形成了 \(x\) 个点连通块,另一部分的所有边形成了 \(y\) 个点连通块,那么它可以占用 \(x\) 行 \(y\) 列或 \(y\) 行 \(x\) 列。
最后可以通过简单 DP 计算答案。
复杂度 \(O(n^3)\)。
任意时刻局面的样子都是若干个连续段,我们只关心每个连续段的样子和它们在环上的相对顺序,而不关心空白的位置,因为只要知道前者的方案数,当前局面的方案数是可以算的。
对于 \(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 | int ans[MAXROW]; // 存每一行的最小值在哪一列 |
有 \(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\)。
给定前 \(k\) 个字母的 \(01\) 前缀编码(不存在一个编码是另一个编码的前缀)。
给定字符串 \(s\),设其解码后的 \(01\) 串为 \(S\),求最多能将 \(S\) 划分为多少段使得每一段都无法解码,无解输出 \(-1\)。
\(k \le 52, n\le 10^6\)
首先考虑两种特殊情况:
剩下的情况为:有 \(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 | #include <bits/stdc++.h> |
有 \(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 函数的形式参数声明中使用 auto
。
1 | auto lambda = [](auto x, auto y) { return x + y; }; |
允许 lambda 函数的捕获部分中定义变量同时初始化。
1 | int a = 1, b = 2, c = 3; |
允许成员函数中的 lambda 函数以拷贝的方式捕获 *this
。
1 | struct node { int value; void func(); }; |