莓在执行任务时，收集到了 n 份岩浆能源， 其中第 i 份的能量值是 wi ，她 决定将它们分成恰好 k 组带回基地，每一组都要有至少 1 份能源。 每一组能源会对运输设备产生负荷值，若该组有 x 份能源，这 x 份能源能 量值之和为 y , 则产生的负荷值为 x × y 。 每种分组方案产生的负荷是每一组能源产生的负荷值总和，莓想知道所有可 能的分组方案产生的负荷之和对 998244353 取模

题目链接 喜提最快解 (?) ## 题目 给定\(n,k\) 求满足\(\gcd(A_{l\cdots r})\cdot(A-l\ \mathjaxrm{xor} \ A_{l+1}\ \mathjaxrm{xor} \cdots \mathjaxrm{xor} \ A-r)=k\)且字典序最小的\(l,r\) 分析 可以看我前两篇博客 按照基本方法，枚举右端点\(r\) 然后我们需要什么呢

题目： UVa1642 solution 因为要求一个最优的子序列，可以想到枚举这个子序列的右端点\(j\)。 那么怎么快速算出左端点\(i\)的答案呢？ 枚举每一个左端点，如果能知道这个子序列所有元素的\(gcd\)值就好了。 先考虑这样一个序列\(5,8,8,6,2\)，假设现在\(j=4\),可以算出所有子序列对应的\(gcd\)。 1. \(i=1\), \(gcd(a_1,a_2,a_3

题目: luogu 签到题IV 话说这道题和UVA1642 魔法GCD很类似 # Solution 题目要求找所有满足条件的子序列，可以考虑固定右端点\(j\)，然后快速求出每个左端点\(i\)对应的子序列的有关信息。 好像有点抽象，可以想一下这个序列怎么做。 \[3,4,6,4,2\] \(j=4\)时，我们写一下所有子序列的有关值，即\(gcd(a-i,a_{i+1}...a-j)\)和\((

题目链接 和社论不一样的方法 ## 题目 已知\(f(n) = \prod\limits_{d|n} \mu(d)\) 求\(\sum\limits_{i=1}^n f(i) \bmod 998244353\)，\(n\leq 10^{10}\) 分析 求\(\sum\limits_{i=1}^n\prod\limits_{d|i} \mu(d)\) 我们来观察一下\(\prod\limits

题目链接 按位看每一个数。 如果某两个数是逆序对，那必然是有一个高位不同。 如果两个数在那一位上面都\(\text{xor}\)上\(1\)，两个数的大小关系将会颠倒。 所以我们可以通过这种方式使逆序对变成顺序对，对于\(x\)的每一位，我们需要知道有哪些数是从这一位开始不同的，也就是这一位改变会使多少逆序对变成顺序对。 把所有数都插入\(01tire\)里面，每个节点记录一下被经过了多少次。

题目链接 编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之 间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。 例如将kitten一字转成sitting： sitten （k->s） sittin （e->i） sitting （->g） 所以kitten和sitt

题目链接 这道题的正解竟然就是 dfs +剪枝... 可以把题目理解成用木板去塞木材，最多塞多少个。 先将不可能塞的不板和不可能被塞的木材排除。 二分答案最多能塞多少个木板，搜索每个木材塞到哪个板，显然用更小的木板来塞一定不会更差。 记录前 mid 个木板的和，总的木材的和。 搜索的时候随时减去不能再被塞的木材。 如果某个时候\(sum[mid]+w\ge S\)则 return 如果木板大小

题目链接 破环成链，\(f[i][j]\)表示点\([i,j]\)的最大价值。 转移时枚举最后一个三角形的划分方法即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include<cstdio>using namespace std;#defin

题目链接 这道题很妙啊... 首先这个建边方式，很自然就能想到按题意串与串连边。 但是这样的复杂度是不能接受的。 我们只需要将每个串前两个字符对应的节点和后两个对应的节点连边就可以了，不难发现这样也是等价的。 现在边建好了，很自然就能想到用 spfa 跑最长路。 这样的时间复杂度也是不能接受的... 我们并不能直接知道答案是多少，于是二分答案上去验证 如果一个环\(\frac{a-1+a-2+