Kanade's convolution

题目链接

题意

已知$A$和$B$数列，且

$$C_{k} = \sum_{i and j = k} A_{i xor j} \times B_{i or j}.$$

计算 $\sum_{i=0}^{ {2}^{m} - 1} C_{i} \times {1526}^{i}$ $mod$ $998244353.$

思路

设$i$ $or$ $j = x$,$i$ $xor$ $j = y$.那么$i$ $and$ $j = x$ $xor$ $y$.且要求$x$ $and$ $y = y$.

$$C_{k} = \sum_{x} \sum_{y} [x and y == y] \times [x xor y == k] \times B_{x} \times A_{y} \times {2}^{bit(y)}.$$ $$C_{k} = \sum_{x xor y = k} [x and y == y] \times B_{x} \times A_{y} \times {2}^{bit(y)}.$$ $$C_{k} = \sum_{x xor y = k} [bit(x) - bit(y) == bit(k)] \times B_{x} \times A_{y} \times {2}^{bit(y)}.$$

考虑新的函数$F(A, k)_{i}$表示$[bit(i)==k] \times A_{i}$，$F(B, k)_{i}$同理。

则有$FWT[F(C, h)] = \sum_{i=k}^{m} FWT[F(A, i-h)] * FWT[F(B, i) )].$

$$C_{k} = F(C, bit(k))_{k}.$$

#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 ll mod = 998244353;
const ll inv2 = (998244353 + 1) / 2;
/*
void FWT_or(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 < n; ++k)
                if (opt == 1)
                    a[i + j + k] = a[j + k] + a[i + j + k];
                else
                    a[i + j + k] = a[i + j + k] - a[j + k];
}
void FWT_and(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)
                if (opt == 1)
                    a[j + k] = a[j + k] + a[i + j + k];
                else
                    a[j + k] = a[j + k] - a[i + j + k];
}
*/
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) % mod;
                a[i + j + k] = (X - Y + mod) % mod;
                if (opt == -1)
                    a[j + k] = 1ll * a[j + k] * inv2 % mod, a[i + j + k] = 1ll * a[i + j + k] * inv2 % mod;
            }
}

const int N = 1e6 + 5;
ll a[20][N], b[20][N];
ll A[N], B[N];
ll c[20][N];
int main()
{
    int m;
    scanf("%d", &m);
    int up = 1 << m;
    for (int i = 0; i < up; i++)
    {
        scanf("%lld", &A[i]);
        A[i] = A[i] * (1 << (__builtin_popcount(i))) % mod;
    }
    for (int i = 0; i < up; i++)
        scanf("%lld", &B[i]);
    for (int i = 0; i < up; i++)
        for (int k = 0; k <= m; k++)
        {
            a[k][i] = (__builtin_popcount(i) == k)? A[i] : 0;
            b[k][i] = (__builtin_popcount(i) == k)? B[i] : 0;
        }
    for (int k = 0; k <= m; k++)
    {
        FWT_xor(a[k], up, 1);
        FWT_xor(b[k], up, 1);
    }
    for (int h = 0; h <= m; h++)
        for (int k = 0; k <= h; k++)
        {
            for (int i = 0; i < up; i++)
                c[k][i] = (c[k][i] + a[h - k][i] * b[h][i] % mod) % mod;
        }
    for (int i = 0; i <= m; i++)
        FWT_xor(c[i], up, -1);
    ll ans = 0;
    ll base = 1;
    for (int i = 0; i < up; i++)
    {
        ans = ans + base * c[__builtin_popcount(i)][i] % mod;
        ans %= mod;
        base = base * 1526 % mod;
    }
    printf("%lld\n", ans);
    return 0;
}