// バグってるから https://yukicoder.me/problems/no/81 でチェック // https://yukicoder.me/problems/593 これも良いかも // 小数第何位までの出力ってのもあって良いかも // Atcoder の MPI を最新にしてるから一応 verify しよう #include #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)< class BMPI : public deque { private: static constexpr int root = 5; static constexpr int MOD_ = 924844033; bool sign, zero; long long ex; static void trim_digit(BMPI& num){ while((int)num.size() >= 1 && num.back() == 0) num.pop_back(); if((int)num.size() == 1 && num[0] == 0){ num.zero = true; return; } while((int)num.size() < acc) num.push_front(0), num.ex--; while((int)num.size() > acc + 1) num.pop_front(), num.ex++; rounding(num); } static void rounding(BMPI& num){ if((int)num.size() != acc + 1) return; if(num[0] >= 5){ int pos = 1; do{ num[pos]++; if(num[pos] != 10) break; num[pos] = 0; }while(++pos <= acc); if(pos == acc+1) num.push_back(1), num.pop_back(), num.ex++; } num.pop_front(), num.ex++; } static bool abs_less(const BMPI& a, const BMPI& b){ if(a.ex != b.ex) return a.ex < b.ex; for(int index = acc - 1; index >= 0; index--){ if(a[index] != b[index]) return a[index] < b[index]; } return false; } static void num_sbst(BMPI& a, const BMPI& b){ a.resize(acc), a.zero = false, a.ex = b.ex; for(int i = 0; i < acc; i++) a[i] = b[i]; } static void add(const BMPI& a, const BMPI& b, BMPI& res){ int diff = a.ex - b.ex, carry = 0; if(abs(diff) > acc) return (diff > 0) ? num_sbst(res, a) : num_sbst(res, b); if(diff >= 0){ num_sbst(res, a); if(diff) res.push_front(0), res.ex--; for(int i = !diff; i <= acc; i++){ int val = res[i-!diff] + (i <= acc-diff ? b[i+diff-1] : 0) + carry; carry = val/10; res[i-!diff] = val%10; } if(carry) res.push_back(1); }else{ num_sbst(res, b); res.push_front(0), res.ex--; for(int i = 0; i <= acc; i++){ int val = res[i] + (i <= acc+diff ? a[i-diff-1] : 0) + carry; carry = val/10; res[i] = val%10; } if(carry) res.push_back(1); } trim_digit(res); } static void sub(const BMPI& a, const BMPI& b, BMPI& res){ int diff = a.ex - b.ex, carry = 0; num_sbst(res, a); if(diff > acc) return; if(diff){ res.push_front(0), res.ex--; int carry = 0; for(int i = 0; i <= acc; i++){ int val = res[i] - carry - (i <= acc-diff ? b[i+diff-1] : 0); if(val < 0){ carry = 1, val += 10; }else{ carry = 0; } res[i] = val; } }else{ for(int i = 0; i < acc; i++){ int val = res[i] - carry - b[i]; if(val < 0){ carry = 1, val += 10; }else{ carry = 0; } res[i] = val; } } trim_digit(res); } static int add_(const int x, const int y) { return (x + y < MOD_) ? x + y : x + y - MOD_; } static int mul_(const int x, const int y) { return (long long)x * y % MOD_; } static int power(int x, int n){ int res = 1; while(n > 0){ if(n & 1) res = mul_(res, x); x = mul_(x, x); n >>= 1; } return res; } static int inverse(const int x) { return power(x, MOD_ - 2); } static void ntt(vector& a, const bool rev = false){ int i,j,k,s,t,v,w,wn; const int size = (int)a.size(); const int height = (int)log2(2 * size - 1); for(i = 0; i < size; i++){ j = 0; for(k = 0; k < height; k++) j |= (i >> k & 1) << (height - 1 - k); if(i < j) std::swap(a[i], a[j]); } for(i = 1; i < size; i *= 2) { w = power(root, (MOD_ - 1) / (i * 2)); if(rev) w = inverse(w); for(j = 0; j < size; j += i * 2){ wn = 1; for(k = 0; k < i; k++){ s = a[j + k], t = mul_(a[j + k + i], wn); a[j + k] = add_(s, t); a[j + k + i] = add_(s, MOD_ - t); wn = mul_(wn, w); } } } if(rev){ v = inverse(size); for (i = 0; i < size; i++) a[i] = mul_(a[i], v); } } static void mul(const BMPI& a, const BMPI& b, BMPI& res){ const int size = (int)a.size() + (int)b.size() - 1; int t = 1; while (t < size) t <<= 1; vector A(t, 0), B(t, 0); for(int i = 0; i < (int)a.size(); i++) A[i] = a[i]; for(int i = 0; i < (int)b.size(); i++) B[i] = b[i]; ntt(A), ntt(B); for(int i = 0; i < t; i++) A[i] = mul_(A[i], B[i]); ntt(A, true); res.resize(size); int carry = 0; for(int i = 0; i < size; i++){ int val = A[i] + carry; carry = val / 10; res[i] = val % 10; } if(carry) res.push_back(carry); trim_digit(res); } class MPI : public deque { public: MPI(){ push_back(0); } inline static void trim_digit(MPI& num){ while(num.back() == 0 && (int)num.size() >= 2) num.pop_back(); } bool isZero() const { return (int)size() == 1 && (*this)[0] == 0; } static void add(const MPI& a, const MPI& b, MPI& res){ res = a; int mx = (int)max(a.size(), b.size()); res.resize(mx, 0); int carry = 0; for(int i = 0; i < mx; i++){ int val = res[i] + ((i < (int)b.size()) ? b[i] : 0) + carry; carry = val/10; res[i] = val%10; } if(carry) res.push_back(1); } static void sub(const MPI& a, const MPI& b, MPI& res){ res = a; int carry = 0; for(int i = 0; i < (int)res.size(); i++){ int val = res[i] - carry - ((i < (int)b.size()) ? b[i] : 0); if(val < 0){ carry = 1, val += 10; }else{ carry = 0; } res[i] = val; } trim_digit(res); } bool operator<(const MPI& another) const { if(size() != another.size()) return size() < another.size(); for(int index = (int)size() - 1; index >= 0; index--){ if((*this)[index] != another[index]) return (*this)[index] < another[index]; } return false; } static bool div_geq(const MPI& mod, const MPI& num){ if((int)mod.size() != (int)num.size()) return (int)mod.size() > (int)num.size(); int n = (int)mod.size(); for(int i = 0; i < n; i++){ if(mod[n-1-i] != num[n-1-i]){ return mod[n-1-i] > num[n-1-i]; } } return true; } static void div_(const MPI& a, const MPI& b, MPI& res){ vector mult(9); MPI mod; mult[0] = b; for(int i = 0; i < 8; i++) add(mult[i], b, mult[i+1]); for(int i = (int)a.size() - 1; i >= 0; i--){ if(mod.isZero()){ mod.back() = a[i]; }else{ mod.push_front(a[i]); } if(div_geq(mod, b)){ int l = 0, r = 9; while(r-l>1){ int mid = (l+r)/2; if(mod < mult[mid]){ r = mid; }else{ l = mid; } } MPI mod_ = mod; sub(mod_, mult[l], mod); res.push_front(l+1); }else{ res.push_front(0); } } trim_digit(res); } }; static void mpi_bmpi(MPI& a, const BMPI& b){ if(b.zero){ a = MPI(0); return; } int n = (int)b.size(); a.resize(n); for(int i = 0; i < n; i++) a[i] = b[i]; } static void bmpi_mpi(BMPI& a, const MPI& b){ if(b.isZero()){ a = BMPI(); return; } int n = (int)b.size(); a.resize(n); for(int i = 0; i < n; i++) a[i] = b[i]; } public: BMPI() : zero(true){} BMPI(long long val) : sign(false), zero(false), ex(0){ if(val == 0){ zero = true; return; } if(val < 0) sign = true, val = -val; while(val) push_back(val%10), val /= 10; trim_digit(*this); } BMPI(const string& s) : sign(false), zero(false), ex(0){ if(s.empty() || s == "0"){ zero = true; return; } if(s[0] == '-') sign = true; for(int i = (int)s.size() - 1; i >= sign; i--){ if(s[i] == '.'){ ex = i + 1 - (int)s.size(); }else{ push_back(s[i]-'0'); } } trim_digit(*this); } friend ostream& operator<<(ostream& os, const BMPI& num) { if(num.zero){ os << "0."; for(int i = 0; i < 10; i++) os << '0'; return os; } if(num.sign) os << '-'; for(int i = max(num.ex+acc-1,0LL); i >= -10; i--){ os << ((i-num.ex >= 0 || i-num.ex >= acc)?num[i-num.ex]:'0'); if(i == 0) os << '.'; } return os; // if(num.zero){ os << "0."; for(int i = 0; i < acc-1; i++) os << '0'; // os << "+e0"; return os; } // if(num.sign) os << '-'; // os << num.back() << '.'; // for(int i = 0; i < acc-1; i++) os << num[acc-2-i]; // os << 'e'; // if(num.ex+acc-1 >= 0) os << '+'; // os << num.ex+acc-1; // return os; } friend istream& operator>>(istream& is, BMPI& num) { string s; is >> s; num = BMPI(s); return is; } BMPI& operator=(long long num) { *this = BMPI(num); return *this; } BMPI& operator=(double num) { *this = BMPI(num); return *this; } bool operator<(const BMPI& num) const { if(zero) return !num.zero && !num.sign; if(num.zero) return sign; if(sign ^ num.sign) return sign; if(ex != num.ex) return (ex < num.ex) ^ sign; for(int index = acc - 1; index >= 0; index--){ if((*this)[index] != num[index]) return ((*this)[index] < num[index]) ^ sign; } return false; } bool operator<(const long long num) const { return *this < BMPI(num); } friend bool operator<(const long long num, const BMPI& another){ return BMPI(num) < another; } bool operator>(const BMPI& num) const { return num < *this; } bool operator>(const long long num) const { return *this > BMPI(num); } friend bool operator>(const long long num, const BMPI& another){ return BMPI(num) > another; } bool operator<=(const BMPI& num) const { return !(*this > num); } bool operator<=(const long long num) const { return *this <= BMPI(num); } friend bool operator<=(const long long num, const BMPI& another){ return BMPI(num) <= another; } bool operator>=(const BMPI& num) const { return !(*this < num); } bool operator>=(const long long num) const { return *this >= BMPI(num); } friend bool operator>=(const long long num, const BMPI& another){ return BMPI(num) >= another; } bool operator==(const BMPI& num) const { if(zero || num.zero) return zero && num.zero; if(sign ^ num.sign) return false; if(ex != num.ex) return false; for(int index = acc - 1; index >= 0; index--){ if((*this)[index] != num[index]) return false; } return true; } bool operator==(const long long num) const { return *this == BMPI(num); } friend bool operator==(const long long num, const BMPI& another){ return BMPI(num) == another; } bool operator!=(const BMPI& num) const { return !(*this == num); } bool operator!=(const long long num) const { return *this != BMPI(num); } friend bool operator!=(const long long num, const BMPI& another){ return BMPI(num) != another; } explicit operator bool() const noexcept { return !zero; } bool operator!() const noexcept { return !static_cast(*this); } explicit operator int() const noexcept { return (int)this->to_ll(); } explicit operator long long() const noexcept { return this->to_ll(); } BMPI operator+() const { return *this; } BMPI operator-() const { BMPI res = *this; res.sign = !sign; return res; } friend BMPI abs(const BMPI& num){ BMPI res = num; res.sign = false; return res; } BMPI operator+(const BMPI& num) const { if(zero){ BMPI res = num; return res; } if(num.zero){ BMPI res = *this; return res; } BMPI res; res.sign = sign; if(sign != num.sign){ if(abs_less(*this, num)){ res.sign = num.sign; sub(num, *this, res); return res; }else{ sub(*this, num, res); return res; } } add(*this, num, res); return res; } BMPI operator+(long long num) const { return *this + BMPI(num); } friend BMPI operator+(long long a, const BMPI& b){ return b + a; } BMPI& operator+=(const BMPI& num){ *this = *this + num; return *this; } BMPI& operator+=(long long num){ *this = *this + num; return *this; } BMPI& operator++(){ return *this += 1; } BMPI operator++(int){ BMPI res = *this; *this += 1; return res; } BMPI operator-(const BMPI& num) const { if(zero){ BMPI res = num; res.sign = !res.sign; return res; } if(num.zero){ BMPI res = *this; return res; } if(sign != num.sign){ BMPI res; res.sign = sign; add(*this, num, res); return res; } BMPI res; res.sign = (abs_less(*this, num) ^ sign); if(res.sign){ sub(num, *this, res); }else{ sub(*this, num, res); } return res; } BMPI operator-(long long num) const { return *this - BMPI(num); } friend BMPI operator-(long long a, const BMPI& b){ return b - a; } BMPI& operator-=(const BMPI& num){ *this = *this - num; return *this; } BMPI& operator-=(long long num){ *this = *this - num; return *this; } BMPI& operator--(){ return *this -= 1; } BMPI operator--(int){ BMPI res = *this; *this -= 1; return res; } BMPI operator*(const BMPI& num) const { if(zero || num.zero) return BMPI(); BMPI res; res.zero = false; res.sign = (sign^num.sign); res.ex = ex + num.ex; mul(*this, num, res); return res; } BMPI operator*(long long num) const { return *this * BMPI(num); } friend BMPI operator*(long long a, const BMPI& b){ return b * a; } BMPI& operator*=(const BMPI& num){ *this = *this * num; return *this; } BMPI& operator*=(long long num){ *this = *this * num; return *this; } BMPI operator/(const BMPI& num) const { assert(!num.zero); if(zero){ return BMPI(); } MPI kp, res_, num_; mpi_bmpi(num_, num); BMPI res; res.zero = false; res.sign = (sign^num.sign); res.ex = ex - num.ex; mpi_bmpi(kp, *this); if(abs_less(*this, num)) kp.push_front(0), res.ex--; for(int i = 0; i < acc; i++) kp.push_front(0), res.ex--; MPI::div_(kp, num_, res_); bmpi_mpi(res, res_); trim_digit(res); return res; } BMPI operator/(long long num) const { return *this / BMPI(num); } friend BMPI operator/(long long a, const BMPI& b){ return b / a; } BMPI& operator/=(const BMPI& num){ *this = *this / num; return *this; } BMPI& operator/=(long long num){ *this = *this / num; return *this; } BMPI div2() const { if(zero) return BMPI(); BMPI res = *this; int carry = 0; for(int i = acc-1; i >= 0; i--){ int val = (*this)[i]+carry*10; carry = val%2; if(i != acc-1 || val >= 2){ res[i] = val/2; }else{ res[i] = 0; } } if(carry) res.push_front(5), res.ex--; trim_digit(res); return res; } friend BMPI sqrt(BMPI x){ if(x <= BMPI(0)) return BMPI(); BMPI s = 1, t = x; while(s < t){ s = s + s, t = t.div2(); } do{ t = s, s = (x / s + s).div2(); }while(s < t); trim_digit(t); return t; } friend BMPI log10(const BMPI& x){ assert(x > BMPI(0)); return BMPI(acc + x.ex); } friend BMPI pow(BMPI a, BMPI b){ if(b.zero) return BMPI(1); if(a.zero) return BMPI(); assert(!b.sign); BMPI res(1); while(b){ if(b[0] % 2) res *= a; a *= a; b = b.div2(); } return res; } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector > vec; rep(i,n){ string s; cin >> s; vec.emplace_back(s); } cout << accumulate(all(vec), BMPI<100>(0)) << "\n"; return 0; }