3-idiots

思路

多項式卷積的經典應用了：

看樣例一:

4 1 3 3 4

我們用多項式系數表示得到一個與$a_i$有關的多項式：$01021$，

也就說明原序列有0個1，1個1，0個2，2個3，1個4，

這個多項式卷積之后得到：0 0 1 0 4 2 4 4 1

也就是可重復使用上面的兩個數可以得到1個2$\dots$

由此我們就確定了三角形的兩條邊了，但是因為可重復使用+有序，所以我們要對上面的數值做一點點改變。

for(int i = 1; i <= n; i++) {num[x[i] + x[i]]--; }//去除重復使用 for(int i= 0; i < lim; i++) {num[i] >>= 1; }//把序列變成有序狀態(tài)

接下來就是找出合法的組合方案了。

我們枚舉最大的邊，把不合法的方案都給減去即可。

代碼

/*Author : lifehappy */ #include <bits/stdc++.h>using namespace std;typedef long long ll;const double pi = acos(-1.0);const int N = 1e6 + 10;struct Complex {double r, i;Complex(double _r = 0, double _i = 0) : r(_r), i(_i) {}}a[N];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); }int r[N], x[N], n, m;ll num[N];void fft(Complex * f, int lim, int rev) {for(int i = 0; i < lim; i++) {if(r[i] < i) {swap(f[i], f[r[i]]);}}for(int i = 1; i < lim; i <<= 1) {Complex wn = Complex(cos(pi / i), rev * sin(pi / i));for(int p = i << 1, j = 0; j < lim; j += p) {Complex w = Complex(1, 0);for(int k = 0; k < i; k++, w = w * wn) {Complex x = f[j + k], y = w * f[i + j + k];f[j + k] = x + y, f[i + j + k] = x - y;}}}if(rev == -1) {for(int i = 0; i < lim; i++) {f[i].r /= lim;}} }void get_r(int lim) {for(int i = 0; i < lim; ++i) {r[i] = (i & 1) * (lim >> 1) + (r[i >> 1] >> 1);} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T, lim;scanf("%d", &T);while(T--) {scanf("%d", &n);memset(num, 0, sizeof num);for(int i = 1; i <= n; i++) {scanf("%d", &x[i]);num[x[i]]++;}sort(x + 1, x + 1 + n);lim = 1;while(lim <= (2 * x[n])) {lim <<= 1;}for(int i = 0; i <= x[n]; i++) {a[i] = Complex(num[i], 0);}for(int i = x[n] + 1; i < lim; i++) {a[i] = Complex(0, 0);}get_r(lim);fft(a, lim, 1);for(int i = 0; i < lim; i++) {a[i] = a[i] * a[i];}fft(a, lim, -1);for(int i = 0; i < lim; i++) {num[i] = int(a[i].r + 0.5);}for(int i = 1; i <= n; i++) {num[x[i] + x[i]]--;}for(int i= 0; i < lim; i++) {num[i] >>= 1;}ll tot = 1ll * n * (n - 1) * (n - 2) / 6, ans = tot;for(int i = 1, k = 1; i < lim; i++) {if(num[i]) {while(k <= n && i > x[k]) k++;if(k == n + 1) break;ans -= num[i] * (n - k + 1);}}printf("%.7f\n", 1.0 * ans / tot);}return 0; }

C - Golf Bot（附贈裸題）

思路

多項式相乘一下，然后判斷哪些值出現了，再記個數就行，FFT裸題。

代碼

/*Author : lifehappy */ #include <bits/stdc++.h>using namespace std;typedef long long ll;const double pi = acos(-1.0);const int N = 1e6 + 10;struct Complex {double r, i;Complex(double _r = 0, double _i = 0) : r(_r), i(_i) {}}a[N];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); }int r[N], k[N], num[N], d[N], n, m, ans, lim;void fft(Complex * f, int lim, int rev) {for(int i = 0; i < lim; i++) {if(r[i] < i) {swap(f[i], f[r[i]]);}}for(int i = 1; i < lim; i <<= 1) {Complex wn = Complex(cos(pi / i), rev * sin(pi / i));for(int p = i << 1, j = 0; j < lim; j += p) {Complex w = Complex(1, 0);for(int k = 0; k < i; k++, w = w * wn) {Complex x = f[j + k], y = w * f[i + j + k];f[j + k] = x + y, f[i + j + k] = x - y;}}}if(rev == -1) {for(int i = 0; i < lim; i++) {a[i].r /= lim;}} }void get_r(int lim) {for(int i = 0; i < lim; ++i) {r[i] = (i & 1) * (lim >> 1) + (r[i >> 1] >> 1);} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf("%d", &n);for(int i = 1; i <= n; i++) {scanf("%d", &k[i]);num[k[i]]++;}sort(k + 1, k + 1 + n);lim = 1;while(lim < k[n] * 2) lim <<= 1;for(int i = 0; i < lim; i++) {a[i] = Complex(num[i], 0);}get_r(lim);fft(a, lim, 1);for(int i = 0; i < lim; i++) {a[i] = a[i] * a[i];}fft(a, lim, -1);for(int i = 0; i < lim; i++) {num[i] += int(a[i].r + 0.5);}scanf("%d", &m);for(int i = 1; i <= m; i++) {int x;scanf("%d", &x);if(num[x]) {num[x] = 0;ans++;}}printf("%d\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的HDU 4609 3-idiots（FFT）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。