好像是第 114514 次重构板子了。
现在的方案是结合自己的码风和习惯，全面贺 EI（bushi
已经完成的：
- DIT-DIF。
- 常用的牛顿迭代。
还需要的：
转置原理相关操作已完成。熟练运用 \(\Theta(n\log^2n/\log\log n)\) 的在线卷积已完成。- 研究一下抄到的 NTT 板子。
然后引用一下 Karry5307 提供的表：
\(p=r\times 2^k+1\) 的较小的 \(2^k\) 次单位根：
\(r\) \(k\) \(p\) 较小单位根（\(\leq 100\)） 最小单位根 \(479\) \(21\) \(1004535809\) 无 \(4172\) \(119\) \(23\) \(998244353\) \(31,89\) \(31\) \(225\) \(22\) \(943718401\) 无 \(175\) \(7\) \(26\) \(469762049\) \(30,33,54,57,58,67,68,83,96\) \(30\) \(5\) \(25\) \(167772161\) \(17,34,43,68,71,85,86\) \(17\)
先放个代码。
以及用来替换的普通 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
29void init(int l) {
L = l;
root.resize((1 << L) + 1);
int n = 1 << L, *w = root.data();
int w1 = mpow(G, (mod - 1) >> L);
w[n / 2] = 1;
for (int i = (n / 2) + 1; i <= n; ++i)
w[i] = (ll)w[i - 1] * w1 % mod;
for (int i = (n / 2) - 1; i; --i)
w[i] = w[i << 1];
}
void DIF(int *a, int l) {
int n = 1 << l;
for (int len = n >> 1; len; len >>= 1)
for (int *j = a; j != a + n; j += len << 1)
for (int *k = j, *o = root.data() + len; k != j + len; ++k, ++o) {
int r = norm(*k + k[len]);
k[len] = (ll)*o * (*k - k[len] + mod) % mod, *k = r;
}
}
void DIT(int *a, int l) {
int n = 1 << l;
for (int len = 1; len < n; len <<= 1)
for (int *j = a; j != a + n; j += len << 1)
for (int *k = j, *o = root.data() + len; k != j + len; ++k, ++o) {
int r = (ll)*o * k[len] % mod;
k[len] = reduce(*k - r), add(*k, r);
}
}