转载请注明出处:http://tokitsukaze.live/

题目链接:https://codeforces.com/gym/101955/problem/I


题意:
1


题解:
枚举max,max那一坨里面的东西,把每个绝对值展开,用cnt数组记录个数。后面那一坨看作fwt下标,做完fwt后,即可求出max里面三个绝对值恰好都等于max的方案数。
但是题目求的是至少一个绝对值等于max。
于是用pre数组记录之前fwt的结果,pre与cnt不要清空,每次fwt后,减掉pre,就是至少一个等于max的方案数。

代码:

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
void go();
int main(){
#ifdef tokitsukaze
freopen("TEST.txt","r",stdin);
#endif
go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=1e5+10;
const ll mod=1e9+7;
/********************************* head *********************************/
namespace FWT
{
void fwt(ll *a,int n,int f,int v)
{
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];
if(!v)
{
if(f==1) a[i+j]=(x+y),a[i+j+d]=(x-y);
}
else
{
if(f==1) a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;
}
}
}
}
}
void XOR(ll *res,ll *a,ll *b,ll *c,int n)
{
int len;
for(len=1;len<n;len<<=1);
fwt(a,len,1,0);
fwt(b,len,1,0);
fwt(c,len,1,0);
for(int i=0;i<len;i++) res[i]=a[i]*b[i]*c[i];
fwt(res,len,1,1);
}
};
ll cnt[3][2222],pre[2222],tmp[3][2222],res[2222];
void go()
{
int t,cas=1;
ll I[2],A[2],G[2],i,j,mx;
ull ans;
read(t);
while(t--)
{
read(I[0],A[0],G[0],I[1],A[1],G[1]);
mem(cnt,0);
mem(pre,0);
ans=0;
for(mx=0;mx<=2000;mx++)
{
for(i=0;i<=I[0]&&i+mx<=I[1];i++) cnt[0][i^(i+mx)]++;
for(i=0;i<=A[0]&&i+mx<=A[1];i++) cnt[1][i^(i+mx)]++;
for(i=0;i<=G[0]&&i+mx<=G[1];i++) cnt[2][i^(i+mx)]++;
if(mx)
{
for(i=0;i<=I[1]&&i+mx<=I[0];i++) cnt[0][i^(i+mx)]++;
for(i=0;i<=A[1]&&i+mx<=A[0];i++) cnt[1][i^(i+mx)]++;
for(i=0;i<=G[1]&&i+mx<=G[0];i++) cnt[2][i^(i+mx)]++;
}
for(i=0;i<3;i++)
{
for(j=0;j<2048;j++)
{
tmp[i][j]=cnt[i][j];
}
}
FWT::XOR(res,tmp[0],tmp[1],tmp[2],2048);
for(i=0;i<2048;i++)
{
ans+=(res[i]-pre[i])*(i^mx);
pre[i]=res[i];
}
}
printf("Case #%d: %llu\n",cas++,ans);
}
}