0%

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

一些有用的网站:

关于我:

  • 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\) 个连续段的方案数,转移分三种:

阅读全文 »

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
#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;
using ll = long long;

const int N = 1e6 + 5;

int n;
char S[N], T[N]; bool s[N * 4], t[N * 4];
ll t0, t1, ts;

void get(char S[], bool s[]) {
n = 0;
for(auto i = S; *i; i++) {
int j = *i > 57 ? *i - 55 : *i - 48;
per(k, 3, 0) s[++n] = j >> k & 1;
}
};
int main() {
int test;
for(cin >> test; test--;) {
scanf("%*d%lld%lld%lld%s%s", &t0, &t1, &ts, S, T);
get(S, s), get(T, t);
stack<pair<int, ll>> stk[2];
ll as = 0;
rep(i, 1, n) if(s[i] ^ t[i]) {
ll mi = s[i] ? t1 : t0;
if(stk[!s[i]].size()) {
auto [j, w] = stk[!s[i]].top();
ll tmp = ts * (i - j) - w;
if(tmp < mi) mi = tmp, stk[!s[i]].pop();
}
stk[s[i]].emplace(i, mi), as += mi;
}
printf("%lld\n", as);
}
}
阅读全文 »

\(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++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

函数返回类型推导。

阅读全文 »

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;
}
};
阅读全文 »