热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

SPOJTSUM三重和(FFT+容斥原理)

题目来源:http://www.spoj.com/problems/TSUM/。题目描述:给定一个包含N个不同整数的序列,计算所有可能的三个不同索引上的整数之和,并统计每个和出现的不同三元组数量。
题目解析

来源


SPOJ TSUM


问题描述


给定一个由N个不同整数组成的序列s。考虑从序列中选取三个不同的索引处的整数的所有可能和。对于每个可达到的和,输出产生该和的不同三元组的数量。


约束条件:
N ≤ 40000, |si| ≤ 20000


输入格式


输入的第一行包含一个整数N。接下来的N行每行包含序列s的一个元素。


输出格式


对于每个可能的和,按照以下格式输出:
sum_value : number_of_triples
较小的和值应先输出。


样例输入


5
-1
2
3
0
5


样例输出


1 : 1
2 : 1
4 : 2
5 : 1
6 : 1
7 : 2
8 : 1
10 : 1


解题思路

本题的核心在于利用快速傅里叶变换(FFT)来高效计算多项式乘积,从而解决三数求和的问题。首先,根据给定的序列构建三个相同的多项式,其中指数代表数字,系数代表该数字出现的次数。通过计算这三个多项式的乘积,可以得到有序且可重复选择数字的所有结果。使用FFT可以显著提高计算效率。


然而,这种方法得到的是有序的三元组计数,而题目要求的是无序的三元组。因此,需要通过容斥原理来调整结果。具体来说,先减去所有两个数字相同的情况,再加回所有三个数字相同的情况,最后将结果除以3的阶乘(即6),以消除重复计数。


为了优化性能,可以采取一些措施减少不必要的计算,例如在多项式相乘时直接对点值进行操作,避免多次执行离散傅里叶变换(DFT)过程。


实现代码
#include 
#include
#include
#include
using namespace std;
#define MAXN 131072
const double PI = acos(-1.0);

struct Complex {
double real, imag;
Complex(double _real = 0, double _imag = 0) : real(_real), imag(_imag) {}
Complex operator+(const Complex &cp) const {
return Complex(real + cp.real, imag + cp.imag);
}
Complex operator-(const Complex &cp) const {
return Complex(real - cp.real, imag - cp.imag);
}
Complex operator*(const Complex &cp) const {
return Complex(real * cp.real - imag * cp.imag, real * cp.imag + cp.real * imag);
}
void setValue(double _real = 0, double _imag = 0) {
real = _real; imag = _imag;
}
};

int len;
Complex wn[MAXN + 1], wn_anti[MAXN + 1];

void FFT(Complex y[], int op) {
for (int i = 1, j = len >> 1, k; i if (i k = len >> 1;
while (j >= k) {
j -= k;
k >>= 1;
}
if (j }
for (int h = 2; h <= len; h <<= 1) {
Complex Wn = (op == 1 ? wn[h] : wn_anti[h]);
for (int i = 0; i Complex W(1, 0);
for (int j = i; j > 1); ++j) {
Complex u = y[j], t = W * y[j + (h >> 1)];
y[j] = u + t;
y[j + (h >> 1)] = u - t;
W = W * Wn;
}
}
}
if (op == -1) {
for (int i = 0; i }
}

Complex A[MAXN], B[MAXN];
double ans[MAXN];
int s[40100], cnt[80100];

int main() {
for (int i = 0; i <= MAXN; ++i) {
wn[i].setValue(cos(2.0 * PI / i), sin(2.0 * PI / i));
wn_anti[i].setValue(wn[i].real, -wn[i].imag);
}

int n;
scanf("%d", &n);
for (int i = 0; i scanf("%d", &s[i]);
s[i] += 20000;
++cnt[s[i]];
}

len = MAXN;

for (int i = 0; i <= 40000; ++i) {
B[i].setValue(cnt[i]);
}
FFT(B, 1);
for (int i = 0; i A[i] = B[i] * B[i] * B[i];
}
FFT(A, -1);
for (int i = 0; i ans[i] = A[i].real;
}

memset(cnt, 0, sizeof(cnt));
for (int i = 0; i ++cnt[s[i] + s[i]];
}
for (int i = 0; i <= 80000; ++i) {
A[i].setValue(cnt[i]);
}
for (int i = 80001; i A[i].setValue(0);
}
FFT(A, 1);
for (int i = 0; i A[i] = A[i] * B[i];
}
FFT(A, -1);
for (int i = 0; i ans[i] -= 3 * A[i].real;
}

for (int i = 0; i ++ans[s[i] + s[i] + s[i]];
}

for (int i = 0; i long long tmp = (long long)(ans[i] / 6.0 + 0.5);
if (tmp) {
printf("%d : %lld\n", i - 60000, tmp);
}
}
return 0;
}

推荐阅读
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本文深入探讨了 Java 中的 Serializable 接口,解释了其实现机制、用途及注意事项,帮助开发者更好地理解和使用序列化功能。 ... [详细]
  • 尽管使用TensorFlow和PyTorch等成熟框架可以显著降低实现递归神经网络(RNN)的门槛,但对于初学者来说,理解其底层原理至关重要。本文将引导您使用NumPy从头构建一个用于自然语言处理(NLP)的RNN模型。 ... [详细]
  • 本文介绍了如何利用JavaScript或jQuery来判断网页中的文本框是否处于焦点状态,以及如何检测鼠标是否悬停在指定的HTML元素上。 ... [详细]
  • 火星商店问题:线段树分治与持久化Trie树的应用
    本题涉及编号为1至n的火星商店,每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品,以及查询某段时间内某些商店中所有商品(含永久商品)与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 本文介绍了如何使用JQuery实现省市二级联动和表单验证。首先,通过change事件监听用户选择的省份,并动态加载对应的城市列表。其次,详细讲解了使用Validation插件进行表单验证的方法,包括内置规则、自定义规则及实时验证功能。 ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • 本文详细介绍了如何构建一个高效的UI管理系统,集中处理UI页面的打开、关闭、层级管理和页面跳转等问题。通过UIManager统一管理外部切换逻辑,实现功能逻辑分散化和代码复用,支持多人协作开发。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • Linux设备驱动程序:异步时间操作与调度机制
    本文介绍了Linux内核中的几种异步延迟操作方法,包括内核定时器、tasklet机制和工作队列。这些机制允许在未来的某个时间点执行任务,而无需阻塞当前线程,从而提高系统的响应性和效率。 ... [详细]
author-avatar
yun悠然_434
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有