程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1402 A * B Problem Plus（FFT）

HDU 1402 A * B Problem Plus（FFT）

編輯：C++入門知識

HDU 1402 A * B Problem Plus（FFT）

題意：求大數 A * B。

思路：由於A 和 B太大了，用java或者大數都會超時。我們可以用所謂的快速傅立葉變換（FFT）求解多項式相乘的問題。

細節參見代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9;
const double PI = acos(-1.0);
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 200010;
int T,n,m, sum[maxn];
char s1[maxn/2], s2[maxn/2];
struct node {
    double x, y;
    node(double x = 0, double y = 0) : x(x), y(y) {}
    node operator - (const node& b) const {
        return node(x - b.x, y - b.y);
    }
    node operator + (const node& b) const {
        return node(x + b.x, y + b.y);
    }
    node operator * (const node& b) const {
        return node(x * b.x - y * b.y, x * b.y + y * b.x);
    }
}x1[maxn], x2[maxn];
void change(node y[], int len) {
    int i, j, k;
    for(i = 1, j = len/2; i < len-1; i++) {
        if(i < j) swap(y[i], y[j]);
        k = len/2;
        while(j >= k) {
            j -= k;
            k /= 2;
        }
        if(j < k) j += k;
    }
}
void fft(node y[], int len, int on) {
    change(y, len);
    for(int h = 2; h <= len; h <<= 1) {
        node wn(cos(-on*2*PI/h), sin(-on*2*PI/h));
        for(int j = 0; j < len; j+=h) {
            node w(1, 0);
            for(int k = j; k < j+h/2; k++) {
                node u = y[k];
                node t = w * y[k+h/2];
                y[k] = u + t;
                y[k+h/2] = u - t;
                w = w * wn;
            }
        }
    }
    if(on == -1)
        for(int i = 0; i < len; i++) y[i].x /= len;
}
int main() {
    while(~scanf("%s%s",s1,s2)) {
        int len1 = strlen(s1);
        int len2 = strlen(s2);
        int len = 1;
        while(len < len1 * 2 || len < len2 * 2) len <<= 1;
        for(int i = 0; i < len1; i++) x1[i] = node(s1[len1-1-i]-'0', 0);
        for(int i = len1; i < len; i++) x1[i] = node(0, 0);

        for(int i = 0; i < len2; i++) x2[i] = node(s2[len2-1-i]-'0', 0);
        for(int i = len2; i < len; i++) x2[i] = node(0, 0);
        fft(x1, len, 1);
        fft(x2, len, 1);
        for(int i=0;i 0) --len;
        for(int i = len; i >= 0; --i) printf("%c",(char)sum[i] + '0');
        printf("\n");
    }
    return 0;
}