HDU 6057 Kanade’s convolution

$C[k]=\sum_{i \text { and } j=k} A[i\ xor\ j] * B[i \text { or } j]$

假设$p = i\ or\ j, t = i\ xor\ j$那么有$t \sub p$，其次显然 此时$i\ and\ j = p-t=p\ xor\ t$

$C[k] = \sum_{p\ xor\ t=k} \alpha(p,t)A[t]B[p]$

$\alpha(p,t)$就是对于一对$p , t$有多少的$i,j$与之对应。

对于每一位来考虑，如果这位$p = 1 , t = 0$那么显然$i , j$在这一位都是$1$

如果$p = 1 , t = 1$那么这一位 可以$i = 1 , j = 0$或者$i = 0 , j = 1$

否则如果$p = 0 , t = 0$这一位 只能都是$0$

所以实际上， 2 的$t$的 1 的个数次方就是$\alpha(p,t)$

所以式子就是$\displaystyle\sum_{p\ xor\ t=k,t\sub p} 2^{cnt(t)}A[t]B[p]$

$p\ xor\ t = k , t \sub p $也就等价于$|p| - |t| = |k| , p\ xor\ t = k$这个可以枚举$|p|,|t|$来做，和子集卷积一样，复杂度$n^22^n$

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
#define MAXN ( 1 << 20 ) + 12
#define P 998244353
//#define int long long
typedef long long ll;
int n , inv2;
int A[MAXN] , B[MAXN] , I[MAXN];
int Pow( int a , int x ) {
	int res = a , ans = 1;
	while( x ) {
		if( x & 1 ) ans = 1ll * ans * res % P;
		res = 1ll * res * res % P , x >>= 1;
	}
	return ans;
}
namespace fwt {
    
    inline void FWT1(int a[], int len) {
        for (int mid = 2; mid <= len; mid <<= 1) 
            for (int i = 0; i < len; i += mid)
                for (int j = i; j < i + (mid >> 1); j++) 
                    a[j + (mid >> 1)] += a[j] , a[j + (mid >> 1)] %= P;
    }
    
    inline void IFWT1(int a[], int len) {
        for (int mid = 2; mid <= len; mid <<= 1) 
            for (int i = 0; i < len; i += mid)
                for (int j = i; j < i + (mid >> 1); j++) 
                    a[j + (mid >> 1)] -= a[j] , a[j + (mid >> 1)] += P , a[j + (mid >> 1)] %= P;
    }
    
    inline void FWT2(int a[], int len) {
        for (int mid = 2; mid <= len; mid <<= 1) 
            for (int i = 0; i < len; i += mid)
                for (int j = i; j < i + (mid >> 1); j++) 
                    a[j] += a[j + (mid >> 1)];
    }
    
    inline void IFWT2(int a[], int len) {
        for (int mid = 2; mid <= len; mid <<= 1) 
            for (int i = 0; i < len; i += mid)
                for (int j = i; j < i + (mid >> 1); j++) 
                    a[j] -= a[j + (mid >> 1)];
    }
    
    inline void FWT3(int a[], int len) {
        for (int mid = 2; mid <= len; mid <<= 1) 
            for (int i = 0; i < len; i += mid)
                for (int j = i; j < i + (mid >> 1); j++) {
                    ll x = a[j], y = a[j + (mid >> 1)];
                    a[j] = ( x + y ) % P, a[j + (mid >> 1)] = ( x - y + P ) % P ;
                }
    }
    
    inline void IFWT3(int a[], int len) {
        for (int mid = 2; mid <= len; mid <<= 1) 
            for (int i = 0; i < len; i += mid)
                for (int j = i; j < i + (mid >> 1); j++) {
                    ll x = a[j], y = a[j + (mid >> 1)];
                    a[j] = ( 1ll * (x + y) % P * inv2 ) % P, a[j + (mid >> 1)] = ( 1ll * (x - y + P) % P * inv2 ) % P;
                }
    }
}

int a[20][MAXN] , b[20][MAXN] , ans[20][MAXN] , res[MAXN];
signed main() {
	cin >> n;
	inv2 = Pow( 2 , P - 2 );
	int len = ( 1 << n );
	for( int i = 0 ; i < len ; ++ i ) scanf("%d",&A[i]) , a[__builtin_popcount( i )][i] = 1ll * A[i] * ( 1 << ( __builtin_popcount( i ) ) ) % P;
	for( int i = 0 ; i < len ; ++ i ) scanf("%d",&B[i]) , b[__builtin_popcount( i )][i] = B[i];
	for( int i = 0 ; i <= n ; ++ i ) fwt::FWT3( a[i] , len ) , fwt::FWT3( b[i] , len );
	for( int i = 0 ; i <= n ; ++ i ) { 
		for( int j = 0 ; j <= i ; ++ j ) {
			for( int k = 0 ; k < len ; ++ k ) 
				( ans[j][k] += 1ll * a[i - j][k] * b[i][k] % P ) %= P; // , cout << i - j << ' ' << k << ':' << a[i - j][k] << endl;;
		}
	}
	for( int i = 0 ; i <= n ; ++ i ) fwt::IFWT3( ans[i] , len );
	for( int i = 0 ; i < len ; ++ i ) res[i] = ans[__builtin_popcount( i )][i];
	int c = 1 , ret = 0;
	for( int i = 0 ; i < len ; ++ i )
		ret = ( ret + 1ll * res[i] * c % P ) % P , c = 1ll * c * 1526 % P; // , cout << res[i] << endl;
	cout << ret << endl;
}