HDU 4609 FFT

?題目大意

給定n條邊的邊值,求任意取三條邊能組成三角形的概率

?

這里概率 P = valid/tot

tot = (n-2)*(n-1)*n/6是沒問題的

valid表示合法的方式

先考慮,任意兩條邊組合形成方法的總數

因為邊值在100000的范圍內,這里組合用fft計算

得到最后形成和為 i 的兩條邊的方法數為 num[i]

這里計算后要記得減去取兩條相同邊的情況,還有 取 3,4 和 4,3是一樣的,要記得除以2

最后跑個n的循環,每次將當前邊作為排序后(主要是因為有長度相同的邊才這么考慮)次序最大的邊,然后保證得到的和是兩條在它前面的邊組成的

這個計算就需要求個總方法數的前綴和了

取到所有和大于當前邊的方法數,減去由兩條比它大的邊組成的情況(n-i)*(n-i-1)/2,一個比他大一個比他小組成的(n-i)*(i-1),還有它其余任意一條邊組成的(n-1)

?

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <iostream>
  5 #include <algorithm>
  6 using namespace std;
  7 #define N 100005
  8 #define ll long long
  9 const double PI = acos(-1.0);
 10 
 11 int n , a[N] , cnt[N] ;
 12 ll num[N<<2] , sum[N<<2];
 13 
 14 struct complex{
 15     double r , i;
 16     complex(double r=0 , double i=0):r(r),i(i){}
 17     complex operator+(const complex &a) const{
 18         return complex(r+a.r , i+a.i);
 19     }
 20     complex operator-(const complex &a) const{
 21         return complex(r-a.r , i-a.i);
 22     }
 23     complex operator*(const complex &a) const{
 24         return complex(r*a.r-i*a.i , r*a.i+i*a.r);
 25     }
 26 };
 27 
 28 void change(complex y[] , int len)
 29 {
 30     int i,j,k;
 31     for(i=1 , j=len/2 ; i<len-1 ; i++){
 32         if(i<j) swap(y[i],y[j]);
 33         k = len/2;
 34         while(j>=k){
 35             j-=k;
 36             k/=2;
 37         }
 38         if(j<k) j+=k;
 39     }
 40 }
 41 
 42 void fft(complex y[] , int len , int on)
 43 {
 44     change(y , len);
 45     for(int i=2 ; i<=len ; i<<=1){
 46         complex wn(cos(-on*2*PI/i) , sin(-on*2*PI/i));
 47         for(int j=0 ; j<len ; j+=i){
 48             complex w(1,0);
 49             for(int k=j ; k<j+i/2 ; k++){
 50                 complex u = y[k];
 51                 complex t = w*y[k+i/2];
 52                 y[k] = u+t;
 53                 y[k+i/2] = u-t;
 54                 w = w*wn;
 55             }
 56         }
 57     }
 58     if(on==-1)
 59         for(int i=0 ; i<len ; i++)
 60             y[i].r /= len;
 61 
 62 }
 63 complex x[N<<2];
 64 
 65 int main()
 66 {
 67    // freopen("a.in" , "r" , stdin);
 68     int T;
 69     scanf("%d" , &T);
 70     while(T--){
 71         scanf("%d" , &n);
 72         int mx = 0;
 73         memset(cnt , 0 , sizeof(cnt));
 74         for(int i=1 ; i<=n ; i++){
 75             scanf("%d" , &a[i]);
 76             cnt[a[i]]++ , mx=max(mx , a[i]);
 77         }
 78         int len = 1;
 79         while(len<2*(mx+1)) len<<=1;
 80         for(int i=0 ; i<=mx ; i++) x[i] = complex(cnt[i] , 0);
 81         for(int i=mx+1 ; i<len ; i++) x[i] = complex(0 , 0);
 82         fft(x , len , 1);
 83         for(int i=0 ; i<len ; i++)
 84             x[i] = x[i]*x[i];
 85         fft(x , len , -1);
 86         for(int i=0 ; i<len ; i++) num[i] = (ll)(x[i].r+0.5);
 87         for(int i=1 ; i<=n ; i++) num[a[i]+a[i]]--;
 88         for(int i=0 ; i<len ; i++){
 89             num[i]/=2;
 90             if(i) sum[i] = sum[i-1]+num[i];
 91         }
 92         ll ans = 0;
 93         sort(a+1 , a+n+1);
 94         for(int i=1 ; i<=n ; i++){
 95             ll val = sum[len-1]-sum[a[i]];
 96             val = val - (n-1);
 97             val = val - (ll)(n-i)*(i-1);
 98             val = val - (ll)(n-i)*(n-i-1)/2;
 99           //  cout<<i<<" "<<a[i]<<" "<<sum[len-1]-sum[a[i]]<<" "<<val<<endl;
100             ans = ans+val;
101         }
102         printf("%.7f\n" , ans*6.0/((ll)n*(n-1)*(n-2)));
103     }
104     return 0;
105 }

