网页设计与网站建设作业,深圳龙华网站公司,微动网站建设,酒店管理系统#3771. Triple
考虑只有一个损失时#xff0c;损失值的生成函数为A(x)A(x)A(x)。
如果不考虑无序方案#xff0c;有两个损失的生成函数为B(x)A(x)A(x)B(x) A(x)A(x)B(x)A(x)A(x)#xff0c;同理有三个的时候C(x)A(x)A(x)A(x)C(x) A(x)A(x)A(x)C(x)A(x)A(x)A(x)。
考虑如…#3771. Triple
考虑只有一个损失时损失值的生成函数为A(x)A(x)A(x)。
如果不考虑无序方案有两个损失的生成函数为B(x)A(x)A(x)B(x) A(x)A(x)B(x)A(x)A(x)同理有三个的时候C(x)A(x)A(x)A(x)C(x) A(x)A(x)A(x)C(x)A(x)A(x)A(x)。
考虑如何得到无序方案
选择两个的时候
ababab的排列有ab,baab, baab,ba两种我们先减去aa,bbaa, bbaa,bb的然后除以二就是B(x)B(x)B(x)了所以B(x)A(x)A(x)−D(x)2B(x) \frac{A(x)A(x) - D(x)}{2}B(x)2A(x)A(x)−D(x)。
选择三个的时候
abcabcabc的排列共有666种同样的我们先减去aaa,bbb,cccaaa, bbb, cccaaa,bbb,ccc这样相同的然后除以666就是C(x)A(x)A(x)A(x)−E(x)2C(x) \frac{A(x)A(x)A(x) - E(x)}{2}C(x)2A(x)A(x)A(x)−E(x)。
#include bits/stdc.husing namespace std;struct Complex {double r, i;Complex(double _r 0, double _i 0) : r(_r), i(_i) {}
};Complex operator (const Complex a, const Complex b) {return Complex(a.r b.r, a.i b.i);
}Complex operator - (const Complex a, const Complex b) {return Complex(a.r - b.r, a.i - b.i);
}Complex operator * (const Complex a, const Complex b) {return Complex(a.r * b.r - a.i * b.i, a.r * b.i a.i * b.r);
}Complex operator / (const Complex a, const Complex b) {return Complex((a.r * b.r a.i * b.i) / (b.r * b.r b.i * b.i), (a.i * b.r - a.r * b.i) / (b.r * b.r b.i * b.i));
}Complex operator * (const Complex a, const double b) {return Complex(a.r * b, a.i * b);
}typedef long long ll;const int N 3e5 10;int r[N];Complex x[N], y[N], z[N], ans[N];void get_r(int lim) {for (int i 0; i lim; i) {r[i] (i 1) * (lim 1) (r[i 1] 1);}
}void FFT(Complex *f, int lim, int rev) {for (int i 0; i lim; i) {if (i r[i]) {swap(f[i], f[r[i]]);}}const double pi acos(-1.0);for (int mid 1; mid lim; mid 1) {Complex wn Complex(cos(pi / mid), rev * sin(pi / mid));for (int len mid 1, cur 0; cur lim; cur len) {Complex w Complex(1, 0);for (int k 0; k mid; k, w w * wn) {Complex x f[cur k], y w * f[cur mid k];f[cur k] x y, f[cur mid k] x - y;}}}if (rev -1) {for (int i 0; i lim; i) {f[i].r / lim;}}
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int n;scanf(%d, n);for (int i 1, a; i n; i) {scanf(%d, a);x[a].r, y[a a].r, z[a a a].r;} int lim 1;while (lim 3 * 40000) {lim 1;}get_r(lim);FFT(x, lim, 1), FFT(y, lim, 1), FFT(z, lim, 1);for (int i 0; i lim; i) {ans[i] ans[i] (x[i] * x[i] * x[i] - 3.0 * x[i] * y[i] 2 * z[i]) * (1.0 / 6.0);ans[i] ans[i] (x[i] * x[i] - y[i]) * (1.0 / 2);ans[i] ans[i] x[i];}FFT(ans, lim, -1);for (int i 0; i lim; i) {int res int(ans[i].r 0.5);if (res) {printf(%d %d\n, i, res);}}return 0;
}
