常用技巧总结

紊莫 · 2023-12-12 16:14:28 · 个人记录

高精度

使用 Python 的 decimal 库，自带 O(n\log n) 的高精度，可以解决如 P2000 拯救世界的问题。

示例代码：

from decimal import *
getcontext().prec = 800000//设置精度
n = Decimal(input())//唯一一步不同
x = (n+1) * (n+4) + 1;
print((x*x-1)/24)

区间 mex

静态+离线：莫队+值域分块/set。P4137 Rmq Problem / mex

inv2

inv[2] = (P + 1) / 2;

错排问题递推公式

首先随便放一个数字 a，有 n-1 种方案（不能放在自己的位置上），然后分类讨论原本在这个位置上的数正好和 a 调换还是放在别的地方，调换的话方案就是 D(n-2) 否则就是 D(n-1)。

最大点覆盖

点权和最小的点集，使得每条边至少被一个点覆盖。根据经典结论，它等价于点权和减去最大权独立集。

位运算

(x & y) + (x | y) = x + y。

1 ~ n 中和 n 互质的数的和

是 \dfrac{n \varphi(n)}{2}，当 i = 1 的时候是 1。

原理是若 \gcd(n, i) = 1，则有 \gcd(n, n - i) = gcd(n, i) = 1，所以这是成对出现的，每一对的和都是 n。