[hdu4609]计数方法,FFT

时间:2022-12-22 10:52:15

题目:给一个数组a,从里面任选三个数,求以这三个数为三条边能构成三角形的概率。

思路:由于每个数只能用一次,所以考虑枚举三边中的最大边。先将a数组排序,然后枚举它的每个数x作为最大边,那么问题就是要求在数组a剩余的数里面“找小于等于x”且“和大于x”的数对个数,答案显然不能直接得到。不妨先计算这样一个数组ans[i]:表示在数组a里面有放回的选两个数,和为i的数对个数。设cnt[i]为i这个数在a数组里面出现的次数,那么ans相当于cnt对cnt的卷积结果, 这可以利用FFT在nlogn的时间内求得。ans数组出来以后,由于还需要将它变成“无放回地取两个数”的结果,且要保证答案的无序性(由于每个答案都会被统计两次,全部除以2即可),需要做些处理,具体见代码。处理完后,ans[i]表示从a数组里面任选两个数和为i的方案数,就可以利用ans来得到答案了。

先对ans进行前缀和处理(ans[i]+=ans[i-1]),在枚举到最大边x时,另两边的和可以为x+1~maxsum的任意值,将答案加上ans[maxsum] - ans[x]---(1),由于加的这个答案里面包含很多不合法的,需要一一减去,下面对不合法的进行分类{设共n个数,范围为[a,a+n),现在枚举到了i这个位置,数为x,需要注意的是由于已经排序,下面的大小关系是指位置的大小关系,而不用特别去考虑相等情况了}:

(1)两边都大于x,显然它们的和大于x,所以会出现在(1)里面,需要减去: (n-i-1)*(n-i-2)/2

(2)一边大于x,一边小于x,显然它们的和也大于x,会出现在(1)里面,需要减去:i*(n-i-1)

(3)一边等于x,一边不等于x,显然他们的和也大于x,会出现在(1)里面,需要减去:n-1

这样枚举完所有数,就得到答案了。

另外,整体看减去的数,是一个常数,而枚举每个数累加的ans值跟次序无关 ,于是根本无需排序,一样得到正确的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/* ******************************************************************************** */
#include <iostream>                                                                 //
#include <cstdio>                                                                   //
#include <cmath>                                                                    //
#include <cstdlib>                                                                  //
#include <cstring>                                                                  //
#include <vector>                                                                   //
#include <ctime>                                                                    //
#include <deque>                                                                    //
#include <queue>                                                                    //
#include <algorithm>                                                                //
#include <map>                                                                      //
#include <cmath>                                                                    //
using namespace std;                                                                //
                                                                                    //
#define pb push_back                                                                //
#define mp make_pair                                                                //
#define X first                                                                     //
#define Y second                                                                    //
#define all(a) (a).begin(), (a).end()                                               //
#define fillchar(a, x) memset(a, x, sizeof(a))                                      //
                                                                                    //
void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);}    //
void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R>                    //
void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1;          //
while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T>      //
void print(const T t){cout<<t<<endl;}template<typename F,typename...R>              //
void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T>   //
void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;}   //
                                                                                    //
typedef pair<intint> pii;                                                         //
typedef long long ll;                                                               //
typedef unsigned long long ull;                                                     //
                                                                                    //
template<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);}        //
template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);}        //
template<typename T>                                                                //
void V2A(T a[],const vector<T>&b){for(int i=0;i<b.size();i++)a[i]=b[i];}            //
template<typename T>                                                                //
void A2V(vector<T>&a,const T b[]){for(int i=0;i<a.size();i++)a[i]=b[i];}            //
                                                                                    //
const double PI = acos(-1);                                                         //
                                                                                    //
/* -------------------------------------------------------------------------------- */
 
