当前位置：首页 > news >正文

P1919 【模板】高精度乘法 | A*B Problem 升级版、P3803 【模板】多项式乘法（FFT）、P1595 信封问题（圆排列、错位排列）

news 来源：原创 2024/9/19 8:14:42

P1919 【模板】高精度乘法 | A*B Problem 升级版（FFT算法）

题目描述

G42 快速傅里叶变换 FFT算法高精度乘法 - 董晓 - 博客园 (cnblogs.com)

运行代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 3e6;
const double PI = acos(-1);struct complex {double x, y;complex operator+(const complex& t) const {return {x + t.x, y + t.y};}complex operator-(const complex& t) const {return {x - t.x, y - t.y};}complex operator*(const complex& t) const {return {x * t.x - y * t.y, x * t.y + y * t.x};}
};complex A[N], B[N];
char s1[N], s2[N];
int R[N], ans[N];// 交换两个复数
void swapComplex(complex& a, complex& b) {complex temp = a;a = b;b = temp;
}// 快速傅里叶变换
void FFT(complex A[], int n, int op) {for (int i = 0; i < n; ++i)R[i] = R[i / 2] / 2 + ((i & 1)? n / 2 : 0);for (int i = 0; i < n; ++i)if (i < R[i])swapComplex(A[i], A[R[i]]);for (int i = 2; i <= n; i <<= 1) {complex w1({cos(2 * PI / i), sin(2 * PI / i) * op});for (int j = 0; j < n; j += i) {complex wk({1, 0});for (int k = j; k < j + i / 2; ++k) {complex x = A[k], y = A[k + i / 2] * wk;A[k] = x + y;A[k + i / 2] = x - y;wk = wk * w1;}}}
}int main() {scanf("%s%s", s1, s2);int n = strlen(s1) - 1, m = strlen(s2) - 1;for (int i = 0; i <= n; i++)A[i].x = s1[n - i] - '0';for (int i = 0; i <= m; i++)B[i].x = s2[m - i] - '0';for (m = n + m, n = 1; n <= m; n <<= 1);FFT(A, n, 1);FFT(B, n, 1);for (int i = 0; i < n; ++i)A[i] = A[i] * B[i];FFT(A, n, -1);int k = 0, t = 0;for (int i = 0; i < n || t; i++) {t += A[i].x / n + 0.5;ans[k++] = t % 10;t /= 10;}while (k > 1 &&!ans[k - 1])k--;for (int i = k - 1; i >= 0; i--)printf("%d", ans[i]);return 0;
}

代码思路

首先定义了一个complex结构体来表示复数，并定义了复数的加法、减法和乘法运算。
FFT函数实现快速傅里叶变换。通过计算R数组确定交换元素的位置，并进行位逆序交换。利用分治思想，对于不同长度的区间，通过旋转因子进行合并计算。
在main函数中：读取两个字符串s1和s2，将它们转换为复数数组A和B，其中每个复数的实部对应字符数字。确定合适的长度n进行快速傅里叶变换。对A和B进行正变换、相乘，再进行逆变换。计算最终结果的进位和存储。从变换后的结果中逐步累加，并处理进位，将结果存储在ans数组中。去除前面多余的0，并输出最终结果。

P3803 【模板】多项式乘法（FFT）

题目描述

P3803 【模板】多项式乘法（FFT） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

运行代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#define LL long long
using namespace std;
const int N = 4e6;
const int g = 3, P = 998244353;int n, m, R[N];
LL A[N], B[N];LL qpow(LL a, LL b) {LL ans = 1;while (b) {if (b & 1) ans = ans * a % P;a = a * a % P;b >>= 1;}return ans;
}void swapLL(LL& a, LL& b) {LL temp = a;a = b;b = temp;
}void NTT(LL A[], int n, int op) {for (int i = 0; i < n; ++i)R[i] = R[i / 2] / 2 + ((i & 1) ? n / 2 : 0);for (int i = 0; i < n; ++i)if (i < R[i]) swapLL(A[i], A[R[i]]);for (int i = 2; i <= n; i <<= 1) {LL g1 = qpow(op == 1 ? g : qpow(g, P - 2), (P - 1) / i);for (int j = 0; j < n; j += i) {LL gk = 1;for (int k = j; k < j + i / 2; ++k) {LL x = A[k], y = gk * A[k + i / 2] % P;A[k] = (x + y) % P;A[k + i / 2] = (x - y + P) % P;gk = gk * g1 % P;}}}
}int main() {scanf("%d%d", &n, &m);for (int i = 0; i <= n; ++i) scanf("%lld", A + i);for (int i = 0; i <= m; ++i) scanf("%lld", B + i);for (m = n + m, n = 1; n <= m; n <<= 1);NTT(A, n, 1);NTT(B, n, 1);for (int i = 0; i < n; ++i) A[i] = A[i] * B[i] % P;NTT(A, n, -1);for (int i = 0; i <= m; ++i)printf("%d ", A[i] * qpow(n, P - 2) % P);return 0;
}

代码思路

NTT 是快速傅里叶变换（FFT）在数论中的一种类似应用。它利用了模运算和特定的原根来实现类似于 FFT 的分治和合并计算，以高效地计算多项式乘法。

在这段代码中，选择了 g = 3 作为原根，P = 998244353 作为模数。

思路：

qpow 函数用于快速计算模意义下的幂运算。
NTT 函数实现了 NTT 过程。首先通过计算 R 数组来确定交换元素的位置，并进行位逆序交换。然后通过循环，对于不同长度的区间，利用原根计算出相应的系数，并进行合并计算。
在 main 函数中：读取两个多项式的系数。确定合适的长度 n 进行 NTT 计算。对两个多项式分别进行正变换。变换后的系数相乘。进行逆变换得到乘法结果。最后输出结果。

P1595 信封问题（圆排列、错位排列）

题目描述

P1595 信封问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

运行代码

#include<iostream>
using namespace std;
const int N=21;
long long D[N];
int main(){int n;cin>>n;D[1]=0,D[2]=1;for(int i=3; i<N; i++)D[i]=(i-1)*(D[i-1]+D[i-2]);  printf("%lld\n",D[n]);return 0;
}

代码思路

首先定义了一个常量N表示数列的最大长度，以及一个长整型数组D来存储数列的各项值。
在main函数中，首先读取一个整数n。
初始化数列的前两项：D[1] = 0，D[2] = 1。
然后通过一个循环从第 3 项开始计算后续的每一项。计算方式为D[i] = (i - 1) * (D[i - 1] + D[i - 2])。这意味着每一项都是其前两项之和乘以当前项的索引减 1。
最后，输出数列的第n项的值D[n]。
D[i] = (i - 1) * (D[i - 1] + D[i - 2])为推断关系式