2019.01.02 bzoj3513: [MUTC2013]idiots(fft)

时间:2022-10-03 18:08:35

传送门

fftfftfft经典题。

题意简述:给定nnn个长度分别为aia_iai​的木棒,问随机选择3个木棒能够拼成三角形的概率。


思路:考虑对于木棒构造出生成函数然后可以fftfftfft出两个木棒能够生成的边长和的生成函数 注意去重

我们还可以在读入的时候顺便统计出cnticnt_icnti​表示长度≤i\le i≤i的木棒有多少根。

然后可以算出选出3个木棒不能拼成三角形的方案数,简单容斥一下再算出总选法数即可。

代码:

#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
	int ans=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans;
}
typedef long long ll;
struct Cp{
	double x,y;
	Cp(double x=0.0, double y=0.0):x(x),y(y){};
	friend inline Cp operator+(const Cp&a,const Cp&b){return (Cp){a.x+b.x,a.y+b.y};}
	friend inline Cp operator-(const Cp&a,const Cp&b){return (Cp){a.x-b.x,a.y-b.y};}
	friend inline Cp operator*(const double&a,const Cp&b){return (Cp){a*b.x,a*b.y};}
	friend inline Cp operator*(const Cp&a,const Cp&b){return (Cp){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
	friend inline Cp operator/(const Cp&a,const double&b){return (Cp){a.x/b,a.y/b};}
};
int lim,tim;
vector<Cp>A,B;
vector<int>pos;
inline void init(const int&up){
	lim=1,tim=0;
	while(lim<=up)lim<<=1,++tim;
	pos.resize(lim),A.resize(lim),B.resize(lim),pos[0]=0;
	for(ri i=0;i<lim;++i)pos[i]=(pos[i>>1]>>1)|((i&1)<<(tim-1));
}
const double pi=acos(-1.0);
inline void fft(vector<Cp>&a,const int&type){
	for(ri i=0;i<lim;++i)if(i<pos[i])swap(a[i],a[pos[i]]);
	for(ri mid=1;mid<lim;mid<<=1){
		Cp wn(cos(pi/mid),type*sin(pi/mid));
		for(ri j=0,len=mid<<1;j<lim;j+=len){
			Cp w(1,0),a0,a1;
			for(ri k=0;k<mid;++k,w=w*wn){
				a0=a[j+k],a1=a[j+k+mid]*w;
				a[j+k]=a0+a1,a[j+k+mid]=a0-a1;
			}
		}
	}
	if(type==-1)for(ri i=0;i<lim;++i)a[i]=a[i]/lim;
}
struct poly{
	vector<Cp>a;
	poly(int k=0,int x=0){a.resize(k+1),a[k]=x;}
	inline Cp&operator[](const int&k){return a[k];}
	inline const Cp&operator[](const int&k)const{return a[k];}
	inline int deg()const{return a.size()-1;}
	inline poly extend(const int&k){poly ret=*this;return ret.a.resize(k+1),ret;}
	friend inline poly operator*(const poly&a,const poly&b){
		int n=a.deg(),m=b.deg();
		init(n+m);
		poly ret(lim);
		for(ri i=0;i<=n;++i)A[i]=a[i];
		for(ri i=0;i<=m;++i)B[i]=b[i];
		for(ri i=n+1;i<lim;++i)A[i]=(0,0);
		for(ri i=m+1;i<lim;++i)B[i]=(0,0);
		fft(A,1),fft(B,1);
		for(ri i=0;i<lim;++i)A[i]=A[i]*B[i];
		return fft(A,-1),ret.a=A,ret;
	}
};
const int N=1e5+5;
int n,x[N],mx;
poly a;
ll sum,cnt[N*2];
int main(){
	for(ri tt=read();tt;--tt){
		fill(cnt,cnt+mx+1,0);
		n=read(),mx=0;
		for(ri i=1;i<=n;++i)mx=max(mx,x[i]=read()),++cnt[x[i]];
		for(ri i=1;i<=2*mx;++i)cnt[i]+=cnt[i-1];
		a=a.extend(mx);
		for(ri i=0;i<=mx;++i)a[i]=(0,0);
		for(ri i=1;i<=n;++i)a[x[i]].x+=1;
		a=a*a,mx<<=1;
		for(ri i=1;i<=n;++i)a[x[i]<<1].x-=1;
		sum=(ll)n*(n-1)*(n-2);
		for(ri i=1;i<=mx;++i)sum-=(ll)(a[i].x+0.5)*(cnt[i-1]-2);
		sum=(ll)n*(n-1)*(n-2)/6-sum/2;
		printf("%.7LF\n",(long double)(sum*6.0)/((long double)n*(n-1)*(n-2)));
	}
	return 0;
}

2019.01.02 bzoj3513: [MUTC2013]idiots(fft)的更多相关文章

  1. 2019&period;01&period;02 bzoj5300&colon; &lbrack;Cqoi2018&rsqb;九连环(fft优化高精&plus;快速幂)

    传送门 题意不好描述(自己看样例解释) 首先可以推出一个递推式:fn=fn−1+2fn−2+1f_n=f_{n-1}+2f_{n-2}+1fn​=fn−1​+2fn−2​+1 然后可以构造两个等式: ...

  2. 2019&period;01&period;02 poj3046 Ant Counting(生成函数&plus;dp)

    传送门 生成函数基础题. 题意:给出nnn个数以及它们的数量,求从所有数中选出i∣i∈[L,R]i|i\in[L,R]i∣i∈[L,R]个数来可能组成的集合的数量. 直接构造生成函数然后乘起来f(x) ...

  3. 机器学习实战(Machine Learning in Action)学习笔记————02&period;k-邻近算法(KNN)

    机器学习实战(Machine Learning in Action)学习笔记————02.k-邻近算法(KNN) 关键字:邻近算法(kNN: k Nearest Neighbors).python.源 ...

  4. 快速傅里叶(FFT)的快速深度思考

    关于按时间抽取快速傅里叶(FFT)的快速理论深度思考 对于FFT基本理论参考*或百度百科. 首先谈谈FFT的快速何来?大家都知道FFT是对DFT的改进变换而来,那么它究竟怎样改进,它改进的思想在 ...

  5. 【BZOJ3527】力(FFT)

    [BZOJ3527]力(FFT) 题面 Description 给出n个数qi,给出Fj的定义如下: \[Fj=\sum_{i<j}\frac{q_i q_j}{(i-j)^2 }-\sum_{ ...

  6. 【BZOJ4827】【HNOI2017】礼物(FFT)

    [BZOJ4827][HNOI2017]礼物(FFT) 题面 Description 我的室友最近喜欢上了一个可爱的小女生.马上就要到她的生日了,他决定买一对情侣手 环,一个留给自己,一 个送给她.每 ...

  7. FFT&sol;NTT总结&plus;洛谷P3803 【模板】多项式乘法(FFT)(FFT&sol;NTT)

    前言 众所周知,这两个东西都是用来算多项式乘法的. 对于这种常人思维难以理解的东西,就少些理解,多背板子吧! 因此只总结一下思路和代码,什么概念和推式子就靠巨佬们吧 推荐自为风月马前卒巨佬的概念和定理 ...

  8. 【BZOJ4503】两个串(FFT)

    [BZOJ4503]两个串(FFT) 题面 给定串\(S\),以及带通配符的串\(T\),询问\(T\)在\(S\)中出现了几次.并且输出对应的位置. \(|S|,|T|<=10^5\),字符集 ...

  9. 【BZOJ4259】残缺的字符串(FFT)

    [BZOJ4259]残缺的字符串(FFT) 题面 给定两个字符串\(|S|,|T|\),两个字符串中都带有通配符. 回答\(T\)在\(S\)中出现的次数. \(|T|,|S|<=300000\ ...

随机推荐

  1. 【个人笔记】《知了堂》MySQL中的数据类型

    MySQL中的数据类型 1.整型 MySQL数据类型 含义(有符号) tinyint(m) 1个字节  范围(-128~127) smallint(m) 2个字节  范围(-32768~32767) ...

  2. PHP删除目录及目录下所有文件

    /** * 删除目录及目录下所有文件或删除指定文件 * @param str $path 待删除目录路径 * @param int $delDir 是否删除目录,1或true删除目录,0或false则 ...

  3. RT-SA-2019-007 Code Execution via Insecure Shell Functiongetopt&lowbar;simple

    Advisory: Code Execution via Insecure Shell Function getopt_simple RedTeam Pentesting discovered tha ...

  4. spring aop 加在Controller层造成类初始化两遍

    写一个测试项目,在配置动态数据源的时候采用的AOP切面到Controller层中,根据参数判断是否切合数据源,结果发现,每次Controller层的类都会初始化两次! 后来测试发现,把切面放到Serv ...

  5. 随机森林学习-2-sklearn

    # -*- coding: utf-8 -*- """ RandomForestClassifier skleran的9个模型在3份数据上的使用. 1. 知识点: skl ...

  6. 六招让你的Ubuntu马上提速

    Chris Hoffman Ubuntu的启动速度非常快,按了开机键之后很快就进入桌面.但我们仍然可以充分利用内存,通过多种方法让开机速度更快.某些方法真的可以提速,对于旧电脑的效果尤其明显. 选用轻 ...

  7. dex2jar 和 jd-gui 的安装与使用(转)

    出处:https://blog.csdn.net/katrinawj/article/details/80016315 将APK直接解压(修改后缀名为.zip,然后解压)后,可以看到目录下包含一个cl ...

  8. JS实现数字千位符格式化方法

    /** * [number_format 参数说明:] * @param {[type]} number [number:要格式化的数字] * @param {[type]} decimals [de ...

  9. sysstat工具

    sysstat工具可以监控系统的IO,CPU,SWAP,LOAD,NETWORK,DISK 安装后,系统会生成定时任务脚本 路径:/etc/cron.d/sysstat 内容: # Run syste ...

  10. 02-JAVA 初始化

    构造器 概念:在创建对象时被自动调用的方法,构造器采用和类名一样的名称 创建对象时,会为其分配存储空间,并调用相应的构造器进行初始化.这就确保了在操作对象之前,这个对象已经被恰当的初始化了. 不接受仁 ...