本题解仅供娱乐
如有疏漏,请提出
大意
给定两个数字,要求输出其的积
多项式
我们可以把一个式子视作一个多项式 如数字 可以表示为 发现公共部分 于是将式子化为
我们用集合 来存储每一个系数即:
所以式子可以化简为
注意:n为次数
所以对于 的结果,就是
所以设, 则 为
不难发现时间复杂度为
实现
很简单 , 分三步
- 将输入内容转化为系数表达
- 系数乘法
- 输出
实现也十分之简单 我们先得规定一个的多项式 十分敏锐的观察到当时,不用做任何处理 因此
struct node {
ll num[N] = {0}; // 系数
ll len; // 最高次
} an, bn, cn;
然后是转化,自己想一下吧,string的每一位对应多项式的哪一位
void str_num(string a, node &num) {
ll len = a.size();
for (int i = 0; i < len; i++) {
num.num[i] = a[len - i - 1] - '0';
}
num.len = len;
}
到了乘法由于所以不用过多处理
然后是套公式即可
void mul(node a, node b, node &c) {
ll clen = a.len + b.len;
c.len = clen + 1;
for (int i = 0; i < clen; i++) {
for (int j = 0; j <= i; j++) {
c.num[i] += a.num[j] * b.num[i - j];
// 进位
if (c.num[i] >= 10) {
c.num[i + 1] += c.num[i] / 10;
c.num[i] %= 10;
}
}
}
}
到这里的时候会发现这就是简单高精乘,但我们还可以优化
点值表达
众所周知 是一个函数, 所以我们可以用图像表示它, 即代入 个点作为 得到值 , 我们可以通过解 元一次方程求得解
也就是说
可以表示出多项式,这就是点值表示法
如果我们做乘法,请动动手算一下点值乘法的时间复杂度
很惊讶,居然是O(n)!!!
所以我们要想办法将其转化为点值表达,点值乘法,再将点值表达转化为系数表达
朴素的,将系数转化为点值的算法叫 DFT(离散傅里叶变换)
, 将点值表达转化为系数表达的算法叫 IDFT(逆离散傅里叶变换)
而我们对其进行优化 , 则有 FFT(快速傅里叶变换)
, IFFT(逆快速傅里叶变换)
数学基础
复数
可以看一看OIWIKI 或 高中数学
单位复数根
满足 所以称 是n次单位复数根
如何得到单位复数根
在一个复平面上, 以 为圆心 , 作半径为 的圆
然后将其平均等分,就有个点,这个点所表示的复数,就是单位复数根
记为( , ...)
图?聪明的人自己会画图!
根据每个复数的幅角,可以计算出所对应的点,对应的点是(,)
即为复数
单位复数根性质
FFT
假设我们有一个多项式
奇偶分开
建立新函数 , 将括号分别代入
则
利用性质 发现和的和的对应的值相同
得到
和
因此求出了 和 后
可以同时求出 和
在递归求解即可
·思考,如何做到更优?(在代码中体现)
IFFT
我也不会证
直接在原函数上 乘以 负一 即可
AC代码
在中伟大的STL
提供了模板使用complex
的exp
就可以求出
好的你现在已经完全学会 了 快 掉这道题吧!
回归上文的思考:考虑倍增
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3000007;
const double pie = acos(-1);
typedef complex<double> cp;
cp a[N] , b[N] , c[N];
char str1[N] , str2[N];
ll brp[N],ans[N];
ll len1 , len2;
ll n;
void init(ll k){
ll len = 1 << k;
for(int i = 0 ; i < len ; i++){
brp[i]=(brp[i>>1]>>1)|((i&1)<<(k-1));
}
}
ll fft(cp *a , ll n , ll mode){
for(int i = 0 ; i < n ; i++){
if(i < brp[i]){
swap(a[i] , a[brp[i]]);
}
}
for(int i = 1 ; i < n ; i *= 2){
cp wn = exp(cp(0,mode*pie/i));
//普通omega
for(int j = 0 ; j < n ; j += i * 2){
cp w = cp(1,0);
for(int k = j ; k < j + i ; k++){
cp x = a[k];
cp y = w * a[k+i];
a[k] = x + y;
a[k+i] = x - y;
w *= wn;
}
}
}
if(mode == -1){
for(int i = 0 ; i < n ; i++){
a[i] /= n;
}
}
return 0;
}
int main(){
cin>>str1;
cin>>str2;
len1 = strlen(str1);
len2 = strlen(str2);
n = max(len1 , len2) + 1;
for(int i = 0 ; i < n ; i++){
if(i >= len1){
a[i] = (double)0.0;
}else{
a[i] = (double)(str1[len1 - i - 1] - '0');
}
}
for(int i = 0 ; i < n ; i++){
if(i >= len2){
b[i] = (double)0.0;
}else{
b[i] = (double)(str2[len2 - i - 1] - '0');
}
}
ll k = 1 , s = 2;
while((1 << k)< 2 * n - 1){
k++ , s <<= 1;
}
init(k);
fft(a,s,1);
fft(b,s,1);
for(int i = 0 ; i < s ; i++){
c[i] = a[i] * b[i];
}
fft(c,s,-1);
for(int i = 0 ; i < s ; i++){
ans[i] += (int)(c[i].real() + 0.5);
ans[i+1] = ans[i] / 10;
ans[i] %= 10;
}
while(!ans[s] && s>-1){
s--;
}
if(s == -1){
cout<<0;
}else{
for(int i = s ; i >= 0; i--){
cout<<ans[i];
}
}
return 0;
}
共 3 条回复
666
666
%%%