code-trick

发表于 更新于 分类于 阅读次数：

总结一些 code-trick ，这种东西看看别人的代码，有时能够大开眼界。

NTT/FFT

预处理原根

普通 NTT 每次长度改变都需要调用若干次快速幂来计算原根，差不多长这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void DFT(ll *a, int n) {
	// ...
	for(int m = 1; m < n; m <<= 1) {
		ll Gn = power(3, (mod - 1) / (m << 1));
		for(int i = 0; i < n; i += m) {
			ll G = 1;
			for(int k = i; k < i + m; k ++) {
				ll a0 = a[k], a1 = a[k + m] * G;
				a[k] = (a0 + a1) % mod;
				a[k + m] = (a0 + mod - a1) % mod;
				(G *= Gn) %= mod;
			}
		}
	}
}

事实上可以预处理数组 \(G\) 满足当前枚举的 \((m, k, i)\) 需要用到的原根就是 G[m + k - i] ，
每一层需要 \(m\) 个位置，由于每次 \(m\) 倍长，\(O(n)\) 的空间是能存下的。
而且只需要递推 \(m\) 最大的一层，剩下的由于 \(W_m^k = W_{2m}^{2k}\) ，可以知道 G[m + k] = G[m * 2 + k * 2] 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void init() {
	ll g = power(3, (mod - 1) / maxl);
	G[maxl >> 1] = 1;
	for(int i = (maxl >> 1) + 1; i <= maxl; i ++)
		G[i] = G[i - 1] * g % mod;
	for(int i = (maxl >> 1) - 1; i; i --)
		G[i] = G[i << 1];
}

void DFT(ll *a, int n) {
	// ...
	for(int m = 1; m < n; m <<= 1)
		for(int i = 0; i < n; i += m << 1)
			for(int k = i; k < i + m; k ++) {
				ll a0 = a[k], a1 = a[k + m] * G[m + k - i] % mod;
				a[k] = (a0 + a1) % mod;
				a[k + m] = (a0 + mod - a1) % mod;
			}
}

同样的道理 rev 数组也是能预处理的。

逆变换

逆变换实际只要 reverse 一遍做正变换然后除以 \(n\) 即可。

除以 \(n\) 往往需要计算逆元，但是由于 \(n\) 是二的整次幂，且 NTT 模数必须是 \(2^k * s + 1\) ，
除了预处理以外 \(n\) 的逆元有更好的 \(O(1)\) 计算方法，因为找到一个满足 \(nx \equiv -1\) 的数 \(x\) 是很容易的。

1
2
3
4
5
6
7
void IDFT(ll *a, int n) {
	std::reverse(a + 1, a + n);
	DFT(a, n);
	int invn = mod - (mod - 1) / n;
	for(int i = 0; i < n; i ++)
		(a[i] *= invn) %= mod;
}

模数

当模数比较小以至于 \(p^2\log n\) 不会爆 long long 或者 unsigned long long 的时候，NTT 的蝴蝶变换可以在最后取模，实测会快很多。

比如一般 167772161 就是这样一个模数。另外 998244353 在长度不超过 \(2^{18}\) 可以用 unsigned long long 存来卡这个取模。

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void __d(ll &x) { if(x < 0) x += mod; }

inline void DFT(ll *a, int n) {
	for(int m = 1; m < n; m <<= 1)
		for(int i = 0; i < n; i += m << 1)
			for(int k = i; k < i + m; k ++) {
				ll a0 = a[k], a1 = a[k + m] * G[m + k - i] % mod;
				a[k] = a0 + a1;
				a[k + m] = a0 - a1;
			}

	for (int i = 0; i < n; ++i) __d(a[i] %= mod);
}

FFT 两次变一次 1

这是 myy 提出的一个优秀的 FFT trick ，能够一次 FFT 处理两个多项式，但缺点是精度会进一步降低。

前提是两个多项式的系数在 FFT 前虚部为 0 ，这个条件在 DFT 中往往是能满足的。

例如要给两个多项式 \(A, B\) 做 FFT ，考虑构造两个多项式：

\[P(x) = A(x) + i B(x)\] \[Q(x) = A(x) - i B(x)\]

那么由于 \(A, B\) 的虚部都为 0 ，\(P, Q\) 的每一项系数都互为共轭，同样 \(FFT(P), FFT(Q)\) 的每一项系数都互为共轭。
那么只需对 \(P\) 做一次 FFT ，就可以通过共轭 \(O(n)\) 求出 \(FFT(Q)\) 的系数。
然后通过 \(FFT(P), FFT(Q)\) 求 \(FFT(A), FFT(B)\) 就是解上面的二元一次方程组，也是可以 \(O(n)\) 做到的。

FFT 两次变一次 2

