BZOJ 3771: Triple(生成函数 FFT)

Time Limit: 20 Sec Memory Limit: 64 MB
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

4
4
5
6
7

Sample Output

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
样例解释
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(-);

using namespace std;

const int MAXN = ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

struct complex {

    double x, y;

    complex(double xx = , double yy = ) {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 = ; i < N; i++) if(i < r[i]) swap(A[i], A[r[i]]);

    for(int mid = ; mid < N; mid <<= ) {

        complex Wn(cos(pi / mid), type * sin(pi / mid));

        for(int j = ; j < N; j += (mid << )) {

            complex w = complex(, );

            for(int i = ; 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 == -) {

        for(int i = ; i < N; i++)

            A[i].x /= N;

    }

}

void print(complex *a) {

    for(int i = ; 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 = ; i <= n; i++)

        val = read(),

        A[val].x = ,

        B[ * val].x = ,

        C[ * val].x = ,

        len = max( * val, len);

    len = len + ;//tag

    for(N = ; N <= len; N <<= , L++);

    for(int i = ; i < N; i++)

        r[i] = (r[i >> ] >> ) | ((i & ) << (L - ));

    FFT(C, );

    FFT(A, );

    FFT(B, );

    for(int i = ; 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, -);

    for(int i = ; i < N; i++) {

        long long cur = (long long )(A[i].x + 0.5);

        if(cur)

            printf("%d %lld\n", i, cur);

    }

    return ;

}

巴特西

BZOJ 3771: Triple(生成函数 FFT)

Description

Input

Output

Sample Input

Sample Output

HINT

Source

最新文章

热门文章