题解:#6580.高精度乘法 审核通过

lyhmbr CSP-S2二等 2024-12-22 21:18:03 2025-01-01 0:08:06 5

本题解仅供娱乐 如有疏漏,请提出

大意

给定两个数字,要求输出其的积

多项式

我们可以把一个式子视作一个多项式 如数字 可以表示为 发现公共部分 于是将式子化为

我们用集合 来存储每一个系数即:

所以式子可以化简为

注意:n为次数

所以对于 的结果,就是

所以设, 则

不难发现时间复杂度为

实现

很简单 , 分三步

  1. 将输入内容转化为系数表达
  2. 系数乘法
  3. 输出

实现也十分之简单 我们先得规定一个多项式 十分敏锐的观察到当时,不用做任何处理 因此

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 或 高中数学

"OIWIKI传送门"

单位复数根

满足 所以称 是n次单位复数根

如何得到单位复数根

在一个复平面上, 为圆心 , 作半径为 的圆

然后将其平均等分,就有个点,这个点所表示的复数,就是单位复数根

记为( , ...)

图?聪明的人自己会画图!

根据每个复数的幅角,可以计算出所对应的点,对应的点是(,)

即为复数

单位复数根性质

FFT

假设我们有一个多项式

奇偶分开

建立新函数 , 将括号分别代入

利用性质 发现的对应的值相同

得到

因此求出了

可以同时求出

在递归求解即可

·思考,如何做到更优?(在代码中体现)

IFFT

我也不会证 直接在原函数上 乘以 负一 即可

AC代码

中伟大的STL提供了模板使用complexexp就可以求出

好的你现在已经完全学会 了 快 掉这道题吧!

回归上文的思考:考虑倍增

#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;
}
{{ vote && vote.total.up }}

共 3 条回复

korme

666

korme

666

lyhldy CSP-J2二等

%%%