这是 myy 提出的一个优秀的 FFT trick ，能够一次 FFT 处理两个多项式，但缺点是精度会进一步降低。

前提是两个多项式的系数在 FFT 后虚部为 0 ，这个条件在 IDFT 中往往是能满足的。

例如要给两个多项式 \(A, B\) 做 FFT ，构造多项式 \(P\) 满足：

\[P(x) = A(x) + i B(x)\]

求出 \(FFT(P)\) ，同样有 \(FFT(P)(x) = FFT(A)(x) + i FFT(B)(x)\) ，而 \(FFT(A), FFT(B)\) 系数的虚部都是 0 。

那么 \(FFT(P)\) 的实部就是 \(FFT(A)\) ，虚部就是 \(FFT(B)\) 。

线段树

同时需要记录区间最大值 max 和区间取 min 标记 tag 时，直接用 max 代替掉 tag 即可。
比如区间取 min 和区间求和的吉司机线段树（segment tree beats）。

STL

将数组降序排序不需要写 cmp ，只需要 std::sort(a, a + n, std::greater<int>()); 即可。
std::greater 包含在头文件 functional 中，这同样适用于结构体排序。
另外如果要用小根堆，可以使用 std::priority_queue<int, std::vector<int>, std::greater<int> > 。
与 std::greater 对应的是 std::less 。

std::set 插入后返回的迭代器可以直接获取：auto iter = set.insert(x).second 。

std::valarray 可以很快速并且很方便地进行许多批量操作，使用用来存方程组之类的东西。

位运算

预处理 bitcount

1
2
for (int i = 1; i <= n; i ++)
	bitcount[i] = bitcount[i & (i - 1)] + 1;

预处理 highbit

1
2
for (int i = 2; i <= n; i ++)
	highbit[i] = highbit[i >> 1] + 1;

语法

利用语法糖可以写出一些骚操作，比如下面这个快读模板：

1
2
3
4
5
6
7
8
9
10
11
12
typedef long long ll;
struct Inputer {
	static char buffer[64 * 1024 * 1024], *p;
	inline operator int () { return int(strtol(p, &p, 10)); }
	inline operator ll () { return strtoll(p, &p, 10); }
	template<class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator ()(a...); }
	Inputer() { fread(buffer, 1, sizeof buffer, stdin); }
} read;
char *Inputer::p = Inputer::buffer;
char Inputer::buffer[] = {};

它有多种用法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void foo (int);

int main () {
	int a = read;

	ll b = read;

	int c;
	read(c);

	int d;
	ll e, f;
	read(d, e, f);

	foo(read);

	read.operator int();

	ll g = int(read);
}

并且可以自定义各种类型的读入，编译器能够根据类型正确调用对应的输入函数（在没有歧义的前提下），或者自己在调用时直接给出类型。

ps: 这个 trick 不是学的，是我自己原创的，也是我一直在使用的快读模板。:)

事实上由于大多时候不需要快读，我平时用的输入模板是这样子的（用法完全相同）：

1
2
3
4
5
6
7
8
typedef long long ll;
struct {
	inline operator int () { int x; return scanf("%d", &x), x; }
	inline operator ll () { ll x; return scanf("%lld", &x), x; }
	template<class T> inline void operator () (T &x) { x = *this; }
	template<class T, class ...A> inline void operator () (T &x, A &...a)
	{ x = *this; this -> operator () (a...); }
} read;

取模优化

众所周知取模很慢，于是有了各种各样的取模优化。

当 \(P\) 以内的数做减法时，可以判断结果是不是负数，如果是负数就加上 \(P\) ，但是众所周知使用 if 分支结构可能会带来一定的惩罚，于是可以用到一个 trick ，对于一个 int 存储的数 x ，它为负数时有 x >> 31 == -1 ，非负时有 x >> 31 = 0 ，于是可以这样写（加法同理），实测在不开启编译优化时效果显著，开启优化时没有啥用：

1
2
void __d (int &x) { x += (x >> 31) & P; }
void __a (int &x) { x += -P + (x >> 31) & P; }

当要算多个 \(P^2\) 内的数的和时，常规做法每次加都要取模，但事实上可以用 long long 存储，只在最后一次取模，优化效果显著：

1
2
3
4
ll sum = 0;
for (int i = 0; i < n; i ++)
	__a(sum += 1ll * a[i] * b[i]);
sum %= P;

更高级的取模优化可以参加论文哥的板子，或者 min25 的相关文章。

零碎

拓扑排序可以用栈模拟，可以在同时求出拓扑序序列。

但实际上栈是不必要的，一个实时的拓扑序序列可以代替掉栈。

1
2
3
4
5
6
for (int i = 1; i <= tot; i ++) {
	int u = topsort[i];
	for (int v : G[u])
		if ((-- deg[v]) == 0)
			topsort[++ tot] = v;
}