Parity of Tuples

题目链接

题意

有$n$个$m$元组，定义$count(x)$为满足所有$a_{i, j} and x$的结果有奇数个1的元组的个数。现在计算$\otimes_{x=0}^{ {2}^{k}-1} (count(x) \times {3}^{x} mod ({10}^{9}+7))$.

思路

FWT

首先了解一下快速沃尔什变换在异或上的意义。
我们现在都知道FWT怎么用。

$$FWT(A)_{i} = \sum_{j} f_{i, j} a_{i}.$$

其中$f_{i, j}$是一个线性变换。

$$FWT(A)_{i} \times FWT(B)_{i} = \sum_{x} f_{i, x} a_{x} \sum_{y} f_{i, y} b_{y}$$ $$= \sum_{x} \sum_{y} f_{i, x} f_{i, y} a_{x} b_{y}$$ $$= \sum_{t} \sum_{x, y, x \otimes y = t} f_{i, x} f_{i, y} a_{x} b_{y}$$ $$= \sum_{t} \sum_{x, y, x \otimes y = t} f_{i, x} f_{i, y} c_{t}$$ $$= \sum_{t} f_{i, t} c_{t}.$$

所以有我们去构造一个线性变换满足：

$$f_{i, x} f_{i, y} = f_{i, x \otimes y}.$$

我们观察这样一个式子：

$${(-1)}^{|i and j|}$$

其中$|x|$表示二进制$x$中1的个数奇偶性。
这个式子恰好满足我们要的线性变换。

$$|i and k| \otimes |j and k| = |(j \otimes i) and k|.$$

言归正传

我们继续观察怎样计算$count(x)$。
我们可以这样写

$$count(x) = \frac{ \sum_{i = 1}^{n} \prod_{j = 1}^{m} (1 - {(-1)}^{|a_{i, j} and x|})}{2^m}$$

我们去讨论分子部分。

$$\prod_{j = 1}^{m} (1-{(-1)}^{|a_{i, j} and x|})$$ $$= 1 - \sum_{j = 1}^{m} {(-1)}^{|a_{i, j} and x|} + \sum_{j, k, j \neq k}^{m}...$$

对于$-1$来说，我们发现

$${(-1)}^{i+j} = {(-1)}^{i \otimes j}.$$

所以上式可以被我们变成FWT：

$$count(x) = \frac{ \sum_{i=1}^{n} \sum_{j=0}^{2^m-1} {(-1)}^{popcount(j)} FWT(f_{i})_{x}}{2^m}.$$

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
const int N = 20;
ll f[(1 << 20) + 5];
const ll mod = 1e9 + 7;
int a[15];
int n, m, k;
ll Pow(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
 
void dfs(int p, int now, int q)
{
    if (p > m)
    {
        f[now] += q;
        return;
    }
    dfs(p + 1, now ^ a[p], -q);
    dfs(p + 1, now, q);
}
/*
void fwt(ll a[],int m){
    int n = __builtin_ctz(m);
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(j&(1<<i)) {
                int l = a[j^(1<<i)];
                int r = a[j];
                a[j^(1<<i)] = (l+r)%mod;
                a[j] = (l-r+mod)%mod;
            }
        }
    }
}
*/
void FWT_xor(ll *a, int n, int opt)
{
    for (int i = 1; i < n; i <<= 1)
        for (int p = i << 1, j = 0; j < n; j += p)
            for (int k = 0; k < i; ++k)
            {
                ll X = a[j + k], Y = a[i + j + k];
                a[j + k] = X + Y;
                a[i + j + k] = X - Y;
                if (opt == -1)
                    a[j + k] = 1ll * a[j + k] / 2, a[i + j + k] = 1ll * a[i + j + k] / 2;
            }
}
 
int main()
{
    while (scanf("%d%d%d", &n, &m, &k)!= EOF)
    {
        for (int i = 0 ; i <= (1 << k) - 1; i++)
            f[i] = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
                scanf("%d", &a[j]);
            dfs(1, 0, 1);
        }
        FWT_xor(f, 1 << k, 1);
        ll ans = 0, base = 1, inv = Pow(1 << m, mod - 2);
        for (int i = 0; i < (1 << k); i++)
        {
            ans = ans ^ (inv * base % mod * f[i] % mod);
            base = base * 3ll % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}