namespace FFT {
    const static int maxn = 1e5 + 7;
    #define L(x) (1 << (x))
    double ax[maxn << 2], ay[maxn << 2], bx[maxn << 2], by[maxn << 2];//需要四倍空间
    int revv(int x, int bits) {
        int ret = 0;
        for (int i = 0; i < bits; i++) {
            ret <<= 1;
            ret |= x & 1;
            x >>= 1;
        }
        return ret;
    }
    void fft(double * a, double * b, int n, bool rev) {
        int bits = 0;
        while (1 << bits < n) ++bits;
        for (int i = 0; i < n; i++) {
            int j = revv(i, bits);
            if (i < j)
                swap(a[i], a[j]), swap(b[i], b[j]);
        }
        for (int len = 2; len <= n; len <<= 1) {
            int half = len >> 1;
            double wmx = cos(2 * PI / len), wmy = sin(2 * PI / len);
            if (rev) wmy = -wmy;
            for (int i = 0; i < n; i += len) {
                double wx = 1, wy = 0;
                for (int j = 0; j < half; j++) {
                    double cx = a[i + j], cy = b[i + j];
                    double dx = a[i + j + half], dy = b[i + j + half];
                    double ex = dx * wx - dy * wy, ey = dx * wy + dy * wx;
                    a[i + j] = cx + ex, b[i + j] = cy + ey;
                    a[i + j + half] = cx - ex, b[i + j + half] = cy - ey;
                    double wnx = wx * wmx - wy * wmy, wny = wx * wmy + wy * wmx;
                    wx = wnx, wy = wny;
                }
            }
        }
        if (rev) {
            for (int i = 0; i < n; i++)
                a[i] /= n, b[i] /= n;
        }
    }
    int solve(ll a[], int na, ll b[], int nb, ll ans[]) {
        int len = max(na, nb), ln;
        for(ln = 0; L(ln) < len; ++ln);
        len = L(++ln);
        for (int i = 0; i < len ; ++i) {
            if (i >= na) ax[i] = 0, ay[i] = 0;
            else ax[i] = a[i], ay[i] = 0;
        }
        fft(ax, ay, len, 0);
        for (int i = 0; i < len; ++i) {
            if (i >= nb) bx[i] = 0, by[i] = 0;
            else bx[i] = b[i], by[i] = 0;
        }
        fft(bx, by, len, 0);
        for (int i = 0; i < len; ++i) {
            double cx = ax[i] * bx[i] - ay[i] * by[i];
            double cy = ax[i] * by[i] + ay[i] * bx[i];
            ax[i] = cx, ay[i] = cy;
        }
        fft(ax, ay, len, 1);
        for (int i = 0; i < len; ++i)
            ans[i] = (ll)(ax[i] + 0.5);
        return len;
    }
    #undef L(x)
}
const int maxn = 1e5 + 7;
ll c[maxn << 2], d[maxn << 2], ans[maxn << 2], sum[maxn << 2];
int a[maxn];
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt""r", stdin);
#endif // ONLINE_JUDGE
    int T, n;
    cin >> T;
    while (T --) {
        fillchar(c, 0);
        fillchar(d, 0);
        fillchar(ans, 0);
        cin >> n;
        int maxv = 0;
        for (int i = 0; i < n; i ++) {
            RI(a[i]);
            c[a[i]] ++;
            umax(maxv, a[i]);
        }
        maxv ++;
        for (int i = 0; i < maxv; i ++) d[i] = c[i];
        int L = FFT::solve(c, maxv, d, maxv, ans);
        while (ans[L] <= 0 && L > 1) L --;
        L ++;
        for (int i = 0; i < n; i ++) ans[a[i] << 1] --;
        for (int i = 1; i < L; i ++) {
            ans[i] >>= 1;
            sum[i] = sum[i - 1] + ans[i];
        }
        ll Result = 0, Total = (ll)n * (n - 1) * (n - 2) / 6;
        //sort(a, a + n);
        for (int i = 0; i < n; i ++) {
            ll buf = sum[L - 1] - sum[a[i]];
            buf -= n - 1;
            buf -= (ll)i * (n - i - 1);
            buf -= (ll)(n - i - 1) * (n - i - 2) / 2;
            Result += buf;
        }
        printf("%.7f\n", (double)Result / Total);
    }
    return 0;
}
/* ******************************************************************************** */

