组成三角形的条件:a+b>c
其中,a
若已知
两条线段之和 = i 的方案数 g[i]
线段长度 > i 的 线段数量 t[i]
答案是否可以表示为 Σ g[i]*t[i] ?
不能,因为 有 c 是最大的数的限制
去掉 c 是最大数的限制:
不能组成三角形的条件:a+b<=c
其中,a
在这里,满足条件的 c 一定是 abc 中最大的
所以解题思路是 求出不能组成三角形的方案数 S
g[i] 两条线段和为 i 的方案数
t[i] 线段长度 >=i 的 线段数
f[i] 线段长度 = i 的线段数
那么
g 的计算:
g[i]= Σ f[j]*f[i-j]
若 i 是偶数 g[i]-=f[i/2] (总长为 i,方案数应该是 f[i/2]*(f[i/2]-1),在式子中算的是 f[i/2]*f[i/2])
g[i]/=2 (每个方案被枚举了两次)
S=Σg[i]*t[i]
tot=C(n,3)
ans=(tot-S)/ tot
用 fft 把 g 的计算优化到 nlogn
多项式:g[]=f[]*f[]
- #include < cmath > #include < cstdio > #include < cstring > #include < iostream > #include < algorithm >
- using namespace std;
- const int N = 1 << 18;
- const double pi = acos( - 1);
- struct Complex {
- double x,
- y;
- Complex() {}
- Complex(double x_, double y_) : x(x_),
- y(y_) {}
- Complex operator + (Complex P) {
- Complex C;
- C.x = x + P.x;
- C.y = y + P.y;
- return C;
- }
- Complex operator - (Complex P) {
- Complex C;
- C.x = x - P.x;
- C.y = y - P.y;
- return C;
- }
- Complex operator * (Complex P) {
- Complex C;
- C.x = x * P.x - y * P.y;
- C.y = x * P.y + y * P.x;
- return C;
- }
- };
- typedef Complex E;
- E f[N];
- long long t[N],
- g[N];
- int n;
- int r[N];
- void read(int & x) {
- x = 0;
- char c = getchar();
- while (!isdigit(c)) c = getchar();
- while (isdigit(c)) {
- x = x * 10 + c - '0';
- c = getchar();
- }
- }
- void fft(E * a, int tag) {
- for (int i = 0; i < n; ++i) if (i < r[i]) swap(a[i], a[r[i]]);
- for (int i = 1; i < n; i <<= 1) {
- E wn(cos(pi / i), tag * sin(pi / i));
- for (int p = i << 1, j = 0; j < n; j += p) {
- E w(1, 0);
- for (int k = 0; k < i; ++k, w = w * wn) {
- E x = a[j + k],
- y = w * a[j + k + i];
- a[j + k] = x + y;
- a[j + k + i] = x - y;
- }
- }
- }
- }
- int main() {
- int T;
- read(T);
- int a,
- mx;
- long long ans,
- tot;
- while (T--) {
- memset(t, 0, sizeof(t));
- memset(g, 0, sizeof(g));
- memset(f, 0, sizeof(f));
- read(n);
- tot = (long long) n * (n - 1) * (n - 2) / 6;
- mx = 0;
- for (int i = 1; i <= n; ++i) {
- read(a);
- t[a]++;
- f[a].x++;
- g[a << 1]--;
- mx = max(mx, a);
- }
- for (int i = mx - 1; i; --i) t[i] += t[i + 1];
- int m = mx - 1 << 1;
- int bit = 0;
- for (n = 1; n <= m; n <<= 1) bit++;
- for (int i = 0; i < n; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << bit - 1);
- fft(f, 1);
- for (int i = 0; i < n; ++i) f[i] = f[i] * f[i];
- fft(f, -1);
- for (int i = 0; i < n; ++i) g[i] += (int)(f[i].x / n + 0.5);
- ans = 0;
- for (int i = 0; i < n; ++i) ans += (g[i] >> 1) * t[i];
- ans = tot - ans;
- printf("%.7lf\n", ans * 1.0 / tot);
- }
- }
给定 n 个长度分别为 a_i 的木棒,问随机选择 3 个木棒能够拼成三角形的概率。
第一行 T(T<=100),表示数据组数。
接下来若干行描述 T 组数据,每组数据第一行是 n,接下来一行有 n 个数表示 a_i。
3≤N≤10^5,1≤a_i≤10^5
T 行,每行一个整数,四舍五入保留 7 位小数。
2 4 1 3 3 4 4 2 3 3 4
0.5000000 1.0000000
T<=20
N<=100000
来源: http://www.bubuko.com/infodetail-2446072.html