BZOJ 4589 Hard Nim（FWT加速DP）

题目链接  Hard Nim

设$f[i][j]$表示前$i$个数结束后异或和为$j$的方案数

那么$f[i][j] = f[i-1][j$ $\hat{}$ $k]$，满足$k$为不大于$m$的质数。

这个$DP$太暴力了。让我们冷静分析。

设不大于m的质数从小到大分别为$c_{1}$, $c_{2}$, ..., $c_{k}$

$f[i][j] = ∑f[i-1][j$ $\hat{}$ $c[k]]$， 我们令$g[c[i]]$为$1$，其余为$0$。

$f[i][j] = ∑f[i-1][j$ $\hat{}$ $k] * g[k]$

我们发现后边其实就是一个异或卷积的形式。

于是就可以$FWT$了。

但是左边那一维还是巨大……

我们可以发现这个多项式乘法是满足结合律的

于是在做逆变换之前的那个乘法的时候直接快速幂即可。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define MP		make_pair

#define fi		first

#define se		second

typedef long long LL;

const LL mod = 1e9 + 7;

const LL rev = (mod + 1) >> 1;

int n, m;

int l;

int tot = 0;

int p[1 << 20];

LL a[1 << 20], b[1 << 20], g[1 << 20];

void pre(){

	rep(i, 2, 5e4){

		if (!g[i]) p[++tot] = i;

		for (int j = 1; j <= tot && i * p[j] <= 5e4; ++j){

			g[i * p[j]] = 1;

			if (i % p[j] == 0) break;

		}

	}

}

void FWT(LL *a, int n){

	for (int d = 1; d < n; d <<= 1)

		for (int m = d << 1, i = 0; i < n; i += m)

			for (int j = 0; j < d; j++){

				LL x = a[i + j], y = a[i + j + d];

				a[i + j] = (x + y) % mod, a[i + j + d] = (x - y + mod) % mod;

			}

}

void UFWT(LL *a, int n){

	for (int d = 1; d < n; d <<= 1)

		for (int m = d << 1, i = 0; i < n; i += m)

			for (int j = 0; j < d; j++){

				LL x = a[i + j], y = a[i + j + d];

				a[i + j] = 1LL * (x + y) * rev % mod, a[i + j + d] = (1LL * (x - y) * rev % mod + mod) % mod;

			}

}

void solve(LL *a, LL *b, int n, int p){

	a[0] = 1;

	FWT(a, n);

	FWT(b, n);

	while (p){

		if (p & 1){

			rep(i, 0, n - 1) (a[i] *= b[i]) %= mod;

		}

		rep(i, 0, n - 1) (b[i] *= b[i]) %= mod;

		p >>= 1;

	}

	UFWT(a, n);

}

int main(){

	pre();

	while (~scanf("%d%d", &n, &m)){

		for (l = 1; l <= m; l <<= 1){;}

		memset(a, 0, sizeof a);

		memset(b, 0, sizeof b);

		for (int i = 1; i <= tot && p[i] <= m; ++i){

			b[p[i]] = 1;

		}

		solve(a, b, l, n);

		printf("%lld\n", a[0]);

	}

	return 0;

}