2018.11.18 spoj Triple Sums(容斥原理+fft)
2024-10-20 02:13:45
传送门
这次fftfftfft乱搞居然没有被卡常?
题目简述:给你nnn个数,每三个数ai,aj,ak(i<j<k)a_i,a_j,a_k(i<j<k)ai,aj,ak(i<j<k)组成的所有和以及这些和出现的次数。
读完题直接让我联想到了昨天写过的一道用fftfftfft优化点分治合并的题
,这不是差不多嘛?
只是这一次的容斥要麻烦一些。
我们令原数列转化成的系数序列为{an}\{a_n\}{an}
那么如果允许重复答案就应该是an3a_n^3an3
然后展开式子。
我们需要容斥掉的就是有3个数相同的和有2个数相同的。
这个时候已经可以用fftfftfft了。
但是还可以进一步优化。
如何优化?
观察到有两个数相同的其实可以再用一次容斥求出。
因为两个数相同的个数是等于至少两个数相同的个数扣去有三个数相同的个数的。
这样可以优化更多常数。
剩下就是fftfftfft的事啦。
代码:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
typedef long long ll;
const int N=(1<<17)+5,delta=20000;
const double pi=acos(-1.0);
struct Complex{
double x,y;
inline Complex operator+(const Complex&b){return (Complex){x+b.x,y+b.y};}
inline Complex operator-(const Complex&b){return (Complex){x-b.x,y-b.y};}
inline Complex operator*(const Complex&b){return (Complex){x*b.x-y*b.y,y*b.x+x*b.y};}
inline Complex operator/(const double&b){return (Complex){x/b,y/b};}
}a[N],b[N],c[N];
int n,lim,tim,A[N],B[N],C[N],pos[N];
inline void fft(Complex *a,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){
Complex wn=(Complex){cos(pi/mid),type*sin(pi/mid)};
for(ri j=0,len=mid<<1;j<lim;j+=len){
Complex w=(Complex){1,0};
for(ri k=0;k<mid;++k,w=w*wn){
Complex 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;
}
inline void init(){
lim=1<<17,tim=17;
for(ri i=0;i<lim;++i)pos[i]=(pos[i>>1]>>1)|((i&1)<<(tim-1));
}
int main(){
freopen("lx.in","r",stdin);
n=read(),init();
for(ri i=1,val;i<=n;++i)val=read()+delta,++A[val],++B[val*2],++C[val*3];
for(ri i=0;i<lim;++i)a[i].x=A[i],b[i].x=B[i],c[i].x=C[i];
fft(a,1),fft(b,1);
for(ri i=0;i<lim;++i)c[i]=a[i]*(a[i]*a[i]-(Complex){3,0}*b[i]);
fft(c,-1);
for(ri i=0;i<lim;++i){
ll cnt=((ll)(c[i].x+0.5)+2*C[i])/6;
if(cnt)cout<<i-3*delta<<" : "<<cnt<<'\n';
}
return 0;
}
最新文章
- Azure机器学习入门(一)
- angular源码阅读的起点,setupModuleLoader方法
- HTML前端--各种小案例
- Struts2标签<;s:textfield/>;
- QQ音乐无损歌曲接口api
- c++描述将一个2进制数转化成10进制数(用到初始化栈,进栈,入栈)
- error “base class has incomplete type”
- Spark计算模型-RDD介绍
- 滚动页面时DIV到达顶部时固定在顶部
- Api 和 Spi
- 【Python之路】第十一篇--CSS
- 实现Spring RESTful服务的SSL
- [BZOJ]1019 汉诺塔(SHOI2008)
- OpenCV kmeans代码
- Bootstrap富文本编辑器-bootstrap-wysiwyg
- [CodeForces - 463B] Caisa and Pylons
- keyup在移动端失效解决方法
- 黄聪:Navicat for MySQL的1577错误解决
- POJ 2823 UESTCoj 1221 Sliding Window 单调队列 经典入门题
- Encode Adjacent Letters