BZOJ 3771: Triple(FFT+容斥)

时间:2022-09-21 23:26:58

题面

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

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.

HINT

所有数据满足:Ai<=40000

解题思路

  \(FFT\),还是比较套路的那种,但是得加一个容斥。设\(f[i]\)表示\(i\)这个权值出现的次数,\(g[i]\)表示每个物品\(*2\)的权值出现次数,\(h[i]\)表示每个物品\(*3\)的权值出现次数。那么\(f\)卷\(f\)就是两个物品一共构成的权值,再卷一个\(f\)就是三个物品构成的权值,但这些多算了一部分,用容斥减去。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define int long long using namespace std;
const int MAXN = 40005*3;
const double Pi = acos(-1); inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return f?x:-x;
} inline int max(int x,int y){
return x>y?x:y;
} struct Complex{
double x,y;
Complex(double xx=0,double yy=0){
x=xx;y=yy;
}
}f[MAXN<<1],g[MAXN<<1],h[MAXN<<1]; Complex operator+(Complex A,Complex B){return Complex(A.x+B.x,A.y+B.y);}
Complex operator-(Complex A,Complex B){return Complex(A.x-B.x,A.y-B.y);}
Complex operator*(Complex A,Complex B){return Complex(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);} int n,a[MAXN],cnt[MAXN],rev[MAXN<<1],limit=1,mx,ans[MAXN],cnt2[MAXN],cnt3[MAXN]; void FFT(Complex *f,int type){
for(int i=0;i<limit;i++) if(i<rev[i]) swap(f[i],f[rev[i]]);
Complex Wn,w,tmp;int len;
for(int i=2;i<=limit;i<<=1){
len=i>>1;Wn=Complex(cos(Pi/len),type*sin(Pi/len));
for(int j=0;j<limit;j+=i){
w=Complex(1,0);
for(int k=j;k<j+len;k++){
tmp=w*f[k+len];f[k+len]=f[k]-tmp;
f[k]=f[k]+tmp;w=w*Wn;
}
}
}
} signed main(){
n=rd();
for(int i=1;i<=n;i++){
a[i]=rd();cnt[a[i]]++;cnt2[a[i]*2]++;cnt3[a[i]*3]++;
mx=max(mx,a[i]);ans[a[i]]++;
}
for(int i=1;i<=mx;i++) f[i].x=cnt[i];mx*=3;
while(limit<=mx*2) limit<<=1;
for(int i=0;i<limit;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?(limit>>1):0);
FFT(f,1);
for(int i=0;i<limit;i++) g[i]=f[i],f[i]=f[i]*f[i];
FFT(f,-1);
for(int i=1;i<=mx;i++) ans[i]+=((int)(f[i].x/limit+0.5)-cnt2[i])/2;
for(int i=1;i<=mx;i++) f[i].x/=limit;
FFT(f,1);
for(int i=0;i<limit;i++) f[i]=f[i]*g[i];
FFT(f,-1);
for(int i=0;i<limit;i++) h[i].x=cnt2[i];
FFT(h,1);
for(int i=0;i<limit;i++) h[i]=h[i]*g[i];
FFT(h,-1);
for(int i=1;i<=mx;i++)
ans[i]+=((int)(f[i].x/limit+0.5)-3*(int)(h[i].x/limit+0.5)+2*cnt3[i])/6;
for(int i=1;i<=mx;i++)
if(ans[i]) printf("%lld %lld\n",i,ans[i]);
return 0;
}

