bzoj#P3771. Triple

Triple

题目描述

我们讲一个悲伤的故事。

从前有一个贫穷的樵夫在河边砍柴。

这时候河里出现了一个水神,夺过了他的斧头,说:

“这把斧头,是不是你的?”

樵夫一看:“是啊是啊!”

水神把斧头扔在一边,又拿起一个东西问:

“这把斧头,是不是你的?”

樵夫看不清楚,但又怕真的是自己的斧头,只好又答:“是啊是啊!”

水神又把手上的东西扔在一边,拿起第三个东西问:

“这把斧头,是不是你的?”

樵夫还是看不清楚,但是他觉得再这样下去他就没法砍柴了。

于是他又一次答:“是啊是啊!真的是!”

水神看着他,哈哈大笑道:

“你看看你现在的样子,真是丑陋!”

之后就消失了。

樵夫觉得很坑爹,他今天不仅没有砍到柴,还丢了一把斧头给那个水神。

于是他准备回家换一把斧头。

回家之后他才发现真正坑爹的事情才刚开始。

水神拿着的的确是他的斧头。

但是不一定是他拿出去的那把,还有可能是水神不知道怎么偷偷从他家里拿走的。

换句话说,水神可能拿走了他的一把,两把或者三把斧头。

樵夫觉得今天真是倒霉透了,但不管怎么样日子还得过。

他想统计他的损失。

樵夫的每一把斧头都有一个价值,不同斧头的价值不同。总损失就是丢掉的斧头价值和。

他想对于每个可能的总损失,计算有几种可能的方案。

注意:如果水神拿走了两把斧头 aabb(a,b)(a,b)(b,a)(b,a) 视为一种方案。拿走三把斧头时,(a,b,c)(a,b,c)(b,c,a)(b,c,a)(c,a,b)(c,a,b)(c,b,a)(c,b,a)(b,a,c)(b,a,c)(a,c,b)(a,c,b) 视为一种方案。

输入格式

第一行是整数 nn,表示有 nn 把斧头。
接下来 nn 行升序输入 nn 个数字 aia_i,表示每把斧头的价值。

输出格式

若干行,按升序对于所有可能的总损失值与方案数输出。 具体地,每一行包含两个正整数 x,yx,yxx 为损失值,yy 为方案数。

4
4
5
6
7
4 1
5 1
6 1
7 1
9 1
10 1
11 2
12 1
13 1
15 1
16 1
17 1
18 1

样例解释

1111 有两种方案是 4+74+75+65+6,其他损失值都有唯一方案,例如 4=4,5=5,10=4+6,18=5+6+74=4,5=5,10=4+6,18=5+6+7

数据规模与约定

对于 100%100\% 的数据,n,ai4×104n,a_i \le 4 \times 10^4