spoj TSUM - Triple Sums fft+容斥
题目链接
首先忽略 i < j < k这个条件。
那么我们构造多项式
\]
显然答案就是 $ A^3(x) $中 $ x^S $的系数。
现在我们考虑容斥:
- $ (\sum_{}x)^3 = \sum_{}x^3 + 3\sum_{}x^2 y + 6\sum_{}xyz $
- $ (\sum_{}x^2)(\sum_{}x) = \sum_{}x^3 + \sum_{}x^2 y $
- $ (\sum_{}x)^3 = \sum_{}x^3 \(
<br>
<br>
由上面三个式子 我们可以推导出<br><br>
\) \sum_{}xyz = \frac {(\sum_{}x)^3 - 3(\sum_{}x^2)(\sum_{}x) + 2\sum_{}x^3}{6} $
1式中的系数3, 是因为相当于从3个(x+y+z)中选2个x和一个y, 那么就是$ C_3^2 \cdotp C_1^1 $
6 就是选一个x一个y一个z, 显然是 $ C_3^1 \cdotp C_2^1 $
然后问题就解决了, 套fft模板就好。
第一次用markdown还有点小激动。
```C++
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt cmx;
typedef pair pll;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int mod = 1e9+7;
const int inf = 1061109567;
const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
const int maxn = 2e5+5;
int c[maxn], val[maxn], a[maxn], b[maxn];
cmx x[maxn], y[maxn];
void change(cmx x[], int len) {
int i, j, k;
for(i = 1, j = len/2; i = k) {
j -= k;
k /= 2;
}
if(j >n;
for(int i = 0; i
最新文章
- Vertica增加一个数据存储的目录
- .Net 转战 Android 4.4 日常笔记目录
- <;一>;获取数据库连接
- 源码阅读笔记 - 2 std::vector (1)
- Magicodes.WeiChat——后台JS框架封装
- Adaboost 卡口车辆检测训练
- struts2与struts1整合,Unable to load configuration. - interceptor-ref ... struts.xml
- No compiler is provided in this environment. Perhaps you are running on a JRE rather than a JDK? 问题
- 关于Tokenizer与TokenFilter的区别
- PHP函数ip2long转换IP时数值太大产生负数的解决办法
- 1.AJAX简介
- 任何时候都适用的20个C++技巧
- Reverse Words in a String | LeetCode OJ | C++
- python 算法练习
- 第四十三节,文件、文件夹、压缩包、处理模块shutil
- 浅谈 Java 主流开源类库解析 XML
- webservice常用两种身份验证方式
- poj3162
- Squid实现正向代理及访问控制--技术流ken
- Win10更新