HDU - 4609

思路：
記錄每個(gè)木棍長度出現(xiàn)的次數(shù)，然后就可以用用類似多項(xiàng)式的乘法（專業(yè)術(shù)語：卷積，因?yàn)槭窍聵?biāo)和為一特定值的積的和（x+y=k），相當(dāng)于在笛卡爾坐標(biāo)系中將這條直線卷起來，故得名卷積）的方法計(jì)算兩個(gè)組合后每個(gè)長度的木棍的個(gè)數(shù)，然后用容斥減去多余的。

然后對它求個(gè)前綴和sum

假設(shè)兩個(gè)組合最長木棍為l

然后再枚舉n個(gè)木棍，假設(shè)當(dāng)前的ai為最大的木棍，

另外兩個(gè)木棍的和肯定大于ai，所以方案數(shù)加sum[l] - sum[ai]

減去另外兩個(gè)都大于它的情況，也就是減去(n-i-1)*(n-i-2)/2

減去一大一小的情況，也就是減去i*(n-i-1)

減去一個(gè)為本身，一個(gè)為其他的情況，也就是減去n-1

最后拿方案數(shù)除以所有的情況n*(n-1)*(n-2)/6

代碼：

#include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long #define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pii pair<int, int> #define piii pair<int,pii> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //headconst int N = 4e5 + 10; int a[N], R[N]; LL num[N],sum[N]; struct Complex {double x, y;Complex(double _x=0, double _y=0) : x(_x),y(_y) {};Complex operator + (Complex &t) {return Complex(x+t.x, y+t.y);}Complex operator - (Complex &t) {return Complex(x-t.x, y-t.y);}Complex operator * (Complex &t) {return Complex(x*t.x - y*t.y, x*t.y + y*t.x);} }X[N]; void fft(Complex *x, int n, int type) {for (int i = 0; i < n; i++) if(i < R[i]) swap(x[i], x[R[i]]);for (int i = 1; i < n; i<<=1) {Complex wn(cos(pi/i), type*sin(pi/i));for (int j = 0; j < n; j+=i<<1) {Complex w(1, 0);for (int k = 0; k < i; k++, w=w*wn) {Complex X = x[j+k];Complex Y = w*x[j+k+i];x[j+k] = X + Y;x[j+k+i] = X - Y;}}} } int main() {int T, n;scanf("%d", &T);while(T--) {mem(num, 0);scanf("%d", &n);for (int i = 0; i < n; i++) scanf("%d", &a[i]), num[a[i]]++;sort(a, a+n);int len = a[n-1] + 1;int l = 1, L = 0;for (int i = 0; i < len; i++) X[i] = Complex(num[i], 0);for ( ; l < len*2; l <<= 1) L++;for (int i = len; i < l; i++) X[i] = Complex(0, 0);for (int i = 0; i < l; i++) {R[i] = (R[i>>1]>>1)|((i&1)<<L-1);}fft(X, l, 1);for (int i = 0; i < l; i++) X[i] = X[i]*X[i];fft(X, l, -1);for (int i = 0; i < l; i++) num[i] = (LL)(X[i].x/l + 0.5);for (int i = 0; i < n; i++) num[a[i]+a[i]]--; for (int i = 0; i < l; i++) num[i] /= 2;sum[0] = num[0];for (int i = 1; i < l; i++) sum[i] = sum[i-1] + num[i]; LL ans = 0;for(int i = 0; i < n; i++) {ans += sum[l-1] - sum[a[i]];ans -= 1LL * (n-i-1) * i;ans -= 1LL * (n-i-1) * (n-i-2) / 2;ans -= n-1;} LL t = 1LL*n*(n-1)*(n-2)/6;printf("%.7f\n", (double)ans/t);}return 0; }

PS:長度可以擴(kuò)展一點(diǎn)，后面是0都沒關(guān)系，只要長度是2的冪次就可以

轉(zhuǎn)載于:https://www.cnblogs.com/widsom/p/9155012.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。