10 进制 FWT 的写法。
题意：给定 $n$ 个整数 $a_1, a_2, \dots, a_n$，求有多少个长度为 $n$ 的序列满足每一个数都从 $n$ 个数里面选（不同位置算不同方案），且 10 进制不进位加法后答案为 $x$。输出 $x\in [0, n - 1]$ 的答案。$n\leq 10 ^ 5, a_i < 10 ^ 5$，答案对 $2 ^ {58}$ 取模。
容易发现我们只需要实现十进制 FWT，直接快速幂再逆变换即可。
首先考虑 FWT 的本质其实是一种高维的 FFT，只不过每一维的长度都是 2。现在考虑如何变为长度为 10。
FFT 的过程需要乘上 $\omega_{10} ^ k$，这个在 $\bmod 2 ^ {58}$ 下似乎是没有整数与之对应，所以我们需要用一个多项式表示，为 $\sum_{i = 0} ^ 9 a_i \omega_{10}^i$。用这个就可以使用 FFT 计算了。
另外，我们还需要考虑另外的问题：最后我们每一维都需要除以一个 10，最后就是除以 $10 ^ 5$，但是 $10 ^ 5$ 在 $\bmod 2 ^ {58}$ 意义下没有逆元。容易发现我们是因为有 $2 ^ 5$ 的缘故，我们可以保留答案 $\bmod 2 ^ {63}$ 意义下的结果，最后直接除，就不需要管逆元了。$5 ^ 5$ 在 $\bmod 2 ^ {63}$ 意义下的逆元可以扩欧计算，所以就可以算了。
最后我们得到的答案是一个多项式，但是由于单位根的性质，表示并不是唯一的。$\omega_{10} ^ 5 = -1, \omega_{10} ^ 9 = -\sum_{i = 0} ^ 8 \omega_{10} ^ i$，用这两个式子我们可以把这个多项式化成 $\sum_{i = 0} ^ 3 a_i\omega_{10}^i$，不能再转换，可以证明盲猜一下这时 $a_0$ 的答案就是最终答案。
实际代码中，我们使用 unsigned long long 计算即可。时间复杂度不好算，不过 unsigned long long 常数小，可以通过。
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| const ULL inv5 = 14757395258967641293ULL;
struct Complex {
ULL a[5];
ULL& operator [](int x) { return a[x]; }
Complex operator +(Complex t) {
return {a[0] + t[0], a[1] + t[1], a[2] + t[2], a[3] + t[3], a[4] + t[4]};
}
Complex operator -(Complex t) {
return {a[0] - t[0], a[1] - t[1], a[2] - t[2], a[3] - t[3], a[4] - t[4]};
}
} f[N];
Complex operator *(Complex a, Complex b)
{
Complex res{};
for (int i = 0; i < 5; ++ i)
for (int j = 0; j < 5; ++ j)
if (i + j >= 5) res[i + j - 5] -= a[i] * b[j];
else res[i + j] += a[i] * b[j];
return res;
}
Complex qpow(Complex a, int k)
{
Complex res{1, 0, 0, 0, 0};
for (; k; k >>= 1, a = a * a)
if (k & 1) res = res * a;
return res;
}
Complex transw(Complex a, int typ)
{
Complex res{};
for (int i = 0; i < 5; ++ i)
{
int to = (i + typ + 10) % 10;
if (to >= 5) res[to - 5] -= a[i];
else res[to] += a[i];
}
return res;
}
void FWT(Complex a[], int typ)
{
for (int mid = 1; mid < N; mid *= 10)
for (int i = 0; i < N; i += mid * 10)
for (int j = 0; j < mid; ++ j)
{
Complex tmp[10];
for (int k = 0; k < 10; ++ k) tmp[k] = a[i + mid * k + j];
for (int k = 0; k < 10; ++ k)
{
Complex &cur = a[i + mid * k + j];
cur = {};
for (int p = 0; p < 10; ++ p) cur = cur + tmp[p];
for (int p = 0; p < 10; ++ p) tmp[p] = transw(tmp[p], typ * p);
}
}
if (typ == 1) return;
ULL inv = inv5 * inv5 * inv5 * inv5 * inv5;
for (int i = 0; i < N; ++ i)
for (int j = 0; j < 5; ++ j) a[i][j] *= inv;
}
|