Distance Between Sweethearts

发表于

题目

链接

给定六个不大于 $2000$ 的整数，$UI_{g},UA_{g},UG_{g},UI_{b},UA_{b},UG_{b}$，

求和：$\max{|I_b-I_g|,|A_b-A_g|,|G_b-G_g|}\bigoplus I_b\bigoplus A_b\bigoplus G_b\bigoplus I_g\bigoplus A_g\bigoplus G_g$，且满足：

$I_{g}\in{0,UI_{g}},A_{g}\in{0,UA_{g}},G_{g}\in{0,UG_{g}}$

$I_{b}\in{0,UI_{b}},A_{b}\in{0,UA_{b}},G_{b}\in{0,UG_{b}}$

题解

那个 $\max$ 比较烦人，把那个 $\max$ 扔掉，假设为 $k=\max{x,y,z}$。

要求出 $f_i$，表示在最大值为 $k$ 的情况下 $I_b\bigoplus A_b\bigoplus G_b\bigoplus I_g\bigoplus A_g\bigoplus G_g=i$ 的方案数。

但这样显然没法做，因为我们无法确定最大值是否为 $k$。

为了确定最大值为 $k$，我们可以利用 $[1,k-1]$ 的答案。

也就是把 $f_i$ 的状态改为 ：在最大值 $\leq k$ 的情况下 $I_b\bigoplus A_b\bigoplus G_b\bigoplus I_g\bigoplus A_g\bigoplus G_g=i$ 的方案数。

把六个异或的顺序改一改：$(I_b\bigoplus I_g)\bigoplus (G_b\bigoplus G_g)\bigoplus (A_b\bigoplus A_g)=i$

只需要看统计 $I_b\bigoplus I_g$ 的出现次数($G,A$ 同理)，然后 $\mbox {FWT}$ 就可以了。

此时可以把 $I_b,I_g$ 相差不超过 $k$ 的统计一下就好了。

时间复杂度 $O(n^2\log n)$

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define ll long long
#define ull unsigned long long
const int N=2048;
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
inline void fwt(int n,ll *a,int t)
{
	ll 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[i+j+k];
				a[j+k]=x+y,a[i+j+k]=x-y;
				if(t!=1) a[j+k]=a[j+k]/2,a[i+j+k]=a[i+j+k]/2;
			}
}
inline void get(ll *a,int x,int y,int z)
{
	fo(i,0,min(x,y-z)) a[i^(i+z)]++;
}
ll cnt[3][N],a[3][N],las[N];
ull ans;
int b[3],g[3];
int main()
{
	for(int _=read(),T=1;T<=_;T++)
	{
		b[0]=read(),b[1]=read(),b[2]=read();
		g[0]=read(),g[1]=read(),g[2]=read();
		fo(i,0,N-1) cnt[0][i]=cnt[1][i]=cnt[2][i]=las[i]=0;
		ans=0;
		fo(i,0,2000)
		{
			fo(j,0,2) get(cnt[j],b[j],g[j],i);
			if(i) fo(j,0,2) get(cnt[j],g[j],b[j],i);
			fo(j,0,N-1) fo(k,0,2) a[k][j]=cnt[k][j];
			fo(k,0,2) fwt(N,a[k],1);
			fo(j,0,N-1) a[0][j]=a[0][j]*a[1][j]*a[2][j];
			fwt(N,a[0],-1);
			fo(j,0,N-1) ans+=(a[0][j]-las[j])*(j^i),las[j]=a[0][j];
		}
		printf("Case #%d: %llu\n",T,ans);
	}
	return 0;
}