题面
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+容斥)的更多相关文章
-
【BZOJ 3771】 3771: Triple (FFT+容斥)
3771: Triple Time Limit: 20 Sec Memory Limit: 64 MBSubmit: 547 Solved: 307 Description 我们讲一个悲伤的故事. ...
-
[BZOJ 3771] Triple(FFT+容斥原理+生成函数)
[BZOJ 3771] Triple(FFT+生成函数) 题面 给出 n个物品,价值为别为\(w_i\)且各不相同,现在可以取1个.2个或3个,问每种价值和有几种情况? 分析 这种计数问题容易想到生成 ...
-
BZOJ 3771 Triple FFT+容斥原理
解析: 这东西其实就是指数型母函数? 所以刚开始读入的值我们都把它前面的系数置为1. 然后其实就是个多项式乘法了. 最大范围显然是读入的值中的最大值乘三,对于本题的话是12W? 用FFT优化的话,达到 ...
-
bzoj 3771 Triple FFT 生成函数+容斥
Triple Time Limit: 20 Sec Memory Limit: 64 MBSubmit: 847 Solved: 482[Submit][Status][Discuss] Desc ...
-
bzoj 3771 Triple——FFT
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3771 把方案作为系数.值作为指数,两项相乘就是系数相乘.指数相加,符合意义. 考虑去重.先自 ...
-
bzoj 3771 Triple —— FFT
题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3771 令多项式的系数是方案数,次数是值: 设 a(x) 为一个物品的多项式,即 a[w[i] ...
-
BZOJ 3771 Triple ——FFT
直接暴力卷积+统计就可以了. 去重比较复杂. 其实也不复杂,抄吧! 反正AC了. #include <map> #include <cmath> #include <qu ...
-
spoj TSUM - Triple Sums fft+容斥
题目链接 首先忽略 i < j < k这个条件.那么我们构造多项式$$A(x) = \sum_{1现在我们考虑容斥:1. $ (\sum_{}x)^3 = \sum_{}x^3 + 3\s ...
-
BZOJ 3771: Triple(生成函数 FFT)
Time Limit: 20 Sec Memory Limit: 64 MBSubmit: 911 Solved: 528[Submit][Status][Discuss] Description ...
随机推荐
-
C# 破解 Reflector8.5
一.分析 破解.net .dll,可以使用reflector,但官方提供的reflector是需要购买的,因此,破解reflector势在必行. 二.破解Reflector具体步骤 下面为详细的破解步 ...
-
TP-LINK WR941 DD-WRT刷回OpenWRT及OpenWRT刷回原厂固件
1.DD-Wrt 刷回 OpenWrt A.从官网下载固件: root@TL-DDWRT:/tmp# wget http://downloads.openwrt.org/barrier_breaker ...
-
List<;T>;与Dictionary<;string,T>;频繁检索的性能差距
一直对LINQ简洁高效的语法青睐有加,对于经常和资料库,SQL语法打交道的C#开发者来说,LINQ无疑是一个非常不错的选择,当要在List<T>(T为一个普通对象)集合中查找满足某些条件的 ...
-
svg(可缩放矢量图形)
入门推荐: http://www.ruanyifeng.com/blog/2018/08/svg.html (教程) http://www.runoob.com/svg/svg-reference.h ...
-
NodePort 只能在node节点*问,外部无法访问
创建了一个NodePort类型的jenkins service,node port 30000,node节点ip为192.168.56.101, 在node节点上通过浏览器能正常访问http://19 ...
-
winform窗体 小程序【打开多个窗体、窗体之间传值、打开唯一窗体】
1.打开多个窗体 2.窗体之间的传值 3打开唯一窗体
-
批处理修改Hosts文件
@echo off set stHosts=127.0.0.1 www.XXX.com FOR /F "eol=# tokens=1 delims=" %%i in (%Syste ...
-
winform程序开机自动启动
app.manifest <requestedExecutionLevel level="requireAdministrator" uiAccess="false ...
- XML Web Service架构图
-
IOC容器02
获取xml文件路径,使用IO读取xml文件,使用Document对象解析xml文件,将xml中的bean的信息注册到BeanDefinition类,将BeanDefinition保存到一个map中:该 ...