日记

神秘 jmr 模拟赛。

睡得十分香甜。

Jzzhu and Numbers# Link to

我们考虑 $dp_i$ 表示选出 $dp_i$ 个数使得他们与起来是 $i$ 的超集。我们用 SOSdp 求解。

1
2
3

for (int i = 0; i < 20; i++)
    for (int s = 0; s < 1 << 20; s++)
        dp[s] = (dp[s] + dp[s | (1 << i)]) % mod

注意是先枚举 $i$ 再枚举 $s$。那么答案就是 $\sum (-1)^{\operatorname{popcount}(i)} \times 2^{dp_i}$。

GCD Counting# Link to

对于一个 $g$，我们不好直接算 $\gcd$ 恰好是 $g$ 的方案数，我们可以算 $\gcd$ 是 $g$ 的倍数的方案数。我们记录下每个 $i$ 它的倍数有哪几个，然后拿并查集维护，如果两个都是 $i$ 的倍数且之间有边就 merge。然后看看每个点所属集合的 $size$，将 $\frac{size(size + 1)}{2}$ 加到 $f_i$ 里。

但是这个是 $\gcd$ 是 $i$ 的倍数的情况。显然我们需要容斥。我们从大到小枚举 $i$，并枚举 $i$ 的倍数 $j$，将 $f_i$ 减掉 $f_j$ 就是了。

但是这个沟槽的题目还要卡空间，只有 $f$ 能开 long long。

逆序对# Link to

我们考虑每个位置的对逆序对数量的贡献。我们发现，第 $i$ 个位置，前面最多只有 $i - 1$ 个比它大，设它的贡献是 $a_i$，那么一定有 $a_i \in [0,i)$。题意就变成了 $\sum_{i = 1}^{n}a_i = k$，但是 $a_i \in [0,i)$。

我们发现 $a_i \ge 0$ 这个限制很好做，直接插板法。但是这个 $a_i < i$ 很烦人。我们考虑钦定 $i$ 个 $a_i$ 是不符合要求的，也就是说这些 $a_i = i + a'_i$。那些合法的就是 $a_i = a'_i$。那么原式就变成了 $\sum_{i = 1}^{n}a'_i = k - \text{一坨东西}$。显然，这 $\text{一坨东西}$ 就是不合法的数的 $i$ 之和，从柿子也可以看出，我们只关心 $i$ 的和。

考虑 dp。设 $dp_{i,j}$ 表示钦定有 $i$ 个不合法，那 $\text{一坨东西} = j$。考虑转移：$dp_{i,j} = dp_{i - 1,j - i} + dp_{i,j - i} - dp_{i - 1,j - (n + 1)}$。分别表示加一项；不加一项，整体 $+1$；不合法的情况。

何谓“不合法”
我们 $j$ 表示那些不合法的 $i$ 之和。显然不会有 $i > n$。而我们每次至多 $+1$，所以只用减 $n + 1$。

答案就是 $\sum_{i = 0}\sum_{j = 0}^{k}(-1)^i \times dp_{i,j} \times \binom{k - j + n - 1}{k - j}$，其中 $\binom{k - j + n - 1}{k - j}$ 表示把 $k - j$ 分给 $n$ 个数的方案数。

后日谈 # Link to 后日谈

我的水平已经和 4 年半前的草八牛一样了。