样例没过,但是交上去AC,求解
查看原帖
样例没过,但是交上去AC,求解
678858
ShiRoZeTsuHL卜奎BBQ!楼主2023/8/22 21:24

不知道为什么,样例会使第一位不输出,但是却能AC,不是很懂

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 3e6 + 5;
const ll mod = 998244353;
const ll G = 3;
const ll Gi = 332748118;

char s[maxn], t[maxn];
int limit = 1, L, r[maxn];
ll a[maxn], b[maxn];

ll fpm(ll a, ll k) {
    ll res = 1;
    while(k) {
        if(k&1) res = res*a % mod;
        a = a*a % mod;
        k >>= 1;
    }
    return res;
}

void NTT(ll* A, bool type) {
    for(int i = 0; i < limit; i++)
        if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < limit; mid <<= 1) {
        ll wn = fpm(type ? G : Gi, (mod-1)/(mid<<1));
        for(int j = 0; j < limit; j += (mid<<1)) {
            ll w = 1;
            for(int k = 0; k < mid; k++, w = w*wn % mod) {
                ll x = A[j+k], y = w*A[j+k+mid] % mod;
                A[j+k] = (x+y) % mod;
                A[j+k+mid] = (x-y + mod) % mod;
            }
        }
    }
    if(!type) {
        ll inv = fpm(limit, mod-2);
        for(int i = 0; i < limit; i++)
            a[i] = a[i]*inv % mod;
    }
}

int main() {
    scanf("%s %s", s+1, t+1);
    int n = strlen(s+1), m = strlen(t+1);
    for(int i = n; i >= 1; i--) a[n-i] = s[i]-'0';
    for(int i = m; i >= 1; i--) b[m-i] = t[i]-'0';
    n--; m--;
    while(limit <= n+m) limit <<= 1, L++;
    for(int i = 0; i < limit; i++) r[i] = (r[i>>1]>>1) | ((i&1) << (L-1));
    NTT(a, 1); NTT(b, 1);
    for(int i = 0; i < limit; i++) a[i] = a[i]*b[i] % mod;
    NTT(a, 0);
    for(int i = 0; i < limit; i++)
        if(a[i] >= 10) {
            a[i+1] += a[i]/10;
            a[i] %= 10;
        }
    n = limit-1;
    while(a[n] == 0) n--;
    for(int i = n; i >= 0; i--)
        printf("%d", a[i]);
    return 0;
}
2023/8/22 21:24
加载中...