[BZOJ3771]Triple

2018-08-12

lolifamily

不同情况的生成函数

我们先设 $𝑎 (𝑥)$ 为丢失一把斧头的生成函数， $𝑏 (𝑥)$ 为丢失两把一样的斧头的生成函数， $𝑐 (𝑥)$ 为丢失三把一样的斧头的生成函数

对于样例来说：

𝑎 (𝑥) = 𝑥 4 + 𝑥 5 + 𝑥 6 + 𝑥 7 𝑏 (𝑥) = 𝑥 8 + 𝑥 10 + 𝑥 12 + 𝑥 14 𝑐 (𝑥) = 𝑥 12 + 𝑥 15 + 𝑥 18 + 𝑥 21

再设 $𝐴 (𝑥)$ 为丢失一把斧头的生成函数， $𝐵 (𝑥)$ 为丢失两把不同的斧头的生成函数， $𝐶 (𝑥)$ 为丢失三把不同的斧头的生成函数

对于样例来说：

𝐴 (𝑥) = 𝑎 (𝑥) 𝐵 (𝑥) = 𝑎 2 (𝑥) - 𝑏 (𝑥) 𝐶 (𝑥) = 𝑎 3 (𝑥) - 3 𝑎 (𝑥) 𝑏 (𝑥) + 2 𝑐 (𝑥)

解释一下 $𝐶 (𝑥)$ ，首先随意的选择三个斧头（可以相同），然后减去选出两把相同的斧头和另一把斧头（也可以相同），但是三个相同的被减了三次，所以要加 $2$

由于数据范围较大，需要用 FFT 或 NTT 优化

Problem

Description

我们讲一个悲伤的故事。

从前有一个贫穷的樵夫在河边砍柴。这时候河里出现了一个水神，夺过了他的斧头，说： “这把斧头，是不是你的？” 樵夫一看：“是啊是啊！”

水神把斧头扔在一边，又拿起一个东西问： “这把斧头，是不是你的？” 樵夫看不清楚，但又怕真的是自己的斧头，只好又答：“是啊是啊！”

水神又把手上的东西扔在一边，拿起第三个东西问： “这把斧头，是不是你的？” 樵夫还是看不清楚，但是他觉得再这样下去他就没法砍柴了。于是他又一次答：“是啊是啊！真的是！”

水神看着他，哈哈大笑道： “你看看你现在的样子，真是丑陋！” 之后就消失了。

樵夫觉得很坑爹，他今天不仅没有砍到柴，还丢了一把斧头给那个水神。于是他准备回家换一把斧头。

回家之后他才发现真正坑爹的事情才刚开始。水神拿着的的确是他的斧头。但是不一定是他拿出去的那把，还有可能是水神不知道怎么偷偷从他家里拿走的。换句话说，水神可能拿走了他的一把，两把或者三把斧头。

樵夫觉得今天真是倒霉透了，但不管怎么样日子还得过。他想统计他的损失。樵夫的每一把斧头都有一个价值，不同斧头的价值不同。总损失就是丢掉的斧头价值和。他想对于每个可能的总损失，计算有几种可能的方案。

注意：如果水神拿走了两把斧头 $𝑎$ 和 $𝑏$ ， $(𝑎, 𝑏)$ 和 $(𝑏, 𝑎)$ 视为一种方案。拿走三把斧头时， $(𝑎, 𝑏, 𝑐)$ , $(𝑏, 𝑐, 𝑎)$ , $(𝑐, 𝑎, 𝑏)$ , $(𝑐, 𝑏, 𝑎)$ , $(𝑏, 𝑎, 𝑐)$ , $(𝑎, 𝑐, 𝑏)$ 视为一种方案。

Input

第一行是整数 $𝑁$ ，表示有 $𝑁$ 把斧头。

接下来 $𝑁$ 行升序输入 $𝑁$ 个数字 $𝐴 𝑖$ ，表示每把斧头的价值。

Output

若干行，按升序对于所有可能的总损失输出一行 $𝑥$ $𝑦$ ， $𝑥$ 为损失值， $𝑦$ 为方案数。

Sample Input

Sample Output

HINT

$11$ 有两种方案是 $4 + 7$ 和 $5 + 6$ ，其他损失值都有唯一方案，例如 $4 = 4$ , $5 = 5$ , $10 = 4 + 6$ , $18 = 5 + 6 + 7$ 。

所有数据满足： $𝐴 𝑖 \leq 40000$

Code

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#include <complex>
6
#include <cmath>
7
using namespace std;
8
typedef complex<double>cp;
9
int rev[140005];
10
cp a[140005],b[140005],c[140005],wi[140005],ans[140005];
11
inline int Make(int n)
12
{
13
  int i,L=log2(n)+1;n=1<<L;
14
  for(i=0;i<n;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
15
  return n;
16
}
17
inline void FFT(cp A[],int n,int f)
18
{
19
  int i,j,k;
20
  for(i=0;i<n;++i)if(rev[i]<i)swap(A[i],A[rev[i]]);
21
  for(i=1;i<n;i<<=1)
22
  {
23
    cp wn(cos(M_PI/i),f*sin(M_PI/i));
24
    wi[0]=1;
25
    for(j=1;j<i;++j)wi[j]=wi[j-1]*wn;
26
    for(j=0;j<n;j+=i<<1)
27
    {
28
      for(k=0;k<i;++k)
29
      {
30
        cp x=A[j+k],y=wi[k]*A[i+j+k];
31
        A[j+k]=x+y;A[i+j+k]=x-y;
32
      }
33
    }
34
  }
35
  if(f==-1)for(i=0;i<n;++i)A[i]=A[i]/double(n);
36
  return;
37
}
38
int main(void)
39
{
40
  int i,x,n,m;
41
  scanf("%d",&n);
42
  for(i=1;i<=n;++i)
43
  {
44
    scanf("%d",&x);
45
    a[x]=b[x*2]=c[x*3]=cp(1,0);
46
  }
47
  m=Make(131071);
48
  FFT(a,m,1);
49
  FFT(b,m,1);
50
  FFT(c,m,1);
51
  for(i=0;i<m;++i)
52
  {
53
    ans[i]=a[i]+(a[i]*a[i]-b[i])/2.0+(a[i]*a[i]*a[i]-a[i]*b[i]*3.0+c[i]*2.0)/6.0;
54
  }
55
  FFT(ans,m,-1);
56
  for(i=0;i<m;++i)
57
  {
58
    if(ans[i].real()>0.9)printf("%d %.0f\n",i,round(ans[i].real()));
59
  }
60
  return 0;
61
}