「BZOJ 3771」Triple

Problem

Description

给定 n 个物品,第 i 个物品的价值为 x_{i}
求在这 n 个物品中选出 1 个或 2 个或 3 个的所有可能价值和,并对于每个价值和 v 求出价值和为 v 的方案数。

两种方案是相同的当且仅当其选择的物品种类均相同。

Constraints

1\le n\le 4\times 10^{4},x_{i}\le 4\times 10^{4}

Solution

Analysis

设价值为 v 的物品的个数为 c_{v} ,则易得选择一件物品的方案的 OGF:

f(x)=\sum_{v}c_{v}x^{v}

考虑选择两件物品的情况。
g(x) 为选择两件相同物品的方案的 OGF:

g(x)=\sum_{v}c_{v}x^{2v}

则选择两件物品的合法方案的 OGF 即为:

\frac{f^{2}(x)-g(x)}{2!}=\frac{f^{2}(x)-g(x)}{2}

亦即在所有选择两件物品的方案中减去有重复物品的方案数后再去除本质相同的方案。

考虑选择三件物品的情况。
h(x) 为选择三件相同物品的方案的 OGF:

h(x)=\sum_{v}c_{v}x^{3v}

发现在选择三件物品的方案中出现重复只有以下几种可能:

AAB,ABA,BAA,AAA

其中 AAB,ABA,BAA 所对应的方案的 OGF 均为 (f \cdot g)(x)
AAA 所对应的方案的 OGF 为 h(x)
AAB,ABA,BAA 中均包含了 AAA 的情况,所以要将其从 (f \cdot g)(x) 中减去。

故选择三件物品的合法方案的 OGF 为

\frac{f^{3}(x)-3\left((f \cdot g)(x)-h(x)\right)-h(x)}{3!}=\frac{f^{3}(x)-3(f \cdot g)(x)+2h(x)}{6}

所求的 OGF 即为三者之和

f(x)+\frac{f^{2}(x)-g(x)}{2}+\frac{f^{3}(x)-3(f \cdot g)(x)+2h(x)}{6}

使用 FFT 加速即可。

时间复杂度 O(n \log{n})

Code

在 BZOJ 上随手交了一发就跑了 rank1...第一次体会到没有自己的权限号是多么难受 qwq

rank1

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include<cstdio>
#include<cmath>

constexpr int Maxdeg=131072;

template<typename _Tp>
inline void chkMax(_Tp&x,const _Tp&y)
{(x<y)&&(x=y);}
template<typename _Tp>
inline void swap(_Tp&x,_Tp&y)
{_Tp t=x;x=y;y=t;}
template<typename _Tp>
inline _Tp sqr(_Tp&x)
{return x*x;}
template<typename _Tp>
inline _Tp cube(_Tp&x)
{return x*x*x;}

constexpr double PI=acos(-1.0);

struct IO{
#define ISIZE 16384
#define OSIZE 65536

char IBUF[ISIZE],*IS,*IT;
char OBUF[OSIZE+128],*OS,*OT;

IO():IS(IBUF),IT(IBUF),OS(OBUF),OT(OBUF+OSIZE){}
~IO(){Flush();}

inline char gc(){return(IS==IT)&&(IT=(IS=IBUF)+fread(IBUF,1,ISIZE,stdin),IS==IT)?EOF:*IS++;}
template<typename T>inline IO&operator>>(T&x){
T s=0;char c;
if(IS+7<IT){
do c=*IS++;while(c<48||c>57);
do s=s*10+c-48,c=*IS++;while(c>47&&c<58);
}else{
do c=gc();while(c<48||c>57);
do s=s*10+c-48,c=gc();while(c>47&&c<58);
}return(x=s,*this);
}

inline void Flush(){fwrite(OBUF,1,OS-OBUF,stdout);OS=OBUF;}
inline void pc(const char&c){if(OS>OT)Flush();*OS++=c;}
inline IO&operator<<(const char&c){return(pc(c),*this);}
template<typename T>inline IO&operator<<(const T&s){
if(OS>OT)Flush();
T x=s;
static char OStack[30];static int Top=0;
do OStack[++Top]=x%10+48;while(x/=10);
while(Top)*OS++=OStack[Top--];
return*this;
}

#undef ISIZE
#undef OSIZE
}io;

template<typename _Tp>struct Complex{
_Tp x,y;
Complex(const _Tp&_x=0,const _Tp&_y=0):x(_x),y(_y){}

friend inline Complex<_Tp>conj(const Complex<_Tp>&rhs)
{return Complex<_Tp>(rhs.x,-rhs.y);}
inline Complex<_Tp>operator+(const Complex<_Tp>&rhs)
{return Complex<_Tp>(x+rhs.x,y+rhs.y);}
inline Complex<_Tp>operator-(const Complex<_Tp>&rhs)
{return Complex<_Tp>(x-rhs.x,y-rhs.y);}
inline Complex<_Tp>operator*(const Complex<_Tp>&rhs)
{return Complex<_Tp>(x*rhs.x-y*rhs.y,y*rhs.x+x*rhs.y);}
inline Complex<_Tp>operator/(const Complex<_Tp>&rhs){
_Tp div=sqr(rhs.x)+sqr(rhs.y);
return Complex<_Tp>((x*rhs.x-y*rhs.y)/div,(y*rhs.x-x*rhs.y)/div);
}

inline Complex<_Tp>&operator+=(const Complex<_Tp>&rhs)
{return(x+=rhs.x,y+=rhs.y,*this);}
inline Complex<_Tp>&operator-=(const Complex<_Tp>&rhs)
{return(x-=rhs.x,y-=rhs.y,*this);}
inline Complex<_Tp>&operator*=(const Complex<_Tp>&rhs)
{return*this=*this*rhs;}
inline Complex<_Tp>&operator/=(const Complex<_Tp>&rhs)
{return*this=*this/rhs;}
};

template<typename _Tp>
void FFT(Complex<_Tp>*A,const int&deg,const int&Flag){
for(int i=0,j=0;i<deg;++i){
if(i>j)swap(A[i],A[j]);
for(int k=deg>>1;(j^=k)<k;k>>=1);
}for(int Len=1;Len<deg;Len<<=1){
Complex<_Tp>wn(cos(PI/Len),Flag*sin(PI/Len));
for(int i=0;i<deg;i+=Len<<1){
Complex<_Tp>w(1,0);
for(int j=0;j<Len;++j,w=w*wn){
Complex<_Tp>x=A[i+j+Len]*w;
A[i+j+Len]=A[i+j]-x;
A[i+j]+=x;
}
}
}if(Flag==-1)
for(int i=0;i<deg;++i)
A[i].x/=deg;
}

Complex<double>f[Maxdeg];
Complex<double>g[Maxdeg];
int h[Maxdeg];

int main(){
int n;io>>n;
int Maxv=0;
for(int i=1,x;i<=n;++i){
io>>x;chkMax(Maxv,x+x+x);
f[x].x+=1.0;
g[x+x].x+=1.0;
++h[x+x+x];
}

int deg=1;
for(;deg<Maxv;deg<<=1);

FFT(f,deg,1);FFT(g,deg,1);
for(int i=0;i<deg;++i)
f[i]=cube(f[i])/6.0+(f[i]*(f[i]-g[i])-g[i])/2.0+f[i];
FFT(f,deg,-1);

for(int i=0;i<deg;++i){
int x=int(f[i].x+(double)(h[i]/3.0)+0.5);
if(x)io<<i<<' '<<x<<'\n';
}

return 0;
}