Description：

给出 $n$ 个物品的价值，问选出 $1/2/3$ 个物品总价值为 $k$ 的方案数之和。

$1\leqslant n\leqslant 40000$

Solution：

以为是生成函数 $+FFT$ 裸题，果然还是太菜。

首先生成函数是一定有的，设 $X$ 是每种斧头取一个的生成函数， $Y$ 是每种取两个， $Z$ 是三个，那么容斥一下： $$ \begin{align} A&=X\\ B&=\frac{X^2-Y}2\\ C&=\frac{X^3-3XY+2Z}6 \end{align} $$ $(a,a,a)$ 会在 $X^3$ 中出现 $1$ 次， $XY$ 中出现 $1$ 次，所以要加 $2$ 次。

$(a,a,b)$ 会在 $X^3$ 中出现 $3$ 次， $XY$ 中出现 $1$ 次（因为生成函数 $X$ 和 $Y$ 是有顺序的）。

所以这样容斥一下的结果累加就是答案。

模数还要用 $2281701377$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 480010

int v[MAXN];

typedef long long ll;

ll a[MAXN],b[MAXN],c[MAXN];

ll x[MAXN],y[MAXN],z[MAXN];

const ll P = 2281701377ll;

ll ww[MAXN << 1],*g = ww + MAXN;

int rev[MAXN];

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % P;

		a = a * a % P;

		b = b >> 1;

	}

	return res;

}

ll inv(ll k){return power(k,P - 2);}

void NTT(ll f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		ll wn = g[type * l / i];

		for(int j = 0;j < l;j += i)

		{

			ll w = 1;

			for(int k = j;k < j + i / 2;++k)

			{

				ll u = f[k],t = w * f[k + i / 2] % P;

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				w = w * wn % P;

			}

		}

	}

	if(type == -1)

	{

		for(int i = 0;i < l;++i)f[i] = f[i] * inv((ll)l) % P;

	}

	return;

}

int main()

{

	scanf("%d",&n);

	int maxv = 0;

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

	{

		scanf("%d",&v[i]);

		a[1 * v[i]] = 1;

		b[2 * v[i]] = 1;

		c[3 * v[i]] = 1;

		maxv = max(maxv,3 * v[i]);

	}

	int l = 0,len = 1;

	for(;len <= 2 * maxv;len = len << 1,++l);

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(int i = 2;i < len;++i)g[i] = g[i - len] = g[i - 1] * g[1] % P;

	//for(int i = 0;i < len;++i)cout << a[i] << " ";cout << endl;

	//for(int i = 0;i < len;++i)cout << b[i] << " ";cout << endl;

	//for(int i = 0;i < len;++i)cout << c[i] << " ";cout << endl;

	NTT(a,len,1);NTT(b,len,1);NTT(c,len,1);

	for(int i = 0;i < len;++i)x[i] = a[i];

	for(int i = 0;i < len;++i)y[i] = (a[i] * a[i] % P - b[i] + P) % P * inv(2ll);

	for(int i = 0;i < len;++i)

	{

		z[i] = a[i] * a[i] % P * a[i] % P;

		z[i] = (z[i] - 3 * a[i] % P * b[i] % P + P) % P;

		z[i] = (z[i] + 2 * c[i]) % P;

		z[i] = z[i] * inv(6ll) % P;

	}

	NTT(x,len,-1);NTT(y,len,-1);NTT(z,len,-1);

	//for(int i = 0;i < len;++i)cout << x[i] << " ";cout << endl;

	//for(int i = 0;i < len;++i)cout << y[i] << " ";cout << endl;

	//for(int i = 0;i < len;++i)cout << z[i] << " ";cout << endl;

	for(int i = 0;i < len;++i)

	{

		if(x[i] + y[i] + z[i] != 0)

		{

			printf("%d %d\n",i,x[i] + y[i] + z[i]);

		}

	}

	return 0;

}