主要思路
首先对于 \(d = 1\)，答案就是 \(k^n\)。
对于 \(d = 2\)，其实发现可以用生成函数来直接乘：\( A(x) = \sum_{i = 0}^\infty \frac{1}{i!} x^i [2 | i] \)，那么答案就是 \( A^k(x)[x^n] \)。发现可以变通奇偶性，所以 \(A(x) = \frac{e^x + e^{-x}}{2}\)，然后试着二项式展开：
标签归档： 数学
「LibreOJ NOI Round #2」不等关系 – 题解
主要思路
这题好神仙啊。
首先介绍一个暴力的套路（虽然跟正解没关系，但我觉得碰上很多比赛的时候会用上）：我们设置 \(f[i][j]\) 当前为前 \(i\) 个数中第 \(j\) 小的贡献，那么有
\[ f[i][j] = \begin{cases} \sum_{k = 1}^{i – 1} f[i – 1][k] (s_{i – 1} = <) \\ \sum_{k = i}^{j} f[i – 1][k] (s_{i – 1} = >) \end{cases} \]
Yali 模拟赛 #1 – 解题报告
A – 神奇的位运算
想了半天，最后一看是离线来维护，直接吐血。
首先大概能想到用本质不同的异或和与区间异或和进行异或得到答案。因为这样可以把出现次数为奇数次的给过滤掉并得到最终的答案。考虑如何得到本质不同的区间异或和，一种方式是使用主席树进行维护，另一种方式是进行离线维护。我们可以在树状数组中维护本质不同的前缀异或：我们把每个数往尽可能近的地方塞，这个时候就需要用 map 来判断要不要移动。
快速沃尔什变换｜FWT
快速入门
记公式：
Or operation:
arr[k + step] += opt * arr[k]
And operation:
arr[k] += opt * arr[k + step]
Xor operation:
A = arr[k], B = arr[k + step]
arr[k] = A + B, arr[k + step] = A - B
with inverse-operation, the inv2 is needed:
arr[k] /= 2, arr[k + step] /= 2;
UOJ#275:「清华集训2016」组合数问题 – 题解
主要思路
好您妈神仙啊。
考虑用 Lucas 把组合数分解：
\[ {n \choose m} = {n / k \choose m / k} {n \mod k \choose m \mod k} \]
Yali CSP-S 2019 模拟赛 – 算式树
思路
这道题思路很妙。
发现算子只有\(+, -, \times\)，所以路径上的解可以表示成线性组合：\(ax + b\)。我们记录从根到下、从下到根的线性组合前缀，然后我们考虑来利用前缀进行分割：就是树上差分的那种套路。
我们先考虑父亲边为：
- 加法/减法：从根向下直接加上即可，从下到根也直接加上就好，但是需要乘上之前的\(a\)。
- 乘法：从根到下需要把\(a\)乘上，\(b\)加上乘积；但是如果是向上合并的话，就可以直接把\(a\)乘上就行：因为反向而言只对乘项有关。
大概这样合并：
void dfs(int u)
{
dep[u] = dep[fa[0][u]] + 1;
for (int i = head[u]; i != -1; i = edges[i].nxt)
if (edges[i].to != fa[0][u])
{
fa[0][edges[i].to] = u, upweight[edges[i].to] = edges[i].weight;
trs_up[edges[i].to] = trs_up[u], trs_down[edges[i].to] = trs_down[u];
if (edges[i].weight == 1)
{
trs_down[edges[i].to].b = (trs_down[edges[i].to].b + vi[edges[i].to]) % mod;
trs_up[edges[i].to].b = (1LL * trs_up[u].a * vi[u] + trs_up[u].b) % mod;
}
else if (edges[i].weight == 2)
{
trs_down[edges[i].to].b = (trs_down[edges[i].to].b - vi[edges[i].to] + mod) % mod;
trs_up[edges[i].to].b = (1LL * trs_up[edges[i].to].b - 1LL * trs_up[u].a * vi[u] % mod + mod) % mod;
}
else
{
trs_down[edges[i].to].a = 1LL * trs_down[u].a * vi[edges[i].to] % mod;
trs_down[edges[i].to].b = 1LL * trs_down[u].b * vi[edges[i].to] % mod;
trs_up[edges[i].to].a = 1LL * trs_up[edges[i].to].a * vi[u] % mod;
}
dfs(edges[i].to);
}
}
如何分裂边呢？我们只需要抵消掉\(a\)和\(b\)的效果即可，直接用逆元和减法就行了：考虑设置\(ax + b\)为从\(x\)到根的效果，设置\(cx + d\)为\(lca\)到根的效果，那么\(x\)到根的效果为\(ex + f\)，可以列式为：
\[ e(cx + d) + f = ax + b \]
解出来就行了，然后再对\(y\)做差不多的处理就可以解决这道题了。（挺麻烦的，细节还挺多，不如打暴力）