[hdu1402]大数乘法(FFT模板)

题意：大数乘法

思路：FFT模板

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

/* ******************************************************************************** */

#include <iostream>                                                                 //

#include <cstdio>                                                                   //

#include <cmath>                                                                    //

#include <cstdlib>                                                                  //

#include <cstring>                                                                  //

#include <vector>                                                                   //

#include <ctime>                                                                    //

#include <deque>                                                                    //

#include <queue>                                                                    //

#include <algorithm>                                                                //

#include <map>                                                                      //

#include <cmath>                                                                    //

using namespace

std;

//

#define pb push_back                                                                //

#define mp make_pair                                                                //

#define X first                                                                     //

#define Y second                                                                    //

#define all(a) (a).begin(), (a).end()                                               //

#define foreach(a, i) for (typeof(a.begin()) i = a.begin(); i != a.end(); ++ i) //

#define foreach(a, n, i) for(typeof(*a) *i = a; i < a + n; i ++) //

#define fillchar(a, x) memset(a, x, sizeof(a))                                      //

//

void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);} //

void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R> //

void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1; //

while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T> //

void print(const T t){cout<<t<<endl;}template<typename F,typename...R> //

void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T> //

void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;} //

//

typedef pair<int, int

> pii;

//

typedef long long

ll;

//

typedef unsigned long long ull; //

//

template<typename T>bool umax(T&a, const T&b){return b>a?false:(a=b,true);} //

template<typename T>bool umin(T&a, const T&b){return b<a?false:(a=b,true);} //

template<typename

T>

//

void V2A(T a[],const vector<T>&b){for(int i=0;i<b.size();i++)a[i]=b[i];} //

template<typename

T>

//

void A2V(vector<T>&a,const T b[]){for(int i=0;i<a.size();i++)a[i]=b[i];} //

//

const double PI = acos(-1); //

//

/* -------------------------------------------------------------------------------- */

namespace FFT {

const static int maxn = 5e4 + 7;

#define L(x) (1 << (x))

double ax[maxn << 2], ay[maxn << 2], bx[maxn << 2], by[maxn << 2];//需要四倍空间

int revv(int x, int bits) {

int ret = 0;

for (int i = 0; i < bits; i++) {

ret <<= 1;

ret |= x & 1;

x >>= 1;

}

return ret;

}

void fft(double * a, double * b, int n, bool rev) {

int bits = 0;

while (1 << bits < n) ++bits;

for (int i = 0; i < n; i++) {

int j = revv(i, bits);

if (i < j)

swap(a[i], a[j]), swap(b[i], b[j]);

}

for (int len = 2; len <= n; len <<= 1) {

int half = len >> 1;

double wmx = cos(2 * PI / len), wmy = sin(2 * PI / len);

if (rev) wmy = -wmy;

for (int i = 0; i < n; i += len) {

double wx = 1, wy = 0;

for (int j = 0; j < half; j++) {

double cx = a[i + j], cy = b[i + j];

double dx = a[i + j + half], dy = b[i + j + half];

double ex = dx * wx - dy * wy, ey = dx * wy + dy * wx;

a[i + j] = cx + ex, b[i + j] = cy + ey;

a[i + j + half] = cx - ex, b[i + j + half] = cy - ey;

double wnx = wx * wmx - wy * wmy, wny = wx * wmy + wy * wmx;

wx = wnx, wy = wny;

}

if (rev) {

for (int i = 0; i < n; i++)

a[i] /= n, b[i] /= n;

}

int solve(int a[], int na, int b[], int nb, int ans[]) {

int len = max(na, nb), ln;

for(ln = 0; L(ln) < len; ++ln);

len = L(++ln);

for (int i = 0; i < len ; ++i) {

if (i >= na) ax[i] = 0, ay[i] = 0;

else ax[i] = a[i], ay[i] = 0;

}

fft(ax, ay, len, 0);

for (int i = 0; i < len; ++i) {

if (i >= nb) bx[i] = 0, by[i] = 0;

else bx[i] = b[i], by[i] = 0;

}

fft(bx, by, len, 0);

for (int i = 0; i < len; ++i) {

double cx = ax[i] * bx[i] - ay[i] * by[i];

double cy = ax[i] * by[i] + ay[i] * bx[i];

ax[i] = cx, ay[i] = cy;

}

fft(ax, ay, len, 1);

for (int i = 0; i < len; ++i)

ans[i] = (int)(ax[i] + 0.5);

return len;

}

#undef L(x)

}

const int maxn = 5e4 + 7;

char s1[maxn], s2[maxn];

int x[maxn], y[maxn], ans[maxn << 2];

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif // ONLINE_JUDGE

while (~scanf("%s", s1)) {

scanf("%s", s2);

int len1 = strlen(s1), len2 = strlen(s2);

for (int i = 0; i < len1; i ++) x[i] = s1[len1 - i - 1] - '0';

for (int i = 0; i < len2; i ++) y[i] = s2[len2 - i - 1] - '0';

fillchar(ans, 0);

int len = FFT::solve(x, len1, y, len2, ans), i;

for (i = 0; i < len || ans[i] >= 10; i ++) {

ans[i + 1] += ans[i] / 10;

ans[i] %= 10;

}

len = i;

while (ans[len] <= 0 && len) len --;

for (int i = len; i >= 0; i --) putchar(ans[i] + '0');

puts("");

}

return 0;

}

/* ******************************************************************************** */

巴特西

[hdu1402]大数乘法(FFT模板)

最新文章

热门文章