# [FWT] [DP] uoj ා 310. [unr 񖓿 2] pre dawn chocolate

## Solution

DP is very thoughtful.
Let i set power series fi of chocolate, where fi,0=1,fi,ai=2.
The answer is to convolute these symmetric differences.
The violence is to multiply each FWT.
Walsh transformation of set power series f

fS^=∑T⊆U(−1)|S∩T|fT
So f^i,S is 3 when ゝ S ∩ ai ゝ is even, otherwise − 1.
Consider a new set power series g, which is the sum of fi.
So g^S is some f *, S contributes − 1, some contributes 3.
It can be solved that there are 4 x = G ^ S + n for 3. Then the product of all f ^ *, S is 3 x (− 1)n − X.
The answer is to go back to FWT.
Because no empty set is allowed, it needs to be − 1s....
```#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> Pairs;

const int MOD = 998244353;
const int INV2 = (MOD + 1) / 2;
const int N = 1 << 21;

inline char get(void) {
static char buf, *S = buf, *T = buf;
if (S == T) {
T = (S = buf) + fread(buf, 1, 100000, stdin);
if (S == T) return EOF;
}
return *S++;
}
template<typename T>
static char c; x = 0; int sgn = 0;
for (c = get(); c < '0' || c > '9'; c = get()) if (c == '-') sgn = 1;
for (; c >= '0' && c <= '9'; c = get()) x = x * 10 + c - '0';
if (sgn) x = -x;
}

int n, m, mx, x;
int f[N];

inline void fwt(int* a, int f, int n) {
static int x, y;
for (int i = 1; i < n; i <<= 1)
for (int j = 0; j < n; j += (i << 1))
for (int k = 0; k < i; k++) {
x = a[j + k]; y = a[j + k + i];
a[j + k] = x + y;
a[j + k + i] = x - y;
if (f == -1) {
a[j + k] = (ll)a[j + k] * INV2 % MOD;
a[j + k + i] = (ll)a[j + k + i] * INV2 % MOD;
}
}
}
inline int pow(int a, int b) {
int c = 1;
while (b) {
if (b & 1) c = (ll)c * a % MOD;
b >>= 1; a = (ll)a * a % MOD;
}
return c;
}

int main(void) {
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
for (int i = 1; i <= n; i++) {
f[x] += 2; f += 1;
}
for (m = 1; m <= mx; m <<= 1);
fwt(f, 1, m);
for (int i = 0; i < m; i++) {
int x = (f[i] + n) / 4;
f[i] = (ll)pow(3, x) * pow(MOD - 1, n - x) % MOD;
}
fwt(f, -1, m);
cout << (f - 1 + MOD) % MOD << endl;
return 0;
}
```

Added by rr1024 on Sat, 02 May 2020 04:09:53 +0300