WA 自闭 求调 玄关
查看原帖
WA 自闭 求调 玄关
749301
AmiyaCast楼主2023/10/10 19:56
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=b;i>=a;--i)
using namespace std;
inline ll read()
{
    ll x=0,f=1;
    char c=getchar();
    while (c<'0' || c>'9')
    {
        if (c=='-')  f=-1;
        c=getchar();
    }
    while (c>='0' && c<='9')
    {
        x=x*10+c-'0';
         c=getchar();
    }
    return x*f;
}

inline void print(ll x)
{
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) print(x / 10);
	putchar(x % 10 + '0');
	return ;
}
const int N = 4e6 + 7;
const double pi = acos(-1);
struct complex{
	double x, y;
	complex operator * (const complex& other) {
        complex result;
        result.x = x * other.x - y * other.y;
        result.y = y * other.x + x * other.y;
        return result;
    }
    complex operator + (const complex& other) {
    	complex result;
    	result.x = x + other.x;
    	result.y = y + other.y;
    	return result;
	}
	complex operator - (const complex& other){
		complex result;
		result.x = x - other.x;
		result.y = y - other.y;
		return result;
	}
};

complex a[N], b[N];
void FFT(complex *A, ll n, ll op)
{
	if(n == 1) return ;
	const int mid = (n >> 1);
	complex A1[mid], A2[mid];
	for(int i = 0; i < mid; ++i)
		A1[i] = A[i << 1], A2[i] = A[i << 1 | 1];
	FFT(A1, mid, op), FFT(A2, mid, op);
	complex w1({cos(2 * pi / n), sin(2 * pi / n) * op});
	complex wk({1, 0});
	for(int i = 0; i < mid; ++i, wk = wk * w1)
	{
		A[i] = A1[i] + A2[i] * wk;
		A[i + mid] = A1[i] - A2[i] * wk;
	}
}
char s[N], t[N];
ll ans[N];
int main(){
	scanf("%s", s + 1);
	scanf("%s", t + 1);
	ll n = strlen(s + 1) - 1, m = strlen(t + 1) - 1;
//	cout << n << " " << m << endl;
	for(int i = 0; i <= n; ++i)	a[i].x = s[n - i + 1] - '0';
	for(int i = 0; i <= m; ++i) b[i].x = t[m - i + 1] - '0';
//	for(int i = 0; i <= n; ++i) cout << a[i].x; puts("");
	for(m = n + m, n = 1; n <= m; n <<= 1);
	FFT(a, n, 1), FFT(b, n, 1);
	for(int i = 0; i <= n - 1; ++i)	a[i] = a[i] * b[i];
	FFT(a, n, -1);
	for(ll i = 0; i <= m; ++i)
		ans[i] = (ll)(a[i].x / n + 0.5);
	for(ll i = 0; i <= m; ++i)
	{
		ans[i + 1] += ans[i] / 10;
		ans[i] %= 10;
	}
	ll top = n + m + 1;
	while(ans[top] == 0 && top > 0) top--;
	for(; top >= 0; top--)
		print(ans[top]);
	return 0;
}
2023/10/10 19:56
加载中...