【BZOJ3771】Triple 生成函数+FFT
函数 生成 FFT
2023-09-11 14:15:27 时间
【BZOJ3771】Triple
Description
我们讲一个悲伤的故事。
从前有一个贫穷的樵夫在河边砍柴。
这时候河里出现了一个水神,夺过了他的斧头,说:
“这把斧头,是不是你的?”
樵夫一看:“是啊是啊!”
水神把斧头扔在一边,又拿起一个东西问:
“这把斧头,是不是你的?”
樵夫看不清楚,但又怕真的是自己的斧头,只好又答:“是啊是啊!”
水神又把手上的东西扔在一边,拿起第三个东西问:
“这把斧头,是不是你的?”
樵夫还是看不清楚,但是他觉得再这样下去他就没法砍柴了。
于是他又一次答:“是啊是啊!真的是!”
水神看着他,哈哈大笑道:
“你看看你现在的样子,真是丑陋!”
之后就消失了。
樵夫觉得很坑爹,他今天不仅没有砍到柴,还丢了一把斧头给那个水神。
于是他准备回家换一把斧头。
回家之后他才发现真正坑爹的事情才刚开始。
水神拿着的的确是他的斧头。
但是不一定是他拿出去的那把,还有可能是水神不知道怎么偷偷从他家里拿走的。
换句话说,水神可能拿走了他的一把,两把或者三把斧头。
樵夫觉得今天真是倒霉透了,但不管怎么样日子还得过。
他想统计他的损失。
樵夫的每一把斧头都有一个价值,不同斧头的价值不同。总损失就是丢掉的斧头价值和。
他想对于每个可能的总损失,计算有几种可能的方案。
注意:如果水神拿走了两把斧头a和b,(a,b)和(b,a)视为一种方案。拿走三把斧头时,(a,b,c),(b,c,a),(c,a,b),(c,b,a),(b,a,c),(a,c,b)视为一种方案。
Input
第一行是整数N,表示有N把斧头。
接下来n行升序输入N个数字Ai,表示每把斧头的价值。
Output
若干行,按升序对于所有可能的总损失输出一行x y,x为损失值,y为方案数。
Sample Input
4
4
5
6
7
4
5
6
7
Sample Output
4 1
5 1
6 1
7 1
9 1
10 1
11 2
12 1
13 1
15 1
16 1
17 1
18 1
样例解释
11有两种方案是4+7和5+6,其他损失值都有唯一方案,例如4=4,5=5,10=4+6,18=5+6+7.
5 1
6 1
7 1
9 1
10 1
11 2
12 1
13 1
15 1
16 1
17 1
18 1
样例解释
11有两种方案是4+7和5+6,其他损失值都有唯一方案,例如4=4,5=5,10=4+6,18=5+6+7.
HINT
所有数据满足:Ai<=40000
题解:当年以为这就是个桶,后来得知这玩意叫生成函数。
设所有斧头的生成函数为x,那么我们将x自乘1,2,3次,得到x,y,z,那么考虑每种情况被计算的次数。
x——a:1次
y——aa:1次,ab:2次
z——aaa:1次,aab:3次,abc:6次
那就把aa,aaa也求出来,用aa*b-aaa得到aab,就全统计出来了。
#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #define pi acos(-1.0) using namespace std; typedef long long ll; struct cp { double x,y; cp (double a,double b){x=a,y=b;} cp (){} cp operator + (cp a){return cp(x+a.x,y+a.y);} cp operator - (cp a){return cp(x-a.x,y-a.y);} cp operator * (cp a){return cp(x*a.x-y*a.y,x*a.y+y*a.x);} cp operator * (double a){return cp(x*a,y*a);} }n1[1<<19],n2[1<<19],n3[1<<19]; int n,m,top,len; int ans[1<<19]; ll s[1<<19]; void FFT(cp *a,int f) { int i,j,k,h; cp t; for(i=k=0;i<len;i++) { if(i>k) swap(a[i],a[k]); for(j=(len>>1);(k^=j)<j;j>>=1); } for(h=2;h<=len;h<<=1) { cp wn(cos(f*2*pi/h),sin(f*2*pi/h)); for(j=0;j<len;j+=h) { cp w(1,0); for(k=j;k<j+h/2;k++) t=w*a[k+h/2],a[k+h/2]=a[k]-t,a[k]=a[k]+t,w=w*wn; } } } int rd() { int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f; } int main() { n=rd(); int i,a; for(i=1;i<=n;i++) a=rd(),n1[a].x+=1,s[a]++,n2[a<<1].x+=1,n3[a*3].x+=1,m=max(m,a); for(len=1;len<=m*3;len<<=1); FFT(n1,1),FFT(n2,1),FFT(n3,1); for(i=0;i<len;i++) { cp x=n1[i],y=n2[i],z=n3[i]; n2[i]=((x*x)-y)*(1.0/2),n3[i]=((x*x*x)-(x*y*3.0)+(z*2.0))*(1.0/6); } FFT(n2,-1),FFT(n3,-1); for(i=0;i<len;i++) s[i]+=(ll)(n2[i].x/len+0.1)+(ll)(n3[i].x/len+0.1); for(i=0;i<len;i++) if(s[i]) ans[++top]=i; for(i=1;i<=top;i++) printf("%d %lld\n",ans[i],s[ans[i]]); return 0; }
相关文章
- Windows PE导出表编程2(重组导出表函数地址)
- SQL LEN() 函数
- PHP array_rand() 函数的特点,我们可以使用它来实现生成随机验证码的功能
- PHP生成订单号函数
- 相似 nginx 编译时生成函数链表
- 微信小程序 功能函数 touch触摸计时
- JNI学习积累之三 ---- 操作JNI函数以及复杂对象传递
- 转 mysql distinct函数 与 免密码登录 与 查看表的结构
- trait Monad:函数式编程类型系统本博客搜索关键字--类型升降
- Vuex之辅助函数
- Qt5 UI信号、槽自动连接的控件重名大坑(UI生成的槽函数存在一个隐患,即控件重名。对很复杂的控件,不要在 designer 里做提升,而是等到程序启动后,再动态创建,可以避免很多问题)
- 新的 CSS 伪类函数 :is() 和 :where()
- MySQL数据库获取汉字拼音的首字母函数
- 浅析前端如何做单元测试:jest与mocha对比、如何使用jest进行单元测试及持续监听、如何生成测试覆盖率报告、常用断言方法、如何测试异步函数
- 小知识随手记(十):多重重复解构对象、es6函数带默认参数时将生成声明作用域、一些注意点、动态设置getter/setter、mysql将字符串字段转为数字排序或比大小、pointer-events:none;属性
- 【C++快速上手】七、纯虚函数和抽象类学习笔记
- WindowsclientC/C++编程规范“建议”——函数
- HDOJ 2189 悼念512四川汶川大地震遇难者——来生一起走 【生成函数】
- 【SQL刷题】Day10----SQL高级过滤函数专项练习
- 【bzoj4001】[TJOI2015]概率论 生成函数+导数
- pytorch detach()截断反向传播、numpy()函数 item函数