?

轉載于:https://www.cnblogs.com/CSU3901130321/p/4910831.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/258154.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/258154.shtml
英文地址,請注明出處:http://en.pswp.cn/news/258154.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

《日志管理與分析權威指南》一2.3 良好日志記錄的標準

本節書摘來華章計算機《日志管理與分析權威指南》一書中的第2章 &#xff0c;第2.3節&#xff0c;&#xff08;美&#xff09; Anton A. Chuvakin Kevin J. Schmidt Christopher Phillips 著 姚 軍 簡于涵 劉 暉 等譯更多章節內容可以訪問云棲社區“華章計算機”公眾號查…

Python【01】【基礎部分】- A

一、WHATS PYTHON ? 1、python 簡介 Python&#xff08;英語發音&#xff1a;/?pa?θ?n/&#xff09;, 是一種面向對象、解釋型計算機程序設計語言&#xff0c;由Guido van Rossum于1989年發明&#xff0c;第一個公開發行版發行于1991年。Python是純粹的自由軟件&#xff0…

java的自增自減_Java中自增和自減操作符(++/--)的那些事

自增()和自減(--)運算符在JAVA語言中存在著很多運算符&#xff0c;但是在實際開發中我們或許很少用到它們&#xff0c;在初次學習中卻時常出現它們的身影&#xff0c;對于這些運算符的含義和用法&#xff0c;是否還記得呢&#xff1f;1. 概述自增操作符()和自減操作符(--)是對變…

Finished yeah!

終于到了最后的博客階段&#xff0c;這時候才知道博客此時此刻是多么的愜意&#xff0c;它成了書寫心聲的自由平臺&#xff01;耗時一天完成這作業說起來也是蠻辛苦的&#xff0c;編譯器需要新裝&#xff0c;IDE需要熟悉&#xff0c;當然最主要的是之前淺入淺出的C功底在此次作…

《Python語言程序設計》——1.6 開始學習Python

本節書摘來自華章計算機《Python語言程序設計》一書中的第1章&#xff0c;第1.6節,作者&#xff1a;&#xff3b;美&#xff3d;梁勇&#xff08;Y. Daniel Liang&#xff09; 更多章節內容可以訪問云棲社區“華章計算機”公眾號查看。 1.6 開始學習Python 關鍵點&#xff1a;…

Tomcat性能調優

1、集成apache 雖然Tomcat也可以作web服務器&#xff0c;但是處理靜態html的速度比不上apache&#xff0c;且其作為web服務器的功能遠不如Apache&#xff0c;因此把apache和tomcat集成起來&#xff0c;講html和jsp功能部分進行明確的分工&#xff0c;讓tomcat只處理jsp部分&…

【轉】sip中的subscribe和notify擴展應用技術

http://blog.csdn.net/hwz119/article/details/3965322轉載于:https://www.cnblogs.com/matthew-2013/p/4917207.html

再讀《被神化的框架》

開發框架&#xff0c;構件&#xff0c;組件非常地多&#xff0c;而且&#xff0c;趨勢是越來越多&#xff0c;特別是在java中。當然也不是說其它平臺的少。而特別是框架越來越被神化了&#xff0c;似乎用之解決一切問題&#xff0c;不用就要敲壞鍵盤。對于老衲這樣的打字員來說…

河南推出近萬億PPP投資計劃 鄭州實現智慧城市全覆蓋

1 近萬億PPP項目啟動 眼下&#xff0c;國內財經新聞的熱點聚焦在PPP開發上&#xff0c;這與PPP支撐國內經濟平衡運行的一支強勁力量正被政府看好。就連二級市場也出現了PPP概念的搶籌現象。 9月27日&#xff0c;股市再一次遭遇拋售&#xff0c;大盤創出階段性新低&#xff0c;然…

java基礎實例代碼_Java基礎實例

