#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
namespace bigint_space {
#ifndef _GLIBCXX_VECTOR
#error You should include header <vector>!
#endif
#if __cplusplus < 201103L
#error The lib is only available with c++11!
#endif
typedef long long ll;
struct bigint : vector<int> {
bool less0 = false;
bigint(ll a = 0)
{
clear();
if(a == 0) push_back(0);
if(a < 0) less0 = true, a = -a;
while(a != 0) push_back(a%10), a /= 10;
}
ll to_ll()
{
ll ans = 0;
int n = min(18, (int)size()-1);
for(int i = n; i >= 0; i--)
ans = ans*10 + (*this)[i];
return ans;
}
};
namespace ntt{
const int P = 998244353;
const int g = 3, gi = 332748118;
int lim, bit;
vector<int> r;
inline ll qpow(ll a, ll b)
{
ll ans = 1;
for(; b; b >>= 1, a = a*a%P)
if(b&1) ans = ans*a%P;
return ans;
}
inline void dnt_prework(int n)
{
lim = 1, bit = 0;
while(lim < n+1) lim <<= 1, bit++;
r.resize(lim);
for(int i = 0; i < lim; i++)
r[i] = (r[i>>1]>>1) | ((i&1)<<(bit-1));
}
inline void dnt(bigint &a)
{
a.resize(lim);
for(int i = 0; i < lim; i++)
if(i < r[i]) swap(a[i], a[r[i]]);
for(int mid = 1; mid < lim; mid <<= 1)
{
ll wn = qpow(g, (P-1)/(mid<<1));
for(int j = 0, k = 0; j < lim; j += (mid<<1), k = j)
{
for(ll w = 1; k < j+mid; k++, w = w*wn%P)
{
ll x = a[k], y = w*a[k+mid]%P;
a[k] = (x+y)%P, a[k+mid] = (x-y+P)%P;
}
}
}
}
inline void idnt(bigint &a)
{
a.resize(lim);
for(int i = 0; i < lim; i++)
if(i < r[i]) swap(a[i], a[r[i]]);
for(int mid = 1; mid < lim; mid <<= 1)
{
ll wn = qpow(gi, (P-1)/(mid<<1));
for(int j = 0, k = 0; j < lim; j += (mid<<1), k = j)
{
for(ll w = 1; k < j+mid; k++, w = w*wn%P)
{
ll x = a[k], y = w*a[k+mid]%P;
a[k] = (x+y)%P, a[k+mid] = (x-y+P)%P;
}
}
}
ll inv = qpow(lim, P-2);
for(int i = 0; i < lim; i++)
a[i] = a[i]*inv%P;
}
}
bigint operator - (const bigint &a);
bigint operator - (const bigint &a, const bigint &b);
bigint operator + (const bigint &a, const bigint &b);
bigint operator * (bigint a, bigint b);
bigint operator / (const bigint &a, ll b);
bigint operator % (const bigint &a, ll b);
bigint& operator += (bigint &a, const bigint &b);
bigint& operator -= (bigint &a, const bigint &b);
bigint& operator *= (bigint &a, const bigint &b);
bigint& operator /= (bigint &a, const ll &b);
bigint& operator %= (bigint &a, const ll &b);
bigint operator ++ (bigint &a);
bigint operator ++ (bigint &a, int);
bool operator < (const bigint &a, const bigint &b);
bool operator > (const bigint &a, const bigint &b);
bool operator == (const bigint &a, const bigint &b);
bool operator != (const bigint &a, const bigint &b);
bool operator <= (const bigint &a, const bigint &b);
bool operator >= (const bigint &a, const bigint &b);
bigint min(const bigint &a, const bigint &b);
bigint max(const bigint &a, const bigint &b);
bigint abs(const bigint &a);
bigint abs(const bigint &a)
{
bigint c = a;
c.less0 = 0;
return c;
}
bigint operator + (const bigint &a, const bigint &b)
{
if(a.less0 and b.less0) return -(-a+(-b));
else if(a.less0) return b-(-a);
else if(b.less0) return a-(-b);
bigint c = a; c.resize(a.size()+1);
if(a.size() < b.size()) c.resize(b.size()+1);
for(int i = 0; i < b.size(); i++)
c[i] += b[i];
for(int i = 0; i < c.size()-1; i++)
c[i+1] += c[i]/10, c[i] %= 10;
while(c.size() > 1 and *(--c.end()) == 0)
c.pop_back();
return c;
}
bigint operator - (const bigint &a)
{
if(a == 0) return a;
bigint c = a;
c.less0 ^= 1;
return c;
}
bigint operator - (const bigint &a, const bigint &b)
{
if(a.less0) return -(-a+b);
if(b.less0) return a+(-b);
bigint c = a; c.resize(a.size());
if(b.size() < b.size()) c.resize(b.size());
for(int i = 0; i < b.size(); i++)
c[i] -= b[i];
for(int i = 0; i < c.size(); i++)
if(c[i] < 0) c[i] += 10, c[i+1] -= 1;
while(c.size() > 1 and *(--c.end()) == 0)
c.pop_back();
if(abs(c) == 0) c.less0 = false;
return c;
}
bigint operator * (bigint a, bigint b)
{
bool opt = a.less0^b.less0;
if(a.size()+b.size() < 500 or a.size() < 10 or b.size() < 10)
{
bigint c; c.resize(a.size()+b.size()+1);
for(int i = 0; i < a.size(); i++)
for(int j = 0; j < b.size(); j++)
c[i+j] += a[i]*b[j];
for(int i = 0; i < c.size(); i++)
c[i+1] += c[i]/10, c[i] %= 10;
while(c.size() > 1 and *(--c.end()) == 0)
c.pop_back();
if(abs(c) == 0) c.less0 = false;
else c.less0 = opt;
return c;
}
else
{
ntt::dnt_prework(a.size()+b.size());
ntt::dnt(a); ntt::dnt(b);
for(int i = 0; i < ntt::lim; i++)
a[i] = (ll)a[i]*b[i] % ntt::P;
ntt::idnt(a);
for(int i = 0; i < ntt::lim-1; i++)
a[i+1] += a[i]/10, a[i] %= 10;
while(a.size() > 1 and *(--a.end()) == 0)
a.pop_back();
if(abs(a) == 0) a.less0 = false;
else a.less0 = opt;
return a;
}
}
bigint operator / (const bigint &c, ll b)
{
ll tmp = 0; bigint a = c;
bool opt = c.less0^(b<0);
if(b < 0) b = -b;
for(int i = a.size()-1; i >= 0; i--)
{
tmp = tmp*10 + a[i];
a[i] = tmp/b;
tmp %= b;
}
while(a.size() > 1 and *(--a.end()) == 0)
a.pop_back();
if(abs(a) == 0) a.less0 = false;
else a.less0 = opt;
return a;
}
bigint operator % (const bigint &c, ll b)
{
bigint a = c;
return a - (a/b)*b;
}
bigint& operator += (bigint &a, const bigint &b) { return a = a+b; }
bigint& operator -= (bigint &a, const bigint &b) { return a = a-b; }
bigint& operator *= (bigint &a, const bigint &b) { return a = a*b; }
bigint& operator /= (bigint &a, const ll &b) { return a = a/b; }
bigint& operator %= (bigint &a, const ll &b) { return a = a%b; }
bigint operator ++ (bigint &a) { return a = a+1;}
bigint operator ++ (bigint &a, int) { bigint b = a; a = a+1; return b;}
bool operator == (const bigint &a, const bigint &b)
{
if(a.less0 != b.less0) return false;
if(a.size() != b.size()) return false;
for(int i = a.size()-1; i >= 0; i--)
if(a[i] != b[i]) return false;
return true;
}
bool operator != (const bigint &a, const bigint &b)
{
return !(a == b);
}
bool operator < (const bigint &a, const bigint &b)
{
if(a.less0 and b.less0) return -b < -a;
else if(a.less0) return false;
else if(b.less0) return true;
if(a.size() != b.size()) return a.size() < b.size();
for(int i = a.size()-1; i >= 0; i--)
if(a[i] != b[i]) return a[i] < b[i];
return false;
}
bool operator > (const bigint &a, const bigint &b)
{
return b < a;
}
bool operator <= (const bigint &a, const bigint &b)
{
return !(b < a);
}
bool operator >= (const bigint &a, const bigint &b)
{
return !(a < b);
}
bigint min(const bigint &a, const bigint &b)
{
return a < b ? a : b;
}
bigint max(const bigint &a, const bigint &b)
{
return a > b ? a : b;
}
#define isdigit(c) ('0' <= c and c <= '9')
#ifdef _GLIBCXX_IOSTREAM
istream& operator >> (istream& cin, bigint& a)
{
a.clear();
char c = cin.get();
vector<char> tmp;
while(!isdigit(c))
{
if(c == '-') a.less0 = true;
c = cin.get();
}
while(isdigit(c))
{
tmp.push_back(c);
c = cin.get();
}
for(auto i = tmp.rbegin(); i != tmp.rend(); i++)
a.push_back(*i-'0');
while(a.size() > 0 and *(--a.end()) == 0)
a.pop_back();
if(a.size() == 0) a = 0;
return cin;
}
ostream& operator << (ostream& cout, const bigint& a)
{
if(a.less0) cout.put('-');
for(auto i = a.rbegin(); i != a.rend(); i++)
cout.put(*i+'0');
return cout;
}
#endif
#ifdef _GLIBCXX_CSTDIO
void read(bigint &a)
{
a.clear();
char c = getchar();
vector<char> tmp;
while(!isdigit(c))
{
if(c == '-') a.less0 = true;
c = getchar();
}
while(isdigit(c))
{
tmp.push_back(c);
c = getchar();
}
for(auto i = tmp.rbegin(); i != tmp.rend(); i++)
a.push_back(*i-'0');
if(a.size() == 0) a = 0;
}
void print(const bigint &a)
{
if(a.less0) putchar('-');
for(auto i = a.rbegin(); i != a.rend(); i++)
putchar(*i+'0');
}
#endif
#undef isdigit
}
using namespace bigint_space;
|
