HDU 1402
题目大意
暂无
题目解法
暂无
RTFC
#include <cmath>
#include <cstdio>
#include <cstring>
const int N = 500005;
const double pi = acos(-1);
struct complex
{
double r, i;
} a[N], b[N];
inline complex operator+(const complex &x, const complex &y)
{
return { x.r + y.r, x.i + y.i };
}
inline complex operator-(const complex &x, const complex &y)
{
return { x.r - y.r, x.i - y.i };
}
inline complex operator*(const complex &x, const complex &y)
{
return { x.r * y.r - x.i * y.i, x.r * y.i + x.i * y.r };
}
char s1[N], s2[N];
int ans[N];
void Rader(complex *F, int len)
{
complex t;
int j = len >> 1;
for (int i = 1; i < len - 1; i++)
{
if (i < j)
t = F[i], F[i] = F[j], F[j] = t;
int k = len >> 1;
while (j >= k)
j -= k, k >>= 1;
if (j < k)
j += k;
}
}
void fft(complex *F, int len, int flag)
{
Rader(F, len);
for (int h = 2; h <= len; h <<= 1)
{
const complex wn = { cos(-flag * 2 * pi / h), sin(-flag * 2 * pi / h) };
for (int j = 0; j < len; j += h)
{
complex w = { 1, 0 };
int m = h >> 1;
for (int k = j; k < j + m; k++, w = w * wn)
{
complex u = F[k], t = w * F[k + m];
F[k] = u + t, F[k + m] = u - t;
}
}
}
}
int main()
{
while (~scanf("%s%s", s1, s2))
{
int len1, len2, len;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(ans, 0, sizeof(ans));
len1 = (int)strlen(s1) << 1, len2 = (int)strlen(s2) << 1;
for (len = 1; len < len1 || len < len2;)
len <<= 1;
len1 >>= 1, len2 >>= 1;
for (int i = 0; i < len1; i++)
a[i].r = s1[len1 - 1 - i] - '0';
for (int i = 0; i < len2; i++)
b[i].r = s2[len2 - 1 - i] - '0';
fft(a, len, 1);
fft(b, len, 1);
for (int i = 0; i < len; i++)
a[i] = a[i] * b[i];
fft(a, len, -1);
for (int i = 0; i < len; i++)
ans[i] = int(a[i].r / len + 0.5);
for (int i = 0; i < len; i++)
ans[i + 1] += ans[i] / 10, ans[i] %= 10;
int high = 0;
for (int i = len - 1; high == 0 && i >= 0; i--)
if (ans[i])
high = i;
for (int i = high; i >= 0; i--)
putchar(ans[i] + '0');
putchar('\n');
}
return 0;
}