Description 我們講一個悲傷的故事。 從前有一個貧窮的樵夫在河邊砍柴。 這時候河裡出現了一個水神，奪過了他的斧頭，說： “這把斧頭，是不是你的？” 樵夫一看：“是啊是啊！” 水神把斧頭扔在一邊，又拿起一個東西問： “這把斧頭，是不是你的？” 樵夫看不清楚，但又怕真的是自己的斧頭，只好又答： ...
Submit: 911 Solved: 528
[Submit][Status][Discuss]
Description
我們講一個悲傷的故事。 從前有一個貧窮的樵夫在河邊砍柴。 這時候河裡出現了一個水神，奪過了他的斧頭，說： “這把斧頭，是不是你的？” 樵夫一看：“是啊是啊！” 水神把斧頭扔在一邊，又拿起一個東西問： “這把斧頭，是不是你的？” 樵夫看不清楚，但又怕真的是自己的斧頭，只好又答：“是啊是啊！” 水神又把手上的東西扔在一邊，拿起第三個東西問： “這把斧頭，是不是你的？” 樵夫還是看不清楚，但是他覺得再這樣下去他就沒法砍柴了。 於是他又一次答：“是啊是啊！真的是！” 水神看著他，哈哈大笑道： “你看看你現在的樣子，真是醜陋！” 之後就消失了。 樵夫覺得很坑爹，他今天不僅沒有砍到柴，還丟了一把斧頭給那個水神。 於是他準備回家換一把斧頭。 回家之後他才發現真正坑爹的事情才剛開始。 水神拿著的的確是他的斧頭。 但是不一定是他拿出去的那把，還有可能是水神不知道怎麼偷偷從他家裡拿走的。 換句話說，水神可能拿走了他的一把，兩把或者三把斧頭。 樵夫覺得今天真是倒霉透了，但不管怎麼樣日子還得過。 他想統計他的損失。 樵夫的每一把斧頭都有一個價值，不同斧頭的價值不同。總損失就是丟掉的斧頭價值和。 他想對於每個可能的總損失，計算有幾種可能的方案。 註意：如果水神拿走了兩把斧頭a和b，(a,b)和(b,a)視為一種方案。拿走三把斧頭時，(a,b,c),(b,c,a),(c,a,b),(c,b,a),(b,a,c),(a,c,b)視為一種方案。
Input
第一行是整數N，表示有N把斧頭。 接下來n行升序輸入N個數字Ai，表示每把斧頭的價值。
Output
若幹行，按升序對於所有可能的總損失輸出一行x y，x為損失值，y為方案數。
Sample Input
44
5
6
7
Sample Output
4 15 1
6 1
7 1
9 1
10 1
11 2
12 1
13 1
15 1
16 1
17 1
18 1
樣例解釋
11有兩種方案是4+7和5+6，其他損失值都有唯一方案，例如4=4,5=5,10=4+6,18=5+6+7.
HINT
所有數據滿足：Ai<=40000
Source
應該不難看出是生成函數
我們用$A(x) = a + bx^1 + cx^2 + \dots $表示價值為$1$的方案為$a$，價值為$2$的方案為$b$
那麼很顯然的思路就是：$A(x) + \frac{A(x) * A(x)}{2!} + \frac{A(x) * A(x) * A(x)}{3!}$
但是題目中要求了每種斧子只能拿一次，這樣會多計算重覆拿的一部分
因此我們考慮用容斥的方法將他們減去
定義$B(x) = x ^ i$表示價值為$i$的拿了兩把的方案數
$C(x) = x ^ i$表示價值為$i$的拿了三把的方案數
拿兩把斧子時會計算到$(x, x)$這種情況，所以拿兩把時應該為$\frac{A(x) * A(x) - B(x)}{2!}$
拿三把時有些複雜
我們需要減去$(x, x, x)$和$(x, y, y)$這兩種情況
第一種情況就是$C(x)$
第二種情況可以通過$A(x)* B(x)$計算得到，但此時也計算上了$(x, x, x)$這種情況
$(x, y, y)$有三種組合排列方式，所以要乘$3$，但$(x, x, x)$只有一種排列方式，所以最終統計答案時要加上$2 * C(x)$
最終的答案就是
$A + \frac{A * A - B}{2!} + \frac{A * A * A - 3 * A * B + 2C}{3!}$
多項式乘法可以用NTT，不過模數會炸998244353
看到大佬們都用FFT A了，那我就偷個懶嘍
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> //#include<iostream> const double pi = acos(-1); using namespace std; const int MAXN = 150000; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } struct complex { double x, y; complex(double xx = 0, double yy = 0) {x = xx, y = yy;} complex operator + (const complex &rhs) { return complex(x + rhs.x, y + rhs.y); } complex operator - (const complex &rhs) { return complex(x - rhs.x, y - rhs.y); } complex operator * (const complex &rhs) { return complex(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x); } complex operator * (const double &rhs) { return complex(x * rhs, y * rhs); } complex operator / (const double &rhs) { return complex(x / rhs, y / rhs); } }A[MAXN], B[MAXN], C[MAXN]; int val, n, N, L, len, r[MAXN]; void FFT(complex *A, int type) { for(int i = 0; i < N; i++) if(i < r[i]) swap(A[i], A[r[i]]); for(int mid = 1; mid < N; mid <<= 1) { complex Wn(cos(pi / mid), type * sin(pi / mid)); for(int j = 0; j < N; j += (mid << 1)) { complex w = complex(1, 0); for(int i = 0; i < mid; i++, w = w * Wn) { complex x = A[j + i], y = w * A[j + i + mid]; A[j + i] = x + y; A[j + i + mid] = x - y; } } } if(type == -1) { for(int i = 0; i < N; i++) A[i].x /= N; } } void print(complex *a) { for(int i = 0; i < N; i++) printf("%d %lf %lf\n", i, a[i].x, a[i].y); } int main() { #ifdef WIN32 freopen("a.in", "r", stdin); freopen("b.out", "w", stdout); #endif n = read(); for(int i = 1; i <= n; i++) val = read(), A[val].x = 1, B[2 * val].x = 1, C[3 * val].x = 1, len = max(3 * val, len); len = len + 1;//tag for(N = 1; N <= len; N <<= 1, L++); for(int i = 0; i < N; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1)); FFT(C, 1); FFT(A, 1); FFT(B, 1); for(int i = 0; i < N; i++) A[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; FFT(A, -1); for(int i = 0; i < N; i++) { long long cur = (long long )(A[i].x + 0.5); if(cur) printf("%d %lld\n", i, cur); } return 0; }
