狂恋多项式算法(FFT,NTT,生成函数,插值,求逆...)
2021/7/25 12:05:51
本文主要是介绍狂恋多项式算法(FFT,NTT,生成函数,插值,求逆...),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
咕咕咕~~
- [P3803 【模板】多项式乘法(FFT)](https://www.luogu.com.cn/problem/P3803)(MODULE + FFT)
- [P1919 【模板】A*B Problem升级版(FFT快速傅里叶)](https://www.luogu.com.cn/problem/P1919)(MODULE + FFT + 高精度乘法)
- [P2553 [AHOI2001]多项式乘法](https://www.luogu.com.cn/problem/P2553)(字符串操作 + FFT)
- [BZOJ3771. Triple](https://darkbzoj.tk/problem/3771)(生成函数+容斥原理+FFT)
- [BZOJ3513 [MUTC2013]idiots](https://darkbzoj.tk/problem/3513)(反向思考 + 生成函数 + FFT)
- [P3321 [SDOI2015]序列统计](https://www.luogu.com.cn/problem/P3321)
- [P3338 [ZJOI2014]力](https://www.luogu.com.cn/problem/P3338)
- [P3702 [SDOI2017]序列计数](https://www.luogu.com.cn/problem/P3702)
- [P3723 [AH2017/HNOI2017]礼物](https://www.luogu.com.cn/problem/P3723)
- [P3763 [TJOI2017]DNA](https://www.luogu.com.cn/problem/P3763)
- [P3784 [SDOI2017] 遗忘的集合](https://www.luogu.com.cn/problem/P3784)
- [P3789 Azuki loves coloring](https://www.luogu.com.cn/problem/P3789)
- [P4002 [清华集训2017]生成树计数](https://www.luogu.com.cn/problem/P4002)
- [P4091 [HEOI2016/TJOI2016]求和](https://www.luogu.com.cn/problem/P4091)
- [P4157 [SCOI2006]整数划分](https://www.luogu.com.cn/problem/P4157)
- [P4173 残缺的字符串](https://www.luogu.com.cn/problem/P4173)
- [P4191 [CTSC2010]性能优化](https://www.luogu.com.cn/problem/P4191)
- [P4199 万径人踪灭](https://www.luogu.com.cn/problem/P4199)
- [P4221 [WC2018]州区划分](https://www.luogu.com.cn/problem/P4221)
- [P4233 射命丸文的笔记](https://www.luogu.com.cn/problem/P4233)
- [P4238 【模板】多项式乘法逆](https://www.luogu.com.cn/problem/P4238)
- [P4239 任意模数多项式乘法逆](https://www.luogu.com.cn/problem/P4239)
- [P4245 【模板】任意模数多项式乘法](https://www.luogu.com.cn/problem/P4245)
- [P4389 付公主的背包](https://www.luogu.com.cn/problem/P4389)
- [P4461 [CQOI2018]九连环](https://www.luogu.com.cn/problem/P4461)
- [P4566 [CTSC2018]青蕈领主](https://www.luogu.com.cn/problem/P4566)
- [P4705 玩游戏](https://www.luogu.com.cn/problem/P4705)
- [P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)](https://www.luogu.com.cn/problem/P4717)
- [P4721 【模板】分治 FFT](https://www.luogu.com.cn/problem/P4721)
- [P4725 【模板】多项式对数函数(多项式 ln)](https://www.luogu.com.cn/problem/P4725)
- [P4726 【模板】多项式指数函数(多项式 exp)](https://www.luogu.com.cn/problem/P4726)
- [P4841 [集训队作业2013]城市规划](https://www.luogu.com.cn/problem/P4841)
- [P4986 逃离](https://www.luogu.com.cn/problem/P4986)
- [P5050 【模板】多项式多点求值](https://www.luogu.com.cn/problem/P5050)
- [P5075 [JSOI2012] 分零食](https://www.luogu.com.cn/problem/P5075)
- [P5158 【模板】多项式快速插值](https://www.luogu.com.cn/problem/P5158)
- [P5162 WD与积木](https://www.luogu.com.cn/problem/P5162)
- [P5277 【模板】多项式开根(加强版)](https://www.luogu.com.cn/problem/P5277)
- [P5282 【模板】快速阶乘算法](https://www.luogu.com.cn/problem/P5282)
- [P5293 [HNOI2019]白兔之舞](https://www.luogu.com.cn/problem/P5293)
- [P5373 【模板】多项式复合函数](https://www.luogu.com.cn/problem/P5373)
- [P5383 普通多项式转下降幂多项式](https://www.luogu.com.cn/problem/P5383)
- [P5393 下降幂多项式转普通多项式](https://www.luogu.com.cn/problem/P5393)
- [P5394 【模板】下降幂多项式乘法](https://www.luogu.com.cn/problem/P5394)
- [P5432 A/B Problem (高精度除法)](https://www.luogu.com.cn/problem/P5432)
- [P5488 差分与前缀和](https://www.luogu.com.cn/problem/P5488)
- [P5519 [MtOI2019]埋骨于弘川](https://www.luogu.com.cn/problem/P5519)
- [P5641 【CSGRound2】开拓者的卓识](https://www.luogu.com.cn/problem/P5641)
- [P5667 拉格朗日插值2](https://www.luogu.com.cn/problem/P5667)
- [P5702 调和级数求和](https://www.luogu.com.cn/problem/P5702)
- [P5748 集合划分计数](https://www.luogu.com.cn/problem/P5748)
- [P5808 【模板】常系数非齐次线性递推](https://www.luogu.com.cn/problem/P5808)
P3803 【模板】多项式乘法(FFT)(MODULE + FFT)
- 模板
#include <bits/stdc++.h> using namespace std; static constexpr int N = 4000010; static constexpr double eps = 1e-6; struct cp { double r, i; cp(double _r = 0, double _i = 0) : r(_r), i(_i) { } cp operator+(const cp x) { return cp(r + x.r, i + x.i); } cp operator-(const cp x) { return cp(r - x.r, i - x.i); } cp operator*(const cp x) { return cp(r * x.r - i * x.i, r * x.i + i * x.r); } }; static const double pi = acos(-1.0); void FFT(cp a[], int n, int t = 1) { for (int i = 1, j = 0; i < n - 1; ++i) { for (int s = n; j ^= s >>= 1, ~j & s; ); if (i < j) swap(a[i], a[j]); } for (int d = 0; (1 << d) < n; ++d) { int m = 1 << d, m2 = m << 1; double o = pi / m * t; cp _w(cos(o), sin(o)); for (int i = 0; i < n; i += m2) { cp w(1, 0); for (int j = 0; j < m; ++j) { cp&A = a[i + j + m], &B = a[i + j], t = w * A; A = B - t; B = B + t; w = w * _w; } } } if (t == -1) for (int i = 0; i < n; ++i) a[i].r /= n; } cp a[N << 1], b[N]; int main() { int n, m; cin >> n >> m; for (int i = 0; i <= n; ++i) cin >> a[i].r; for (int i = 0; i <= m; ++i) cin >> b[i].r; int siz = 1; while ((siz <<= 1) <= n + m); FFT(a, siz), FFT(b, siz); for (int i = 0; i <= siz; ++i) a[i] = a[i] * b[i]; FFT(a, siz, -1); for (int i = 0; i <= n + m; ++i) { printf("%.0f ", a[i].r + eps); } return 0; }
P1919 【模板】A*B Problem升级版(FFT快速傅里叶)(MODULE + FFT + 高精度乘法)
- 把这两个大数的每一位看做多项式的系数,两多项式的乘法就相当于没有进位的数位乘法,可以用 F F T \rm FFT FFT在 O ( ( n + m ) log ( n + m ) ) \Omicron((n+m)\log(n+m)) O((n+m)log(n+m))的时间处理。
#include <bits/stdc++.h> using namespace std; static constexpr int N = 4000010; static constexpr double eps = 0.5; // (模板略) int ans[N], stk[N], top = 1; cp _a[N << 1], _b[N]; int main() { ios::sync_with_stdio(false), cin.tie(nullptr); string a, b; cin >> a >> b; int n1 = a.length(), n2 = b.length(); for (int i = 0; i < n1; ++i) _a[i].r = a[n1 - i - 1] - '0'; for (int i = 0; i < n2; ++i) _b[i].r = b[n2 - i - 1] - '0'; int n = 1; while ((n <<= 1) <= n1 + n2);// n <<= 1; FFT(_a, n), FFT(_b, n); for (int i = 0; i <= n; ++i) _a[i] = _a[i] * _b[i]; FFT(_a, n, -1); for (int i = 0; i <= n1 + n2; ++i) { ans[i] += int(_a[i].r + eps); ans[i + 1] += ans[i] / 10; ans[i] %= 10; stk[++top] = ans[i]; } while (!stk[top]) top--; while (top != 1) { cout << stk[top]; top --; } return 0; }
P2553 [AHOI2001]多项式乘法(字符串操作 + FFT)
- 这个题的难度不在与多项式算法,而是字符串模拟…网上看了好多题解大概是只含有
*
或者是只含有空格
的一个串也有可能出现…可以说是非常毒瘤了…
#include <bits/stdc++.h> using namespace std; static constexpr int N = 1000010; static constexpr double eps = 1e-6; // (模板略) char poly[N]; cp a1[N], a2[N], ans[N]; int len, i = 1, ind; // ind 表示 index --> 当前已经输入的多项式的度 deg 之和 void setpoly(cp a[]) { while (poly[i] != ')' && i < len) { int x = 0, z = 0; while (!isdigit(poly[i])) i++; x = poly[i] - '0'; if (isdigit(poly[i + 1])) { i++; x = x * 10 + poly[i] - '0'; } i++; if (poly[i] == 'a') { i++; i++; z = poly[i] - '0'; if (isdigit(poly[i+1])) { i++; z = z * 10 + poly[i] - '0'; } i++; } ind ++; a[z].r += x; } } int main() { while (gets(poly), poly[0]) { len = strlen(poly); memset(a1, 0, sizeof(a1)); memset(a2, 0, sizeof(a2)); memset(ans, 0, sizeof(ans)); i = 1, ind = 0; setpoly(a1); i++; setpoly(a2); int siz = 1; while ((siz <<= 1) <= ind); FFT(a1, siz), FFT(a2, siz); for (int i = 0; i <= siz; ++i) ans[i] = a1[i] * a2[i]; FFT(ans, siz, -1); bool first = false; for (int j = siz; j >= 0; j--) { if (int(ans[j].r + eps) == 0) continue; if (first) putchar('+'); else first = true; if (j > 0) printf("%.0fa^%d", ans[j].r + eps, j); else printf("%.0f", ans[j].r + eps); } putchar(10); memset(poly, 0, sizeof(poly)); } return 0; }
BZOJ3771. Triple(生成函数+容斥原理+FFT)
- 这类问题,也即组合计数基本都可以构造普通型生成函数来解决。
排列计数常使用构造指数型生成函数解决。
- 定义 a a a数列: a i a_i ai表示「价值为 i i i的物品的出现次数」(朴素的想就是选了 a i a_i ai次价值为 i i i的元素)
- 对 a a a构造普通型生成函数 A ( x ) = a 0 x 0 + a 1 x 1 + a 2 x 2 + ⋯ + a n x n A(x) = a_0x^0+a_1x^1+a_2x^2+\cdots+a_nx^n A(x)=a0x0+a1x1+a2x2+⋯+anxn,表示 x 元 素 选 了 1 次 的 方 案 数 x元素选了1次的方案数 x元素选了1次的方案数
- 如果不计重复的,选的方案数就是 A ( x ) + A 2 ( x ) + A 3 ( x ) A(x) + A^2(x)+A^3(x) A(x)+A2(x)+A3(x)
n 排 列 数 n排列数 n排列数的生成函数表示为 n n n个生成函数的积。
- 为了叙述方便,我们定义 B ( x ) 为 x 元 素 选 了 2 次 的 方 案 数 B(x)为x元素选了2次的方案数 B(x)为x元素选了2次的方案数, C ( x ) 为 x 元 素 选 了 3 次 的 方 案 数 C(x)为x元素选了3次的方案数 C(x)为x元素选了3次的方案数
- 然而题目中说需要将重复的减去,这里就是容斥原理的部分了:选一次没有重复;选两次中可能选到同一元素,我们减去 B ( x ) B(x) B(x),同时考虑到无序 ( a , b ) = ( b , a ) (a,b)=(b,a) (a,b)=(b,a),还要除以 2 ! = 2 2! = 2 2!=2;选三次也是类似的想法: ( a , a , b ) , ( a , b , a ) , ( b , a , a ) ) c y c \Big(a,a,b),(a,b,a),(b,a,a)\Big)_{cyc} (a,a,b),(a,b,a),(b,a,a))cyc,减去 3 A ( x ) B ( x ) 3A(x)B(x) 3A(x)B(x),然而 3 A ( x ) B ( x ) 3A(x)B(x) 3A(x)B(x)中包含了 3 ( a , a , a ) c y c 3(a,a,a)_{cyc} 3(a,a,a)cyc,原本的 A 3 ( x ) A^3(x) A3(x)中有 1 1 1份 ( a , a , a ) c y c (a,a,a)_{cyc} (a,a,a)cyc,加上这部分 2 C ( x ) 2C(x) 2C(x)最后除以 3 ! = 6 3! = 6 3!=6即可。
- 因此答案生成于
A ( x ) + A 2 ( x ) − B ( x ) 2 ! + A 3 ( x ) − 3 A ( x ) B ( x ) + 2 C ( x ) 3 ! A(x) + \dfrac{A^2(x) - B(x)}{2!} +\dfrac{A^3(x) - 3A(x)B(x)+2C(x)}{3!} A(x)+2!A2(x)−B(x)+3!A3(x)−3A(x)B(x)+2C(x)
- 这个式子可以用 F F T FFT FFT加速。
// (模板中 struct cp 里加一句) cp operator/(const double&x) { return cp(r / x, i / x); } cp A[N], B[N], C[N]; inline void work() { int n; in(n); int M = INT_MIN; forn(i,1,n) { int t; in(t); A[t].r ++, B[t << 1].r ++, C[t * 3].r ++; M = max(M, t * 3); } int siz = 1; while ((siz <<= 1) <= M << 1); FFT(A, siz), FFT(B, siz), FFT(C, siz); forn(i, 0, siz) { A[i] = A[i] + (A[i] * A[i] - B[i]) / 2 + (A [i] * A[i] * A[i] - cp(3., 0) * A[i] * B[i] + cp(2., 0) * C[i]) / 6.; } FFT(A, siz, -1); forn (i, 1, M << 1) { LL ans = LL(A[i].r + .5); if (ans) { out(i), putchar(32), out(ans), putchar(10); } } }
BZOJ3513 [MUTC2013]idiots(反向思考 + 生成函数 + FFT)
- 要求合法情况,需要判断两个条件,不如找出不合法的情况,再用总数,也即 ( n 3 ) \binom{n}{3} (3n)减去之
- 两边之和为 x x x的方案数是: A 2 ( x ) A^2(x) A2(x),也可以理解为一个卷积 ∑ k = i + j a i × a j \sum_{k = i+j}a_i\times a_j ∑k=i+jai×aj,其中有重复选了同一木棍的情况 B ( x ) B(x) B(x),那么 实 际 的 两 边 等 于 x 的 方 案 数 就 是 C ( x ) = A 2 ( x ) − B ( x ) 2 实际的两边等于x的方案数就是C(x) = \dfrac{A^2(x) - B(x)}{2} 实际的两边等于x的方案数就是C(x)=2A2(x)−B(x)
- 现在要求 两 边 之 和 ≤ x 两边之和\le x 两边之和≤x的情况:实际上就是 ∑ i = 0 x C ( i ) \sum_{i = 0}^xC(i) ∑i=0xC(i),处理一个前缀和即可。
- 最终答案就是 1 − A ( x ) C ( x ) ( n 3 ) 1-\dfrac{ A(x)C(x)}{\binom{n}{3}} 1−(3n)A(x)C(x)
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false), cin.tie(nullptr) #define forn(i, s, e) for (int i = s; i <= int(e); ++i) #define forr(i, e, s) for (int i = e; i >= int(s); --i) using namespace std; using LL = long long; static constexpr int N = 1000010; // (模板略) LL f[N << 1], g[N]; cp a[N]; void solve() { double ans; LL M = LLONG_MIN, siz = 1, tot, n; in(n); forn(i, 1, n) { LL t; in(t); a[t].r ++; M = max(M, t); f[t << 1] --; // 对于 t + t 的情况,是多余的,需要去重 } forr(i, M, 1) g[i] = g[i + 1] + LL(a[i].r); while ((siz <<= 1) <= M << 1); FFT(a, siz); forn(i, 0, siz) a[i] = a[i] * a[i]; FFT(a, siz, -1); forn(i, 0, siz) { f[i] += (LL)(a[i].r + .5); f[i] >>= 1; // 考虑到 i = j + k, (j, k)cyc 于是 i = k + j 也成立, 应去重 } ans = tot = (n) * (n - 1) / 2 * (n - 2) / 3; // 2 | ( n × (n - 1) ) 并且有 3 | ( n × (n - 1) × (n - 2) ) 避免溢出 // (虽然 n ^ 3 < LLONG_MAX ), 但是很秀(bushi) forn (i, 0, M) ans -= f[i] * g[i]; // 统计不合法的情况 printf("%.7f\n", 1. * ans / tot); // .f 而不是 .lf 老生常谈了 fill_n(f, siz << 1, 0), fill_n(g, siz, 0), fill_n(a, siz, 0); // 用多少清多少, 而不是 memset } inline void work() { int tt; in(tt); while (tt --) solve(); }
P3321 [SDOI2015]序列统计
P3338 [ZJOI2014]力
P3702 [SDOI2017]序列计数
P3723 [AH2017/HNOI2017]礼物
P3763 [TJOI2017]DNA
P3784 [SDOI2017] 遗忘的集合
P3789 Azuki loves coloring
P4002 [清华集训2017]生成树计数
P4091 [HEOI2016/TJOI2016]求和
P4157 [SCOI2006]整数划分
P4173 残缺的字符串
P4191 [CTSC2010]性能优化
P4199 万径人踪灭
P4221 [WC2018]州区划分
P4233 射命丸文的笔记
P4238 【模板】多项式乘法逆
P4239 任意模数多项式乘法逆
P4245 【模板】任意模数多项式乘法
P4389 付公主的背包
P4461 [CQOI2018]九连环
P4566 [CTSC2018]青蕈领主
P4705 玩游戏
P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)
P4721 【模板】分治 FFT
P4725 【模板】多项式对数函数(多项式 ln)
P4726 【模板】多项式指数函数(多项式 exp)
P4841 [集训队作业2013]城市规划
P4986 逃离
P5050 【模板】多项式多点求值
P5075 [JSOI2012] 分零食
P5158 【模板】多项式快速插值
P5162 WD与积木
P5277 【模板】多项式开根(加强版)
P5282 【模板】快速阶乘算法
P5293 [HNOI2019]白兔之舞
P5373 【模板】多项式复合函数
P5383 普通多项式转下降幂多项式
P5393 下降幂多项式转普通多项式
P5394 【模板】下降幂多项式乘法
P5432 A/B Problem (高精度除法)
P5488 差分与前缀和
P5519 [MtOI2019]埋骨于弘川
P5641 【CSGRound2】开拓者的卓识
P5667 拉格朗日插值2
P5702 调和级数求和
P5748 集合划分计数
P5808 【模板】常系数非齐次线性递推
这篇关于狂恋多项式算法(FFT,NTT,生成函数,插值,求逆...)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南
- 2024-09-26Springboot微服务资料入门教程