RT，为了方便自己全文背诵板子特开此文。

代码有很多很冗余的地方，主要是因为 @Rui_R 神仙是这么说的：

$\mathrm{NTT}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void NTT(poly &arr, int typ)
{
	for (int i = 0; i < LIM; i++)
	{
		if (R[i] > i)
		{
			swap(arr[i], arr[R[i]]);
		}
	}
	for (int mid = 1; mid < LIM; mid <<= 1)
	{
		int W = quick_pow(typ == 1 ? org : lev, (MOD - 1) / (mid << 1));
		for (int j = 0; j < LIM; j += (mid << 1))
		{
			int w = 1;
			for (int i = 0; i < mid; i++)
			{
				int x = arr[i + j], y = (arr[i + j + mid] * w) % MOD;
				arr[i + j] = (x + y) % MOD;
				arr[i + j + mid] = (x - y + MOD) % MOD;
				w = w * W % MOD;
			}
		}
	}
	if (typ == -1)
	{
		int inv = quick_pow(LIM, MOD - 2);
		for (int i = 0; i < LIM; i++)
		{
			arr[i] = arr[i] * inv % MOD;
		}
	}
}

$\mathrm{init}$ （取按位反转）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void init(int len)
{
	L = 0;
	LIM = 1;
	while (LIM <= len)
	{
		L++;
		LIM <<= 1LL;
	}
	for (int i = 0; i < LIM; i++)
	{
		R[i] = (R[i >> 1] >> 1) | ((i & 1) << (L - 1));
	}
}

$\mathrm{mul}$ （卷）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void mul(poly &a, int lena, poly &b, int lenb, poly &kk)
{
	init(lena + lenb);
	for (int i = lena; i < LIM; i++)
	{
		a[i] = 0;
	}
	for (int i = lenb; i < LIM; i++)
	{
		b[i] = 0;
	}
	NTT(a, 1);
	NTT(b, 1);
	for (int i = 0; i < LIM; i++)
	{
		kk[i] = (a[i] * b[i]) % MOD;
	}
	NTT(kk, -1);
	for (int i = lena + lenb - 1; i < LIM; i++)
	{
		kk[i] = 0;
	}
}

以上三个是最基础的，不另加公式。

$\mathrm{inv}$ （取逆元）

设：

有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
namespace INV
{
	poly G0, F;
}
void get_inv(poly &a, int len, poly &kk)
{
	if (len == 1)
	{
		kk[0] = quick_pow(a[0], MOD - 2);
		return;
	}
	INV::G0.clear();
	get_inv(a, (len + 1) >> 1LL, INV::G0);

	init(len + len);
	for (int i = 0; i < len; i++)
	{
		INV::F[i] = a[i];
	}
	for (int i = len; i < LIM; i++)
	{
		INV::F[i] = 0;
	}
    
    
	NTT(INV::F, 1);
	NTT(INV::G0, 1);
	for (int i = 0; i < LIM; i++)
	{
		kk[i] = (INV::G0[i] * (2 - (INV::G0[i] * INV::F[i]) % MOD)) % MOD;
	}
	NTT(kk, -1);
    
	for (int i = len; i < LIM; i++)
	{
		kk[i] = 0;
	}
}

$\mathrm{ln}$

不会求导，全文背诵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
namespace LN
{
	poly dev_A, inv_A, B;
}
void get_dev(poly &a, int len, poly &kk)
{
	for (int i = 1; i < len; i++)
	{
		kk[i - 1] = a[i] * i % MOD;
	}
	kk[len - 1] = 0;
}
void get_idev(poly &a, int len, poly &kk)
{
	for (int i = 1; i < len; i++)
	{
		kk[i] = a[i - 1] * quick_pow(i, MOD - 2) % MOD;
	}
	kk[0] = 0;
}
void get_ln(poly &a, int len, poly &kk)
{
	kk.clear();
    
	LN::dev_A.clear();
	get_dev(a, len, LN::dev_A);
    
	LN::inv_A.clear();
	get_inv(a, len, LN::inv_A);
    
	LN::B.clear();
	mul(LN::dev_A, len, LN::inv_A, len, LN::B);
    
	get_idev(LN::B, len, kk);
}

$\mathrm{exp}$

不会求导，全文背诵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
namespace EXP
{
	poly G0, lnG0, F;
}
void get_exp(poly &a, int len, poly &kk)
{
	if (len == 1)
	{
		kk[0] = 1;
		return;
	}

	/*获取G0*/
	EXP::G0.clear();
	get_exp(a, len + 1 >> 1, EXP::G0);

	/*获取ln(G0)*/
	get_ln(EXP::G0, len, EXP::lnG0);

	init(len + len);

	/*获取F*/
	EXP::F.clear();
	for (int i = 0; i < len; i++)
	{
		EXP::F[i] = a[i];
	}
	for (int i = len; i < LIM; i++)
	{
		EXP::F[i] = 0;
	}

	NTT(EXP::G0, 1);
	NTT(EXP::lnG0, 1);
	NTT(EXP::F, 1);
	for (int i = 0; i < LIM; i++)
	{
		kk[i] = EXP::G0[i] * ((1 - EXP::lnG0[i] + EXP::F[i] + MOD) % MOD) % MOD;
	}

	NTT(kk, -1);
	for (int i = len; i < LIM; i++)
	{
		kk[i] = 0;
	}
    
	EXP::lnG0.clear();
}

$\text{sqrt}$

不会任意零次项 $\text{sqrt}$ ，先整理零次项为 $1$ 的 $\text{sqrt}$ 。

设：

有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
namespace SQRT
{
	poly G, F, A, invG;
}
void get_sqrt(poly &a, int len, poly &kk)
{
	if (len == 1)
	{
		kk[0] = 1;
		return;
	}
	SQRT::G.clear();
	get_sqrt(a, len + 1 >> 1, SQRT::G);

	SQRT::invG.clear();
	get_inv(SQRT::G, len, SQRT::invG);

	SQRT::A.clear();
	init(len + len);
	for (int i = 0; i < len; i++)
	{
		SQRT::A[i] = a[i];
	}
	for (int i = len; i < LIM; i++)
	{
		SQRT::A[i] = 0;
	}

	NTT(SQRT::G, 1);
	NTT(SQRT::invG, 1);
	NTT(SQRT::A, 1);
	int inv2 = quick_pow(2, MOD - 2);
	for (int i = 0; i < LIM; i++)
	{
		kk[i] = ((SQRT::G[i] + SQRT::A[i] * SQRT::invG[i] % MOD) % MOD * inv2) % MOD;
	}
	NTT(kk, -1);
	for (int i = len; i < LIM; i++)
	{
		kk[i] = 0;
	}
}

最后更新： 2021年04月22日 09:56

原始链接： https://quest233.github.io/2021/04/17/%E5%A4%9A%E9%A1%B9%E5%BC%8F%E5%85%AC%E5%BC%8F%E6%9F%A5%E8%AF%A2-%E6%9D%BF%E5%AD%90%E6%95%B4%E7%90%86/