[hdu4609]计数方法,FFT的更多相关文章

  1. 【spring data jpa】jpa中使用count计数方法

    spring data jpa中使用count计数方法很简单 直接在dao层写方法即可 int countByUidAndTenementId(String parentUid, String ten ...

  2. 【概率论】1-2&colon;计数方法&lpar;Counting Methods&rpar;

    title: [概率论]1-2:计数方法(Counting Methods) categories: Mathematic Probability keywords: Counting Methods ...

  3. 有标号的DAG计数(FFT)

    有标号的DAG计数系列 有标号的DAG计数I 题意 给定一正整数\(n\),对\(n\)个点有标号的有向无环图(可以不连通)进行计数,输出答案\(mod \ 10007\)的结果.\(n\le 500 ...

  4. 【hdu4609】 3-idiots FFT

    题外话:好久没写blog了啊-- 题目传送门 题目大意:给你m条长度为ai的线段,求在其中任选三条出来,能构成三角形的概率.即求在这n条线段中找出三条线段所能拼出的三角形数量除以$\binom{m}{ ...

  5. &lbrack;HDU4609&rsqb;3-idiots&lpar;生成函数&plus;FFT&rpar;

    3-idiots Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total S ...

  6. php导出excel长数字串显示为科学计数方法与最终解决方法

    1.设置单元格为文本 $objPHPExcel = new PHPExcel(); $objPHPExcel->setActiveSheetIndex(0); $objPHPExcel-> ...

  7. UOJ&num;335&period; 【清华集训2017】生成树计数 多项式&comma;FFT&comma;下降幂&comma;分治

    原文链接www.cnblogs.com/zhouzhendong/p/UOJ335.html 前言 CLY大爷随手切这种题. 日常被CLY吊打系列. 题解 首先从 pruffer 编码的角度考虑这个问 ...

  8. bzoj1272 Gate Of Babylon(计数方法&plus;Lucas定理&plus;乘法逆元)

    Description Input Output Sample Input 2 1 10 13 3 Sample Output 12 Source 看到t很小,想到用容斥原理,推一下发现n种数中选m个 ...

  9. loj6570 毛毛虫计数&lpar;生成函数FFT&rpar;

    link 巨佬olinr的题解 <-- olinr很强 考虑生成函数 考虑直径上点数>=4的毛毛虫的直径,考虑直径中间那些节点以及他上面挂的那些点的EGF \(A(x)=\sum_{i\g ...

随机推荐

  1. Java BigDecimal 转换,除法陷阱(转)

    源地址:   http://blog.csdn.net/niannian_315/article/details/24354251 今天在用BigDecimal“出现费解”现象,以前虽然知道要避免用, ...

  2. Vim 练级攻略

    以下的文章翻译自<Learn Vim Progressively>,我认为这是给新手最好的VIM的升级教程了,没有列举全部的命令,仅仅是列举了那些最实用的命令. 很不错. -------- ...

  3. Android布局详解之一:FrameLayout

      原创文章,如有转载,请注明出处:http://blog.csdn.net/yihui823/article/details/6702273 FrameLayout是最简单的布局了.所有放在布局里的 ...

  4. linux服务器上apache+php独立于mysql server单独部署

    1. mysql client 2. libmysqlclient-devel 3. PDO_MYSQL

  5. 学c语言做练习

    /*编写一个函数,其功能是使输入字符串反序.在一个使用循环语句为这个函数提供输入的完整 程序中进行测试.*/ #include<stdio.h> #include<string.h& ...

  6. 浅谈JavaScript中typeof与instanceof的区别

      首先,我们从其常规定义入手:       instanceof 运算符可以用来判断某个构造函数的 prototype 属性是否存在另外一个要检测对象的原型链上.(需要注意的一点是:prototyp ...

  7. Android初级教程人品计算器

    先看布局: main_activity.xml <LinearLayout xmlns:android="http://schemas.android.com/apk/res/andr ...

  8. Ubuntu如何安装vncserver

    Ubuntu上安装和配置vncserver,然后通过客户端进行连接,就能够使用图像界面的方式来运行上面的软件了. 1.使用apt-cache search vncserver命令搜索可以用来安装vnc ...

  9. Linux进程管理 &lpar;9&rpar;实时调度类分析,以及FIFO和RR对比实验

    关键词:rt_sched_class.SCHED_FIFO.SCHED_RR.sched_setscheduler().sched_setaffinity().RR_TIMESLICE. 本文主要关注 ...

  10. bzoj 3674&colon; 可持久化并查集加强版 (启发式合并&plus;主席树)

    Description Description:自从zkysb出了可持久化并查集后……hzwer:乱写能AC,暴力踩标程KuribohG:我不路径压缩就过了!ndsf:暴力就可以轻松虐!zky:…… ...