建议加强数据
查看原帖
建议加强数据
807041
hjyowl楼主2024/11/4 08:34

如下,这个代码:

 #include <bits/stdc++.h>
using namespace std;
const long long N = 5000010;
const double pi = acos(-1);
long long n,m;
struct owl{
    double x,y;
    owl operator + (const owl s) const {
        return {x + s.x,y + s.y};
    }
    owl operator - (const owl s) const {
        return {x - s.x,y - s.y};
    }
    owl operator * (const owl s) const {
        return {x * s.x - y * s.y,x * s.y + y * s.x};
    }
}a[N],b[N];
long long rev[N];
long long bit;
void fft(owl a[],long long op){
    for (long long i = 0; i < (1 << bit); i ++ ){
        if (i < rev[i]){
            swap(a[i],a[rev[i]]);
        }
    }
    for (long long mid = 1; mid < (1 << bit); mid *= 2){
        owl w1 = {cos(pi / mid), op * sin(pi / mid)};
        for (long long i = 0; i < (1 << bit); i += mid * 2){
            owl wk = {1,0};
            for (long long j = 0; j < mid; j ++ ,wk = wk * w1){
                owl x = a[i + j],y = wk * a[i + j + mid];
                a[i + j] = x + y,a[i + j + mid] = x - y;
            }
        }
    }
}
int main(){
    string s1,s2;
    cin >> s1 >> s2;
    n = s1.size() - 1,m = s2.size() - 1;
    for (long long i = 0;i <= n; i ++ ){
        a[i].x = s1[n - i] - '0';
    }
    for (long long i = 0; i <= m; i ++ ){
        b[i].x = s2[m - i] - '0';
    }
    while ((1 << bit) < n + m + 1){
        bit ++ ;
    }
    for (long long i = 0; i < (1 << bit); i ++ ){
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    }
    fft(a,1);
    fft(b,1);
    for (long long i = 0; i < (1 << bit); i ++ ){
        a[i] = a[i] * b[i];
    }
    fft(a,-1);
    vector<long long>vec;
    long long t = 0;
    for (long long i = 0; i < (1 << bit) || t; i ++ ){
        t += (long long)(a[i].x / (1 << bit) + 0.5);
        vec.push_back(t % 10);
        t /= 10;
    }
    while (vec.back() == 0){
        vec.pop_back();
    }
    for (long long i = vec.size() - 1; i >= 0; i -- ){
        cout << vec[i];
    }
    return 0;
}

在这个数据下:

0
1

应该输出 00,但是以上程序没有输出,但是能AC,建议加强数据。

2024/11/4 08:34
加载中...