0%

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

一些有用的网站:

关于我:

  • 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++11C++14C++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

函数返回类型推导。

阅读全文 »