ACM模版

描述

题解

这么黑科技的一个题，夹克老师竟然将他放在了四级，后来夹克老师及时改成了六级，让我内心少了些微的冲击。

FWT ……快速沃尔什变化，这个题我真的不会写，但是还好前天网上有大神放了题解，强行理解了一波，学了一下 FWT 的入门。

根据题意，只有在两个城市的二进制位差别为其中一位值不同，其他位都相同时才能连接在一起，这个很符合 FWT 的应用场景， FWT 是为了解决一类卷积问题的方法，而这一类问题刚好就是二进制位之间的运算关系的问题，具体的可以在参考部分点进去看看某大神的讲解，十分好，好像需要 VPN 才能访问。

而后因为 t 很大了，所以需要用到快速幂，这个部分不难理解。

原谅垃圾的我最开始看到 FWT 以为是树状数组的简称，英语早已超鬼啊~~~

代码

#include <cstdio>

using namespace std;

typedef long long ll;

const int MAXN = 2330010;
const int MOD = 1e9 + 7;
const int INV_2 = 5e8 + 4;  // 2的逆元

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

template <class T>
inline void print_d(T x)
{
    if (x > 9)
    {
        print_d(x / 10);
    }
    putchar(x % 10 + '0');
}

int N;
int a[MAXN], b[MAXN];

inline void FWT(int c[], int tf_utf)    // tf_utf 1:tf; 0:utf
{
    for (int i = 1; i < N; i <<= 1)
    {
        int tmp = i << 1;
        for (int j = 0; j < N; j += tmp)
        {
            for (int k = 0; k < i; k++)
            {
                int x = c[j + k], y = c[j + k + i];
                if (tf_utf)
                {
                    c[j + k] = x + y;
                    if (c[j + k] >= MOD)
                    {
                        c[j + k] -= MOD;
                    }
                    c[j + k + i] = x - y;
                    if (c[j + k + i] < 0)
                    {
                        c[j + k + i] += MOD;
                    }
                }
                else
                {
                    c[j + k] = (ll)(x + y) * INV_2 % MOD;
                    c[j + k + i] = (ll)(x - y + MOD) * INV_2 % MOD;
                }
            }
        }
    }
}

int QPow(int a, int k)
{
    int ret = 1;
    while (k)
    {
        if (k & 1)
        {
            ret = (ll)ret * a % MOD;
        }
        a = (ll)a * a % MOD;
        k >>= 1;
    }

    return ret;
}

int n, t;

int main()
{
    scan_d(n), scan_d(t);

    N = 1 << n;
    for (int i = 0; i < N; i++)
    {
        scan_d(a[i]);
    }

    b[0] = 1;
    for (int i = 0; i < n; i++)
    {
        b[1 << i] = 1;
    }

    FWT(a, 1);
    FWT(b, 1);

    for (int i = 0; i < N; i++)
    {
        a[i] = (ll)a[i] * QPow(b[i], t) % MOD;
    }

    FWT(a, 0);

    for (int i = 0; i < N; i++)
    {
        print_d((a[i] + MOD) % MOD);
        putchar(' ');
    }
    putchar(10);

    return 0;
}

参考

《Fast Walsh-Hadamard Transform》 p.s. 名字虽然是英文的，但是内容是中文的，可以放心观看。