在文章《K 进制 FWT》发表评论：

@Zi_Gao 可以令其为x，然后视为多项式做乘法卷积mod k阶分圆多项式（在此意义下有x^k \equiv 1)

rt 没找到具体评测机说明

K 进制 FWT # 引入 问题：给定长度为 $k^n$ 的序列 $A_i,B_i$，求 $$ C_i=\sum_{j \oplus k=i} A_j B_k $$ 其中 $\oplus$ 是任意一种 $k$ 进制**按位**运算。 # 通用解法 我们希望定义变换 $$ \hat{F}(i)=\sum_{j=0}^{k…

在讨论《暴力list启发式合并+tag模拟无人机位置即可》回复：

@[fanchuanyu](luogu://user/706256) 《也不是很难写》

在讨论《该测试点可能不止满足题面所述特殊性质》回复：

这很正常啊，毕竟是多测

设 $f(x)$ 表示 $x$ 的校验值。容易发现 $f$ 是完全积性函数，且若 $p$ 是质数，则 $f(p)=-1$。 设 $t$ 的标准分解式为： $$t=\prod_{i}p_i^{\alpha_i}$$ 则： $$ \begin{aligned} f(t)=\prod_{i}(-1)^{\alpha_i}\e…

先把所有的数减去平均值。这样就要求每个连通块的和为 $0$。设 $a$ 为减完之后的值，以及： $$ \begin{aligned} s_{i,j}&=\sum_{k=1}^{j} a_{i,k}\\ S_{j}&=s_{0,j}+s_{1,j} \end{aligned} $$ 设计 DP。设 $f(i)$ 为考虑前…

在文章《题解：AT_joisc2019_g 指定都市 (Designated Cities)》发表评论：

什么是「拿 b_{p-1} 去替换掉前面最小的项」？？？

闭合： $$ \left\{ \begin{aligned} \mathcal{E}(t)&=-L \cdot I'(t)\\ U+\mathcal{E}(t)&=R \cdot I(t) \end{aligned}\right. \\ %R \cdot I(t) + L \cdot I'(t) = U\\ \boxe…

在文章《employ》发表评论：

s名字重了

[例题](http://nflsoi.cc:10611/p/P10122) 时间限制 3s。 本题有 $O(nm2^m)$ 的正常做法（std），也有 $O(n^2m)$ 的暴力做法（实际指令集优化为 $O(n^2 \lceil \frac{m|\Sigma|}{\omega} \rceil)=O(n^2)$ 可过）。…

如果在同一位置，上方的数字大于下方的数字，则这两个之中必须要移除至少一个。将上面的点向下方连边，就变成了一个二分图，求最大匹配。使用 [Hopcroft-Karp 算法](https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm) 即可在 $O(E\sq…

枚举第一个加油站 $i$。可以二分出最大的距离 $\le d$ 的加油站 $k_m$。则 $i #define int long long using namespace std; const int N = 500005; int n, d, ans, t[N], x[N]; int m, X[N], sm[N],…

枚举 $i$，钦定 $a_i=\min_{x=l}^r a_x$。再枚举 $j=\lfloor \dfrac{\max_{x=l}^r a_x}{\min_{x=l}^r a_x} \rfloor$。我们要统计最小值为 $a_i$，最大值在一个范围 $[a_ij, a_i(j+1)-1]$ 内的区间的个数。 对原序列建…

补充一下另一篇题解。 注：X 轴为路程，Y 轴为时间。 画出 s-t 图像。就是用一个折线从 $(0,0)$ 到 $(m+1,\le s)$，且不能经过一些横线（即不能撞火车）。 显然有，折线一定会经过某个横线的端点。处理出这些端点连成的直线，并算出直线的合法区间。 注意折线还可以沿着横线走（即重合）。这部分需要单独处…

简要题意： > 求 > $$\sum_{g=0}^m [g \oplus (P-1) \equiv 1 \pmod P]$$ 对所求式进行转化。 $$ \begin{align*} &\sum_{g=0}^m [g \oplus (P-1) \equiv 1 \pmod P] \\=&\sum_{g=0}^m [\ex…

简要题意： > 给定一颗有 $N$ 个点的树。你可以删除最多 $K$ 个点。最小化删完之后所有连通块大小的最大值。回答最小化的最大值。 显然答案具有可二分性。考虑二分答案 $S$。问题变成了： > 删除最多 $K$ 个点，是否可以使得所有连通块大小 $\le S$。 贪心地处理这个问题。对树进行 dfs，设现在 dfs…

简要题意： > 给定一个 $n$ 个点的带权无向完全图和它的一颗根为 $1$ 的生成树。有 $t$ 组询问。每组询问给定 $d$。你需要找两个点 $p,q$，满足： > > * 设 $p$ 和 $q$ 的 LCA 为 $l$。则存在序列 $A=\{(p,q),\dots,(l,l)\}$，使得： > * 对于 $A$…

在讨论《在线求助数学题》回复：

@[fcy20180201](luogu://user/866154)  答案为 16。至于怎么算的，问 MMA。

在讨论《有人有OI-WIKI PDF版本吗》回复：

（暂无内容）

---- [NFLSOJ P50](http://www.nfls.com.cn:10611/p/P50) 完成某件事情的期望代价通常采用 逆推 的形式，因为我们知道 终止状态 的局面，但不知道初始状态的局面。因此，我们接下来所讨论的期望值的定义应和 接下来 局面的发展有关，而和之前局面是如何发展的无关。 ---- […

容易观察到一个引理： * 当且仅当通票可以乘坐的缆车的终点集合为 $\left\{2,3,\cdots,n\right\}$ 时符合题意。 > 证明： > > * 充分性：如果终点是 $2$，则这条路线一定是 $1 \to 2$，则 $2$ 是可达的。而如果 $2 \sim k$ 是可达的，且终点集合中包含 $k+1$…

在文章《[tricks] 分块优化在线二维数点》发表评论：

orz

在讨论《如何卡掉 DSU on tree？》回复：

@[PLDIS](luogu://user/302356) ？？？？？？？？？？？？ 为什么要卡掉我？

差分转化为求 $[1,x]$ 之间的 B-smooth 数。 记忆化搜索。先预处理出所有 $\le B$ 的质数。令 $f(x,i)$ 表示搜完前 $i-1$ 个质数，剩下的乘积 $\le x$ 的方案数。显然有 $f(x,i)=f(x,i+1)+f(\dfrac{x}{p_i},i)$ ，其中 $p_i$ 为第 $i…

一个不用 DP 的做法。 记 $f(x,l,r)$ 表示以初始 rating $x$，连续参加第 $l$ 场至第 $r$ 场比赛之后的 rating。 显然，若 $w_1 using namespace std; int f(int x, int y) { if (y > x) return x + 1; if (y…

在文章《震惊！事情真相太残酷！金霏不让大爷穿秋裤》发表评论：

什麼鬼

#16 TLE 1.02s，其余也有两个点跑了 900+ms。 ```cpp #include #define int long long using namespace std; const int N = 100005, p = 1e9 + 7; int fpow(int a, int b) { int res =…

在讨论《【集中处理】升学/换校快速处理》回复：

513329 南京外国语学校

在讨论《关于CSP的数据》回复：

肯定不會是完全隨機的，但是否能卡掉某一細節錯誤也不好説，要看這個細節具體是什麽。如果能通過所有的大樣例，那問題不大。