打印等腰三角形代碼public class ForForTest{public static void main(String []args){for(int x0;x<5;x){for(int yx1;y<5;y){System.out.print(" ");}for(int z0;zSystem.out.print("* ");}System.out.println();}}}折半查找代碼&#xff1a;//練習…

###《Effective STL》--Chapter3

點擊查看Evernote原文。 #author: gr #date: 2014-09-13 #email: forgeruigmail.com Chapter3 關聯容器 Topic 22: 切勿直接修改set或multiset中的鍵 修改元素的值可以通過下面五步操作&#xff0c;避免作類型轉換。 struct IDNumberLess : public binary…

如何獲取網絡資源?

# encodingutf-8 #python 2.7.10 #xiaodeng #如何獲取網絡資源&#xff1f; #HTTP權威指南 26頁#url就是因特網資源的標準化名稱&#xff0c;他指向每一條電子信息&#xff0c;告訴你他們位于何處&#xff0c;以及如何與之交互。 #URL是瀏覽器尋找信息時所需的資源位置。 #一個…

Loadrunner多服務器連接問題

今天用想增加一個壓力機,在服務器管理列表里怎么也連不上,后來解決方法如下:1. 關閉所有loadrunner組件,并手動結束lr_開頭的進程2.找到惠普loadrunner安裝目錄(C:\Program Files\HP\LoadRunner\bin),手動運行magentproc.exe即可最新內容請見作者的GitHub頁&#xff1a;http://…

java 常量存儲_JAVA?存儲空間 寄存器 堆棧 堆 常量存儲 非RAM存儲

&#xff11;.寄存器這是最快的存儲區&#xff0c;因為它位于處理器內部&#xff0c;數量極其有限&#xff0c;所以寄存器根據需求進行分配&#xff0c;你不能直接控制&#xff0c;也不能在程序中感 覺到寄存器存在的任何跡象。2.堆棧位于通用RAM(隨機訪問存儲器)中&#xff0…

物聯網安防技術融合在細分領域的應用分析

物聯網的核心是業務和應用的創新。物聯網技術與智能化技術的深度融合&#xff0c;加快了行業的智能化發展&#xff0c;促使了行業需求在應用層上的落地。安防技術架構是物聯網架構的一個子集&#xff0c;傳統安防是一個相對保守的行業。現代安防和物聯網在業務和技術上的融合發…

一個強大的工具來模擬數百萬??并發用戶負載測試:Gryphon

Gryphon是由網易自主研發的能夠模擬千萬級別并發用戶的一個軟件&#xff0c;目的是能夠用較少的資源來模擬出大量并發用戶&#xff0c;并且能夠更加真實地進行壓力測試&#xff0c; 以解決網絡消息推送服務方面的壓力測試的問題和傳統壓力測試的問題。Gryphon分為兩個程序&…

java 反射與泛型_Java基礎系列 - 泛型和反射機制

package com.test5;import java.lang.reflect.Field;import java.lang.reflect.Method;/*** Java泛型和反射機制(泛型的好處 代碼安全簡單&#xff0c;自動裝箱拆箱&#xff0c;提高代碼的重用率)*/public class test5 {public static void main(String[] args) {Employer empl…

Linux環境下的Popush部署——張凱

完成情況&#xff1a; 已按照相關部署文檔完成了所有任務&#xff0c;包括軟件包的安裝與配置&#xff0c;以及對各種開發語言的支持&#xff0c;以及gdb的調試功能的支持 遇到的主要問題&#xff1a; 由于從大二以來我基本上所有的開發工作都是在Linux下做的&#xff0c;因此對…

【c++】標準模板庫STL入門簡介與常見用法

一、STL簡介 1、什么是STL STL&#xff08;Standard Template Library&#xff09;標準模板庫&#xff0c;主要由容器、迭代器、算法、函數對象、內存分配器和適配器六大部分組成。STL已是標準C的一部分&#xff0c;使用STL開發系統可以提高開發效率。 2、容器&#xff08;Cont…

強連通分量(學習心得)

定義&#xff1a;有向圖強連通分量&#xff1a;在有向圖G中&#xff0c;如果兩個頂點vi,vj間&#xff08;vi>vj&#xff09;有一條從vi到vj的有向路徑&#xff0c;同時還有一條從vj到vi的有向路徑&#xff0c;則稱兩個頂點強連通如果有向圖G的每兩個頂點都強連通&#xff0c…