AFO
追踪最近的用户名外显变动记录。
最近的文章、讨论、云剪贴板与社区记录
首先对偶数的 $m$，可以用巴什博弈的策略，$(m+1)\mid n$ 时必败。下面假设 $m$ 是奇数。 我们计算每个状态 $(n,ban)$ 是必胜态或必败态，$ban$ 为上一次取的数量。注意到对于一个 $n$，要么总是必败态，要么只有不超过一个 $ban$ 是必败的。从前往后考虑，遇到一个必败的 $n$，则 $…
下面为了方便操作，把条件改成先降后升，最后反过来。 考虑一个增量法。在排列后面加一个 $p_{n+1}=n+1$，也就是加一个自环，让 $(n,m)$ 变成 $(n+1,m+1)$。如果 $p_1=n$，我们可以往环里塞一个单点，也就是令 $p_1=n+1,p_{n+1}=n$，让 $(n,m)$ 变成 $(n+1,m…
# 概述 区间 DP 是 DP 状态是一段区间的信息的 DP。这种问题，可能子状态是天然的一段区间。更多的时候问题涉及合并或分裂。一个元素由原序列的一段区间的元素合并而成，我们可以考虑当前区间由哪些段合并而成。或者在区间内取一些特殊元素，分成若干区间，这些区间是比较独立的子问题。一种特殊情况是笛卡尔树式的 DP，取区间…
# 极限 我们先来定义数列的极限。感性理解，极限是指这个数列越往后，值会越靠近某个值 $a$，且这个靠近可以无限接近，我们将其描述为对于任意一个距离 $\varepsilon$ 都可以比它更小，且在某个点之后都满足距离比 $\varepsilon$ 小。因此可以定义： 数列的极限：设 $x_n$ 为一数列，如果存在常数…
三重求和问题，同时反演三个 $\gcd$，可以得到 $\sum_{u=1}^n\sum_{v=1}^n\sum_{w=1}^n(D\ast\mu)_u(E\ast\mu)_v(F\ast\mu)_w\sum_{u\mid i,v\mid i}A_i\sum_{u\mid j,w\mid j}B_j\sum_{v\mid…
对于每条从根出发的链，上面的点的排名是确定的。考虑如何刻画大小关系，可以建出一张图。从上往下，到达一个节点 $pos$ 时找到它在它的祖先中的前驱 $u$ 和后继 $v$，会产生两个大小关系 $u\to pos,pos\to v$，最后会得到一个 DAG 描述了偏序关系。 拓扑序计数通常不可做，但这里图形态很特殊，总形…
这个询问差分后是一个点 $u$ 的邻居中有几个满足 $p_v using namespace std; const int p[10]={1,3,9,27,81,243,729,2187,6561,19683}; int t,n,q[32][50005],temp[50005],ans[32][50005],num[5…
考虑合法排列的形态。有序排列是例外。对于其他排列，会有一段红色的前缀和蓝色的后缀不动，中间的一段红色的每个数都必须往后动，蓝色的必须往前动。因此中间这一段都满足 $p_i\ne i$，且红色的满足 $p_i i$。此时分成两种情况讨论： 若可能形成有序排列，即不存在 $p_i\ne-1\wedge p_i\ne i$。…
# 笛卡尔树上 DP 通常用于处理排列/序列最值相关的限制，一般形如区间 DP $f_{l,r}$。 这类题能用区间 DP 处理的原因是这个区间确定最值的位置后，跨越这个点的 $\min$ 或 $\max$ 都确定，劈成的两个区间是相对独立的。这个结构是最大值/最小值的分治树，也就是笛卡尔树。 另一种情况是这个序列上的…
显然 $C$ 从小到大/从大到小选，按 $C$ 排序，则 $C$ 的贡献是 $-2$ 倍极差，因此选一个区间 $[l,r]$，强制首尾要选，权值是 $V$ 在 $(l,r)$ 的前 $k-2$ 大和加 $V_l+V_r-2(C_r-C_l)$。 注意到它有决策单调性。四边形不等式，只和端点有关的抵消，剩 $(l,r)$…
爆标做法。考虑把 DP 套 DP 直接扔掉，钦定当前状态按后 $1/2/4$ 个分段，强行分讨去掉重复情况： 最后一个分段，$f_i\gets f_i+f_{i-1}$； 若 $[i-1,i]$ 相邻，最后两个分段，要求这两个交换，否则被两个 $1$ 段替代，$f_i\gets f_i+f_{i-2}$。 若 $[i-…
考虑这个神秘的限制是说不存在 $x,y,x,y$。若 $a_l=a_r$，则 $(l,r)$ 内的数都不会出现在其他位置，形成一个嵌套关系。 我们可以考虑建出一个树形结构，将每种数以第一次出现为根连成一个菊花，数之间按嵌套关系连边。具体来说，维护一个栈，每次将当前位置连向栈顶，然后若它是第一次出现就入栈，若它是最后一次…
题意：$n$ 个物品有 $V_i,C_i$，选恰好 $m$ 个物品按某个顺序排成一个环，权值是 $V_i$ 的和减环上相邻两个物品 $C_i$ 之差，最大化权值。 显然 $C$ 从小到大/从大到小选，按 $C$ 排序，则 $C$ 的贡献是 $-2$ 倍极差，因此选一个区间 $[l,r]$，强制首尾要选，权值是 $V$…
设 $A,B$ 为 $a,b$ 的前缀和，$w(l,r)$ 是区间 $[l,r]$ 的权值。显然，这个权值函数几乎是上凸的，想到决策单调性优化 DP。但是这不一定对，有可能 $w(a,c)+w(b,d)$ 刚好卡在升级之前，导致比 $w(a,d)+w(b,c)$ 小 $1$。 一个巧妙的想法是，把 $w$ 补全成连续的…
补充一下，三进制 FWT 是不必要的。我们只要凑出系数 $h_0=f_0g_0,h_1=f_0g_1+f_1g_0,h_2=f_1g_1$。这个构造 $f_0g_0,(f_0+f_1)(g_0+g_1),f_1g_1$ 即可，正变换为 $\begin{bmatrix}1&0&0\\1&1&0\\0&1&0\end{bm…
不推式子，直接上科技。二维积性函数求和可以做到 $O(n^\frac23\log n)$。 考虑拓展积性函数的定义。定义二维积性函数 $f(a,b)$ 满足 $f(1,1)=1$，且 $\forall\gcd(ab,xy)=1,f(ax,by)=f(a,b)f(x,y)$。类似，我们可以定义多元积性函数。 从质数处的点…
有简单的爆标做法，轻松构造出 $n=1.2\times10^6$。 核心思路是有两个块 $[l_1,r_1],[l_2,r_2]$，每块中的点距离为 $1$，我们可以 $l_2\to r_1\to l_2+1\to r_1-1\cdots$ 这样跳。 现在我们需要构造块间的转移。考虑倍增两个块的距离，比如设第 $i$…
在讨论《关于 DFA 找等价类数目》回复：
造自动机的过程要判是否合法
在讨论《关于 DFA 找等价类数目》回复：
挂了指跑出来 DFA 变化，判定可以直接记搜，枚举三个字符替换
在讨论《关于 DFA 找等价类数目》回复：
先写个阈值较大的，然后不断改小，看什么时候挂了
问题看上去很不可做。根据一些经验，对这种问题，我们可以猜测一个下界。直接注意到，答案不超过 $2$。 删去偶数边，我们总可以做到将图黑白染色，使每个点与偶数个同色点相邻，此时最小割/最大流为偶数。可以这么构造：取出一个奇数点删掉，对与这个点相邻的每一对点 $(u,v)(u\ne v)$ 之间加一条边，递归构造子问题。不…
对于 $ans=0\sim31$，求使 $\operatorname{popcount}$ 增加到 $ans$ 的最小操作数。显然，根据二进制的性质，我们会让前若干个 $0$ 变成 $1$。假设我们让 $0\sim i$ 位变成 $1$，不难感受到一个贪心：从 $i$ 位枚举到 $0$ 位，若当前位为 $0$，选择代价…
# 异或线性基 把每一个二进制数的看作一个位数维的向量，异或相当于模二意义下的加法，这样的线性基为异或线性基。异或线性基就是对于给定的数，求出一组数，从中选数异或能产生给定数异或的所有结果，且这组数的数量最小。 异或线性基解决的问题一般会从序列里挑任意个数异或起来。根据定义，线性基的异或能表示原序列异或的所有可能，而且…
询问中位置 $i$ 能取到的数是 $a_{l\sim i}$ 中选数异或能得到的数。显然我们可以对每个左端点求出合法的最大 $r$。此时有一个暴力，从前往后，设位置 $i-1$ 操作后变成 $a'_{i-1}$，在 $a_{l\sim i}$ 的线性基中找到能表出的第一个大于 $a'_{i-1}$ 的数。 考虑固定左端…
杜教筛（给定积性函数 $f\ast g=h$，已知 $g,h$ 块筛，求 $f$ 的块筛）可以不借助 zak 筛手法做到 $O(\frac{n^\frac23}{\log n})$。 我们考虑人为地让取值变稀疏。有结论：对于任意 $0 n^\alpha],f(i)[\operatorname{lpf}(i)>n^\al…
动态 FMT 问题有复杂度更优的随机化做法，来源是 [[集训队互测 2024] 观虫我](https://qoj.ac/problem/9518)，复杂度 $O(n(\frac43)^{\log V})$。 首先我们可以想到高低位分块的根号做法。考虑这个做法的实质是什么。现在对于每一位，有两种贡献的路径：修改时 $0\…
类似题目 [gym102586J](https://codeforces.com/gym/102586/problem/J)，[P12294](https://www.luogu.com.cn/problem/P12294)。按某种简单规则判定 01 串，可以考虑造一个自动机判定。 考虑直接根据等价关系建自动机，根据…
首先因为魔方阵的所有数不同，旋转翻转必定不同，只需在最后除以 $8$。 先不考虑有数相同。对于每个质因数，考虑其次数，相当于一个加法的幻方。设中间的数为 $n$，则一行和为 $3n$（三行总和 $3S$，过中间的四条线总和 $4S=3S+3n$，则 $S=3n$）。枚举两个格子的数，就能确定其余所有格： ^2+(Y-y_i)^2$ 因式分解。通常这会用到虚数，在模意义下就是 $p=299993$ 的二次剩余。则 $(X-x_i)^2+(Y-y_i)^2=(X-x_i+I(Y-y_i))(X-x_i-I(Y-y_i))$。这就是说，将原坐标系的每个点映射至 $(x+Iy,x-…