2019杭电多校二 F. Fantastic Magic Cube (FWT)

大意: 给定$N^3$立方体, 每个单位立方体权值为三个坐标异或, 每次沿坐标轴切一刀, 得分为两半内权值和的乘积, 求切成$n^3$块的最大得分.

可以发现得分与切法无关, 假设每个点权值为$a_i$, 就有$ans=\frac{(\sum a_i)^2-\sum a_i^2}{2}$.

从而转化为求$f_x=\sum\limits_{i=0}^{N-1}\sum\limits_{j=0}^{N-1}\sum\limits_{k=0}^{N-1}[(i\oplus j\oplus k)=x]$

可以用$FWT$很容易求出

#include <iostream>

#include <cstdio>

#define REP(i,a,n) for(int i=a;i<=n;++i)

using namespace std;

typedef long long ll;

const int P = 998244353, INV2 = (P+1)/2;

ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}

const int N = 5e6+10;

int n, m, a[N];

void FWT(int *a, int n, int tp) {

	for (int i=0; (1<<i)<n; ++i) {

		REP(j,0,n-1) if (j>>i&1) {

			int l = a[j^1<<i], r = a[j];

			(a[j^1<<i] += r) %= P;

			a[j] = (l-r)%P;

		}

	}

	if (tp==-1) REP(i,0,n-1) a[i]=(ll)a[i]*inv(n)%P;

}

int main() {

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

		m = 1;

		while (m<n) m *= 2;

		REP(i,0,m-1) a[i]=i<n;

		FWT(a,m,1);

		REP(i,0,m-1) a[i]=(ll)a[i]*a[i]%P*a[i]%P;

		FWT(a,m,-1);

		int f1 = 0, f2 = 0;

		REP(i,0,m-1) {

			f1 = (f1+(ll)i*a[i])%P;

			f2 = (f2+(ll)i*i%P*a[i])%P;

		}

		f1 = (ll)f1*f1%P;

		int ans = (ll)(f1-f2)*INV2%P;

		if (ans<0) ans += P;

		printf("%d\n", ans);

	}

}

巴特西

2019杭电多校二 F. Fantastic Magic Cube (FWT)

最新文章

热门文章