BZOJ 3771: Triple(FFT+容斥)的更多相关文章

  1. 【BZOJ 3771】 3771&colon; Triple &lpar;FFT&plus;容斥&rpar;

    3771: Triple Time Limit: 20 Sec  Memory Limit: 64 MBSubmit: 547  Solved: 307 Description 我们讲一个悲伤的故事. ...

  2. &lbrack;BZOJ 3771&rsqb; Triple&lpar;FFT&plus;容斥原理&plus;生成函数&rpar;

    [BZOJ 3771] Triple(FFT+生成函数) 题面 给出 n个物品,价值为别为\(w_i\)且各不相同,现在可以取1个.2个或3个,问每种价值和有几种情况? 分析 这种计数问题容易想到生成 ...

  3. BZOJ 3771 Triple FFT&plus;容斥原理

    解析: 这东西其实就是指数型母函数? 所以刚开始读入的值我们都把它前面的系数置为1. 然后其实就是个多项式乘法了. 最大范围显然是读入的值中的最大值乘三,对于本题的话是12W? 用FFT优化的话,达到 ...

  4. bzoj 3771 Triple FFT 生成函数&plus;容斥

    Triple Time Limit: 20 Sec  Memory Limit: 64 MBSubmit: 847  Solved: 482[Submit][Status][Discuss] Desc ...

  5. bzoj 3771 Triple——FFT

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3771 把方案作为系数.值作为指数,两项相乘就是系数相乘.指数相加,符合意义. 考虑去重.先自 ...

  6. bzoj 3771 Triple —— FFT

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3771 令多项式的系数是方案数,次数是值: 设 a(x) 为一个物品的多项式,即 a[w[i] ...

  7. BZOJ 3771 Triple ——FFT

    直接暴力卷积+统计就可以了. 去重比较复杂. 其实也不复杂,抄吧! 反正AC了. #include <map> #include <cmath> #include <qu ...

  8. spoj TSUM - Triple Sums fft&plus;容斥

    题目链接 首先忽略 i < j < k这个条件.那么我们构造多项式$$A(x) = \sum_{1现在我们考虑容斥:1. $ (\sum_{}x)^3 = \sum_{}x^3 + 3\s ...

  9. BZOJ 3771&colon; Triple&lpar;生成函数 FFT&rpar;

    Time Limit: 20 Sec  Memory Limit: 64 MBSubmit: 911  Solved: 528[Submit][Status][Discuss] Description ...

随机推荐

  1. C&num; 破解 Reflector8&period;5

    一.分析 破解.net .dll,可以使用reflector,但官方提供的reflector是需要购买的,因此,破解reflector势在必行. 二.破解Reflector具体步骤 下面为详细的破解步 ...

  2. TP-LINK WR941 DD-WRT刷回OpenWRT及OpenWRT刷回原厂固件

    1.DD-Wrt 刷回 OpenWrt A.从官网下载固件: root@TL-DDWRT:/tmp# wget http://downloads.openwrt.org/barrier_breaker ...

  3. List&lt&semi;T&gt&semi;与Dictionary&lt&semi;string&comma;T&gt&semi;频繁检索的性能差距

    一直对LINQ简洁高效的语法青睐有加,对于经常和资料库,SQL语法打交道的C#开发者来说,LINQ无疑是一个非常不错的选择,当要在List<T>(T为一个普通对象)集合中查找满足某些条件的 ...

  4. svg&lpar;可缩放矢量图形&rpar;

    入门推荐: http://www.ruanyifeng.com/blog/2018/08/svg.html (教程) http://www.runoob.com/svg/svg-reference.h ...

  5. NodePort 只能在node节点*问,外部无法访问

    创建了一个NodePort类型的jenkins service,node port 30000,node节点ip为192.168.56.101, 在node节点上通过浏览器能正常访问http://19 ...

  6. winform窗体 小程序【打开多个窗体、窗体之间传值、打开唯一窗体】

    1.打开多个窗体 2.窗体之间的传值 3打开唯一窗体

  7. 批处理修改Hosts文件

    @echo off set stHosts=127.0.0.1 www.XXX.com FOR /F "eol=# tokens=1 delims=" %%i in (%Syste ...

  8. winform程序开机自动启动

    app.manifest <requestedExecutionLevel level="requireAdministrator" uiAccess="false ...

  9. XML Web Service架构图

  10. IOC容器02

    获取xml文件路径,使用IO读取xml文件,使用Document对象解析xml文件,将xml中的bean的信息注册到BeanDefinition类,将BeanDefinition保存到一个map中:该 ...