博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 4609 3-idiots——FFT
阅读量:6819 次
发布时间:2019-06-26

本文共 1288 字,大约阅读时间需要 4 分钟。

题目:

答案就是随便选三条边的方案 - 不合法的方案。

不合法的方案就是算出 x+y = k 的方案数 g[ k ],对于每个长度 z ,不合法方案+=\( \sum\limits_{k=0}^{z}g[k] \)

注意 FFT 之后偶数项 k 算上了取长度为 k/2 的同一条边两遍的方案,要去重。

随便选三条边的 n*(n-1)*(n-2) 会把同一个 x , y , z 算6遍,而枚举 z 会把同一个 x , y , z 算两遍,所以要乘3。

注意减去的时候乘上长度为 z 的边的个数。

#include
#include
#include
#include
#define db double#define ll long longusing namespace std;const int N=1e5+5,M=(1<<18)+5;const db pi=acos(-1);int T,n,len,r[M],f[N];struct cpl{db x,y;}a[M],I;cpl operator+ (cpl a,cpl b){
return (cpl){a.x+b.x,a.y+b.y};}cpl operator- (cpl a,cpl b){
return (cpl){a.x-b.x,a.y-b.y};}cpl operator* (cpl a,cpl b){
return (cpl){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}int Mx(int a,int b){
return a>b?a:b;}int rdn(){ int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){
if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret;}void fft(cpl *a,bool fx){ for(int i=0;i
>1; cpl wn=(cpl){ cos(pi/m),fx?-sin(pi/m):sin(pi/m) }; for(int i=0;i
>1;i
>1]>>1)+((i&1)?j:0); fft(a,0); for(int i=0;i
>1]:0) )*3; ans-=lj*f[i];//*f[i]!! } printf("%.7f\n",(db)ans/sm); } return 0;}

 

转载于:https://www.cnblogs.com/Narh/p/10099775.html

你可能感兴趣的文章
[数据结构]插入排序与希尔排序
查看>>
如何高效利用GitHub
查看>>
Server-sent Event 简单介绍
查看>>
nginx 常用的几个命令
查看>>
解决命令行的乱码以及编码的问题
查看>>
Linux 程序获取环境变量
查看>>
vim设置括号自动补全
查看>>
windows环境eclipse开发C++程序
查看>>
svn 常用命令总结
查看>>
Tomcat全攻略
查看>>
make: *** linux-2.6.36.4/arch/arm: Is a directo...
查看>>
android http连接阻塞超时问题
查看>>
异常处理
查看>>
线性插值针对位置量和角度量
查看>>
关于方法快的理解
查看>>
sublime text2配置
查看>>
library 'system/lib/libhoudini.so' not find
查看>>
TCP UDP socket debug tools
查看>>
网页矢量图在组态软件中的应用
查看>>
disabled by the php.ini setting phar.readonly
查看>>