题解 | #Luner Xor#

不需要快速沃尔什变换的题解！小学二年级就能掌握的简单 DP！代码是场上通过里面的最短解！这道题最本质的做法！这篇文章绝对值得你点一个赞！

Luner XOR

题意

给定 元布尔函数在的全部取值，对于每个 数列 ，求该布尔函数与 取值不同的情况个数。

分析

我们设 表示，令 中所有取值为 的数的下标为 （令 为 ）， 中所有取值为 的数的下标为 集合（令 任意取值），所有情况中， 与 取值不同的情况个数。

让我们考虑从 更新到 时，此时若 仍然为 ，那么直接从 过渡即可，否则在 的时候，需要相同的变成不同的，即用 进行贡献。

直接进行 DP ，复杂度即为 ，且相比 FWT，代码显然更为简洁。

代码

#include<bits/stdc++.h>
const int N=22,p=1e9+7;
#define up(a,b,c) for(int a=b;a<=c;++a)
#define dn(a,b,c) for(int a=b;a>=c;--a)
using namespace std;
int n,f[1<<N],g[1<<N],sm,mn;
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n,mn=1<<n+1;
	up(S,0,(1<<n)-1)
	{
		bool r;cin>>r;
		f[S*2]=r,f[S*2+1]=!r;
	}
	up(i,1,n)
	{
		copy(f,f+(1<<n+1),g);
		up(S,0,(1<<n+1)-1)
		{
			bool e=S>>i&1;
			if(!e)f[S]=g[S]+g[S^(1<<i)];
			else f[S]=(1<<i-1)-g[S]+g[S^(1<<i)];
		}
	}
	up(S,0,(1<<n+1)-1)
		sm=(sm+1ll*f[S]*f[S])%p,mn=min(mn,f[S]);
	cout<<sm<<' '<<mn<<'\n';
	return 0;
}

易错点

推式子时更新贡献的方式要仔细想清楚，做到无误，最好先在笔上写出来。