Submission #57730

#	Time	Username	Problem	Language	Result	Execution time	Memory
57730		Benq	Multiply (CEOI17_mul)	C++14	100 / 100	90 ms	6792 KiB

mul

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

namespace NTT {
    const ll mod = (119 << 23) + 1, root = 3; // = 998244353
    // For p < 2^30 there is also e.g. (5 << 25, 3), (7 << 26, 3),
    // (479 << 21, 3) and (483 << 21, 5). The last two are > 10^9.
        
    ll modpow(ll b, ll p) { return !p?1:modpow(b*b%mod,p/2)*(p&1?b:1)%mod; }
    
    ll inv (ll b) { return modpow(b,mod-2); }
    
    int get(int s) {
        return s > 1 ? 32 - __builtin_clz(s - 1) : 0;
    }
    
    vl ntt(vl& a) { 
        int n = a.size(), x = get(n); 
        vl res, RES(n), roots(n);
        roots[0] = 1, roots[1] = modpow(root,(mod-1)/n);
        FOR(i,2,n) roots[i] = roots[i-1]*roots[1] % mod;
        
        res = a;
        FOR(i,1,x+1) {
            int inc = n>>i;
            F0R(j,inc) for (int k = 0; k < n; k += inc) {
                int t = 2*k%n+j;
                RES[k+j] = (res[t]+roots[k]*res[t+inc]) % mod;
            }
            swap(res,RES);
        }
        
        return res;
    }
    
    vl ntt_rev(vl& a) {
        vl res = ntt(a);
        ll in = inv(a.size());
        F0R(i,sz(res)) res[i] = res[i]*in % mod;
        reverse(res.begin() + 1, res.end());
        return res;
    }
    
    vl brute(vl& a, vl& b) {
        vl c(sz(a)+sz(b)-1);
        F0R(i,sz(a)) F0R(j,sz(b)) c[i+j] = (c[i+j]+a[i]*b[j])%mod;
        return c;
    }
    
    vl conv(vl a, vl b) {
        int s = sz(a)+sz(b)-1, L = get(s), n = 1<<L;
        if (s <= 0) return {};
        if (s <= 200) return brute(a,b);
        
        a.resize(n); a = ntt(a);
        b.resize(n); b = ntt(b);
        
        F0R(i,n) a[i] = a[i]*b[i] % mod;
        a = ntt_rev(a);
        
        a.resize(s);
        return a;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int a,b; cin >> a >> b;
    vl A(a), B(b);
    F0R(i,a) {
        char c; cin >> c;
        A[a-1-i] = c-'0';
    }
    F0R(i,b) {
        char c; cin >> c;
        B[b-1-i] = c-'0';
    }
    vl C = NTT::conv(A,B);
    F0R(i,sz(C)) if (C[i] >= 10) {
        if (i+1 == sz(C)) C.pb(0);
        C[i+1] += C[i]/10; C[i] %= 10;
    }
    while (sz(C) > 1 && C.back() == 0) C.pop_back();
    F0Rd(i,sz(C)) cout << C[i];
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30