给出两个n位10进制整数x和y，你需要计算x*y。

第一行一个正整数n。
第二行描述一个位数为n的正整数x。
第三行描述一个位数为n的正整数y。

输出一行，即x*y的结果。

1
3
4

12

数据范围：
n<=60000

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 const double pi = acos(-);

 typedef complex<double> Complex;

 int n, m, len;

 int ans[maxn];

 int rev[maxn];

 char str[maxn];

 Complex a[maxn];

 Complex b[maxn];

 inline void calculateFFT(Complex *c, double f)

 {

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

         if (i < rev[i])swap(c[i], c[rev[i]]);

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

     {

         Complex wn(cos(pi/i), f*sin(pi/i));

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

         {

             Complex wk(, );

             for (int k = ; k < i; ++k, wk *= wn)

             {

                 Complex x = c[j + k];

                 Complex y = c[i + j + k] * wk;

                 c[j + k] = x + y;

                 c[i + j + k] = x - y;

             }

         }

     }

 }

 signed main(void)

 {

     scanf("%d", &n);

     scanf("%s", str);

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

         a[i] = str[n - i - ] - '';

     scanf("%s", str);

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

         b[i] = str[n - i - ] - '';

     m = n << ;

     for (n = ; n < m; )

         ++len, n <<= ;

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

     {

         rev[i] |= rev[i >> ] >> ;

         rev[i] |= (i&) << (len - );

     }

     calculateFFT(a, );

     calculateFFT(b, );

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

         a[i] *= b[i];

     calculateFFT(a, -);

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

         a[i] /= n;

     for (int i= ; i < m; ++i)

         ans[i] = int(a[i].real() + 0.5);

     while (!ans[m - ])--m;

     for (int i = ; i < m; ++i)

         if (ans[i] >= )

         {

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

             ans[i] %= ;

         }

     if (!ans[m])--m;

     for (int i = m; ~i; --i)

         putchar('' + ans[i]);

 }