快速沃尔什变换

新的卷积

卷积的东西都很好玩呀。有时间一定好好学泛函.jpg

前面提到了,离散傅里叶变换的多项式卷积是对于每个 k 获得 i+j=k\sum a_i \times a_j,而在数论中比较多的狄利克雷卷积是对于每个 k 获得 i \times j = k\sum a_i \times a_j。在实际题目中,我们可能会遇到这样的一类卷积:

对于每个 k,获得 i \otimes j = k\sum a_i \times a_j。其中 \otimes 是任意按位逻辑运算,如 \&, |, \oplus 等。

继续阅读“快速沃尔什变换”

大衍求一术

int dyqys(int a, int n)
{
    int k[3], r[3], q;
    k[1] = 0, k[2] = 1;
    r[1] = n, r[2] = a;

    while (r[2] != 1)
    {
        r[0] = r[1], r[1] = r[2];
        k[0] = k[1], k[1] = k[2];
        if (r[1] == 0) return -1;
        q = r[0] / r[1];
        r[2] = r[0] % r[1];
        k[2] = (k[0] - q * k[1]) % n;
        if (k[2] < 0) k[2] += n;
    }

    return k[2];
}