結果
問題 | No.1334 Multiply or Add |
ユーザー | mtsd |
提出日時 | 2021-01-08 23:02:39 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 24,444 bytes |
コンパイル時間 | 2,172 ms |
コンパイル使用メモリ | 147,760 KB |
実行使用メモリ | 10,736 KB |
最終ジャッジ日時 | 2024-11-16 15:12:33 |
合計ジャッジ時間 | 5,238 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
5,888 KB |
testcase_01 | AC | 4 ms
5,888 KB |
testcase_02 | AC | 4 ms
5,888 KB |
testcase_03 | AC | 17 ms
7,296 KB |
testcase_04 | AC | 16 ms
7,296 KB |
testcase_05 | AC | 15 ms
7,368 KB |
testcase_06 | AC | 16 ms
7,424 KB |
testcase_07 | AC | 17 ms
7,364 KB |
testcase_08 | AC | 15 ms
7,296 KB |
testcase_09 | AC | 16 ms
7,296 KB |
testcase_10 | AC | 33 ms
7,296 KB |
testcase_11 | AC | 16 ms
7,296 KB |
testcase_12 | AC | 20 ms
7,296 KB |
testcase_13 | AC | 16 ms
7,296 KB |
testcase_14 | AC | 15 ms
7,364 KB |
testcase_15 | AC | 15 ms
7,296 KB |
testcase_16 | AC | 16 ms
7,296 KB |
testcase_17 | AC | 17 ms
7,424 KB |
testcase_18 | AC | 21 ms
7,424 KB |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 16 ms
7,168 KB |
testcase_23 | AC | 17 ms
7,296 KB |
testcase_24 | AC | 16 ms
7,424 KB |
testcase_25 | AC | 18 ms
7,296 KB |
testcase_26 | AC | 16 ms
7,424 KB |
testcase_27 | AC | 16 ms
7,424 KB |
testcase_28 | AC | 16 ms
7,296 KB |
testcase_29 | AC | 17 ms
7,296 KB |
testcase_30 | AC | 15 ms
7,296 KB |
testcase_31 | AC | 16 ms
7,296 KB |
testcase_32 | AC | 20 ms
7,296 KB |
testcase_33 | AC | 15 ms
7,296 KB |
testcase_34 | AC | 16 ms
7,296 KB |
testcase_35 | AC | 16 ms
7,296 KB |
testcase_36 | AC | 16 ms
7,296 KB |
testcase_37 | AC | 16 ms
7,296 KB |
testcase_38 | AC | 17 ms
7,296 KB |
testcase_39 | AC | 4 ms
5,888 KB |
testcase_40 | AC | 9 ms
6,400 KB |
testcase_41 | AC | 6 ms
6,016 KB |
testcase_42 | AC | 6 ms
5,932 KB |
testcase_43 | AC | 12 ms
6,856 KB |
testcase_44 | AC | 9 ms
6,400 KB |
testcase_45 | AC | 6 ms
6,060 KB |
testcase_46 | AC | 9 ms
6,400 KB |
testcase_47 | AC | 11 ms
6,784 KB |
testcase_48 | AC | 9 ms
6,400 KB |
testcase_49 | AC | 15 ms
7,168 KB |
testcase_50 | AC | 31 ms
10,624 KB |
testcase_51 | AC | 30 ms
10,604 KB |
testcase_52 | AC | 31 ms
10,580 KB |
testcase_53 | AC | 31 ms
10,600 KB |
testcase_54 | AC | 30 ms
10,736 KB |
testcase_55 | AC | 33 ms
10,476 KB |
testcase_56 | AC | 3 ms
5,760 KB |
testcase_57 | AC | 4 ms
5,760 KB |
testcase_58 | AC | 4 ms
5,888 KB |
testcase_59 | AC | 4 ms
6,016 KB |
testcase_60 | AC | 3 ms
5,888 KB |
testcase_61 | AC | 4 ms
5,760 KB |
testcase_62 | AC | 3 ms
5,888 KB |
testcase_63 | AC | 4 ms
6,016 KB |
testcase_64 | AC | 4 ms
5,760 KB |
testcase_65 | AC | 4 ms
5,760 KB |
testcase_66 | AC | 26 ms
9,640 KB |
testcase_67 | AC | 18 ms
8,240 KB |
testcase_68 | AC | 4 ms
6,016 KB |
testcase_69 | AC | 30 ms
10,212 KB |
testcase_70 | AC | 27 ms
9,992 KB |
ソースコード
#include <algorithm> #include <bitset> #include <cassert> #include <chrono> #include <climits> #include <cmath> #include <complex> #include <cstring> #include <deque> #include <functional> #include <iostream> #include <iomanip> #include <list> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <stack> #include <unordered_map> #include <unordered_set> #include <vector> #include <cstdint> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; #define MP make_pair #define PB push_back #define inf 1000000007 #define rep(i,n) for(int i = 0; i < (int)(n); ++i) #define all(x) (x).begin(),(x).end() template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val){ std::fill( (T*)array, (T*)(array+N), val ); } template<class T> inline bool chmax(T &a, T b){ if(a<b){ a = b; return true; } return false; } template<class T> inline bool chmin(T &a, T b){ if(a>b){ a = b; return true; } return false; } class MPI : public vector<int> { private: static constexpr int root = 3; static constexpr int MOD_ = 998244353; // 2^23 * 119 + 1 (2^22 桁以下の数の積を計算可能) bool sign; static void trim_sign(MPI& num){ if(num.isZero()) num.sign = false; } static void trim_digit(MPI& num){ while(num.back() == 0 && (int)num.size() >= 2) num.pop_back(); } static bool abs_less(const MPI& a, const MPI& b){ if(a.size() != b.size()) return a.size() < b.size(); for(int index = (int)a.size() - 1; index >= 0; index--){ if(a[index] != b[index]) return a[index] < b[index]; } return false; } static void num_sbst(MPI& a, const MPI& b){ int n = (int)b.size(); a.resize(n); for(int i = 0; i < n; i++) a[i] = b[i]; } static void add(const MPI& a, const MPI& b, MPI& res){ num_sbst(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){ num_sbst(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), trim_sign(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<int>& 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 MPI& a, const MPI& b, MPI& res){ const int size = (int)a.size() + (int)b.size() - 1; int t = 1; while (t < size) t <<= 1; vector<int> 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), trim_sign(res); } bool isZero() const { return (int)size() == 1 && (*this)[0] == 0; } 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[i] != num[n-1-i]){ return mod[i] > num[n-1-i]; } } return true; } static void div_(const MPI& a, const MPI& b, MPI& quo, MPI& mod){ vector<MPI> mult(9); mult[0] = b; for(int i = 0; i < 8; i++) mult[i+1] = mult[i] + b; for(int i = (int)a.size() - 1; i >= 0; i--){ if(mod.isZero()){ mod.back() = a[i]; }else{ mod.push_back(a[i]); } if(div_geq(mod, b)){ int l = 0, r = 9; reverse(mod.begin(), mod.end()); while(r-l>1){ int mid = (l+r)/2; if(mult[mid] > mod){ r = mid; }else{ l = mid; } } mod -= mult[l]; reverse(mod.begin(), mod.end()); quo.push_back(l+1); }else{ quo.push_back(0); } } reverse(quo.begin(), quo.end()); trim_digit(quo); reverse(mod.begin(), mod.end()); } public: MPI() : sign(false){ this->push_back(0); } MPI(long long val) : sign(false){ if(val == 0){ this->push_back(0); }else{ if(val < 0) sign = true, val = -val; while(val){ this->push_back(val%10); val /= 10; } } } MPI(const string& s) : sign(false){ if(s.empty()){ this->push_back(0); return; } if(s[0] == '-') sign = true; for(int i = (int)s.size() - 1; i >= sign; i--) this->push_back(s[i]-'0'); } long long to_ll() const { long long res = 0, dig = 1; for(int i = 0; i < (int)size(); i++){ res += dig * (*this)[i], dig *= 10; } if(sign) res = -res; return res; } string to_string() const { int n = (int)size() + sign; string s(n, ' '); if(sign) s[0] = '-'; for(int i = sign; i < n; i++) s[i] = (char)('0'+(*this)[n-1-i]); return s; } friend istream& operator>>(istream& is, MPI& num) { string s; is >> s; num = MPI(s); return is; } friend ostream& operator<<(ostream& os, const MPI& num) { if(num.sign) os << '-'; for(int i = (int)num.size()-1; i >= 0; i--) os << (char)('0'+num[i]); return os; } MPI& operator=(long long val) { *this = MPI(val); return *this; } bool operator<(const MPI& another) const { if(sign ^ another.sign) return sign; if(size() != another.size()) return (size() < another.size()) ^ sign; for(int index = (int)size() - 1; index >= 0; index--){ if((*this)[index] != another[index]) return ((*this)[index] < another[index]) ^ sign; } return false; } bool operator<(const long long num) const { return *this < MPI(num); } friend bool operator<(const long long num, const MPI& another){ return MPI(num) < another; } bool operator>(const MPI& another) const { return another < *this; } bool operator>(const long long num) const { return *this > MPI(num); } friend bool operator>(const long long num, const MPI& another){ return MPI(num) > another; } bool operator<=(const MPI& another) const { return !(*this > another); } bool operator<=(const long long num) const { return *this <= MPI(num); } friend bool operator<=(const long long num, const MPI& another){ return MPI(num) <= another; } bool operator>=(const MPI& another) const { return !(*this < another); } bool operator>=(const long long num) const { return *this >= MPI(num); } friend bool operator>=(const long long num, const MPI& another){ return MPI(num) >= another; } bool operator==(const MPI& another) const { if(sign ^ another.sign) return false; if(size() != another.size()) return false; for(int index = (int)size() - 1; index >= 0; index--){ if((*this)[index] != another[index]) return false; } return true; } bool operator==(const long long num) const { return *this == MPI(num); } friend bool operator==(const long long num, const MPI& another){ return MPI(num) == another; } bool operator!=(const MPI& another) const { return !(*this == another); } bool operator!=(const long long num) const { return *this != MPI(num); } friend bool operator!=(const long long num, const MPI& another){ return MPI(num) != another; } explicit operator bool() const noexcept { return !isZero(); } bool operator!() const noexcept { return !static_cast<bool>(*this); } explicit operator int() const noexcept { return (int)this->to_ll(); } explicit operator long long() const noexcept { return this->to_ll(); } MPI operator+() const { return *this; } MPI operator-() const { MPI res = *this; res.sign = !sign; return res; } friend MPI abs(const MPI& num){ MPI res = num; res.sign = false; return res; } MPI operator+(const MPI& num) const { MPI 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; } MPI operator+(long long num) const { return *this + MPI(num); } friend MPI operator+(long long a, const MPI& b){ return b + a; } MPI& operator+=(const MPI& num){ *this = *this + num; return *this; } MPI& operator+=(long long num){ *this = *this + num; return *this; } MPI& operator++(){ return *this += 1; } MPI operator++(int){ MPI res = *this; *this += 1; return res; } MPI operator-(const MPI& num) const { if(sign != num.sign){ MPI res; res.sign = sign; add(*this, num, res); return res; } MPI res; res.sign = (abs_less(*this, num) ^ sign); if(res.sign){ sub(num, *this, res); }else{ sub(*this, num, res); } return res; } MPI operator-(long long num) const { return *this - MPI(num); } friend MPI operator-(long long a, const MPI& b){ return b - a; } MPI& operator-=(const MPI& num){ *this = *this - num; return *this; } MPI& operator-=(long long num){ *this = *this - num; return *this; } MPI& operator--(){ return *this -= 1; } MPI operator--(int){ MPI res = *this; *this -= 1; return res; } MPI operator*(const MPI& num) const { MPI res; res.sign = (sign^num.sign); mul(*this, num, res); return res; } MPI operator*(long long num) const { return *this * MPI(num); } friend MPI operator*(long long a, const MPI& b){ return b * a; } MPI& operator*=(const MPI& num){ *this = *this * num; return *this; } MPI& operator*=(long long num){ *this = *this * num; return *this; } MPI operator/(const MPI& num) const { MPI num_ = abs(num); MPI a, b; div_(*this, num_, a, b); a.sign = (sign^num.sign); trim_sign(a); return a; } MPI operator/(long long num) const { return *this / MPI(num); } friend MPI operator/(long long a, const MPI& b){ return b / a; } MPI& operator/=(const MPI& num){ *this = *this / num; return *this; } MPI& operator/=(long long num){ *this = *this / num; return *this; } MPI operator%(const MPI& num) const { MPI num_ = abs(num); MPI a, b; div_(*this, num_, a, b); b.sign = sign; trim_sign(b); return b; } MPI operator%(long long num) const { return *this % MPI(num); } friend MPI operator%(long long a, const MPI& b){ return b % a; } MPI& operator%=(const MPI& num){ *this = *this % num; return *this; } MPI& operator%=(long long num){ *this = *this % num; return *this; } MPI div2() const { MPI res; res.sign = sign; int n = (int)this->size(), carry = 0; for(int i = n-1; i >= 0; i--){ int val = (*this)[i]+carry*10; carry = val%2; if(i != n-1 || val >= 2) res.push_back(val/2); } reverse(res.begin(), res.end()); trim_digit(res); return res; } friend MPI sqrt(const MPI& x){ if(x <= MPI(0)) return MPI(0); MPI s = 1, t = x; while(s < t){ s = s + s, t = t.div2(); } do{ t = s, s = (x / s + s).div2(); }while(s < t); return t; } friend MPI log10(const MPI& x){ assert(x > MPI(0)); return MPI((int)x.size()); } friend MPI pow(MPI a, MPI b){ assert(b >= 0); MPI res(1); while(b){ if(b[0] % 2){ res *= a; } a *= a; b = b.div2(); } return res; } }; template <unsigned int mod> class ModInt { private: unsigned int v; static unsigned int norm(const unsigned int& x){ return x < mod ? x : x - mod; } static ModInt make(const unsigned int& x){ ModInt m; return m.v = x, m; } static ModInt inv(const ModInt& x){ return make(inverse(x.v, mod)); } static unsigned int inverse(int a, int m){ int u[] = {a, 1, 0}, v[] = {m, 0, 1}, t; while(*v){ t = *u / *v; swap(u[0] -= t * v[0], v[0]), swap(u[1] -= t * v[1], v[1]), swap(u[2] -= t * v[2], v[2]); } return (u[1] % m + m) % m; } public: ModInt() : v{0}{} ModInt(const long long val) : v{norm(val % mod + mod)} {} ModInt(const ModInt<mod>& n) : v{n()} {} explicit operator bool() const noexcept { return v != 0; } bool operator!() const noexcept { return !static_cast<bool>(*this); } ModInt& operator=(const ModInt& n){ return v = n(), (*this); } ModInt& operator=(const long long val){ return v = norm(val % mod + mod), (*this); } ModInt operator+() const { return *this; } ModInt operator-() const { return v == 0 ? make(0) : make(mod - v); } ModInt operator+(const ModInt& val) const { return make(norm(v + val())); } ModInt operator-(const ModInt& val) const { return make(norm(v + mod - val())); } ModInt operator*(const ModInt& val) const { return make((long long)v * val() % mod); } ModInt operator/(const ModInt& val) const { return *this * inv(val); } ModInt& operator+=(const ModInt& val){ return *this = *this + val; } ModInt& operator-=(const ModInt& val){ return *this = *this - val; } ModInt& operator*=(const ModInt& val){ return *this = *this * val; } ModInt& operator/=(const ModInt& val){ return *this = *this / val; } ModInt operator+(const long long val) const { return ModInt{v + val}; } ModInt operator-(const long long val) const { return ModInt{v - val}; } ModInt operator*(const long long val) const { return ModInt{(long long)v * (val % mod)}; } ModInt operator/(const long long val) const { return ModInt{(long long)v * inv(val)}; } ModInt& operator+=(const long long val){ return *this = *this + val; } ModInt& operator-=(const long long val){ return *this = *this - val; } ModInt& operator*=(const long long val){ return *this = *this * val; } ModInt& operator/=(const long long val){ return *this = *this / val; } bool operator==(const ModInt& val) const { return v == val.v; } bool operator!=(const ModInt& val) const { return !(*this == val); } bool operator==(const long long val) const { return v == norm(val % mod + mod); } bool operator!=(const long long val) const { return !(*this == val); } unsigned int operator()() const { return v; } friend ModInt operator+(const long long val, const ModInt& n) { return n + val; } friend ModInt operator-(const long long val, const ModInt& n) { return ModInt{val - n()}; } friend ModInt operator*(const long long val, const ModInt& n) { return n * val; } friend ModInt operator/(const long long val, const ModInt& n) { return ModInt{val} / n; } friend bool operator==(const long long val, const ModInt& n) { return n == val; } friend bool operator!=(const long long val, const ModInt& n) { return !(val == n); } friend istream& operator>>(istream& is, ModInt& n){ unsigned int v; return is >> v, n = v, is; } friend ostream& operator<<(ostream& os, const ModInt& n){ return (os << n()); } friend ModInt mod_pow(ModInt x, long long n){ ModInt ans = 1; while(n){ if(n & 1) ans *= x; x *= x, n >>= 1; } return ans; } }; #define MOD 1000000007 using mod = ModInt<MOD>; #define MAX_N 200000 mod inv[MAX_N],fac[MAX_N],finv[MAX_N]; void make() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for(int i=2;i<MAX_N;i++){ inv[i] = MOD - inv[MOD % i] * (MOD / i); fac[i] = fac[i-1] * i; finv[i] = finv[i-1] * inv[i]; } } mod comb(int a, int b) { if(a<b) return 0; return fac[a] * finv[b] * finv[a-b]; } class UnionFind { private: int sz; vector<int> par, size_; public: UnionFind(){} UnionFind(int node_size) : sz(node_size), par(sz), size_(sz, 1){ iota(par.begin(), par.end(), 0); } int find(int x){ if(par[x] == x) return x; else return par[x] = find(par[x]); } void unite(int x,int y){ x = find(x), y = find(y); if(x == y) return; if(size_[x] < size_[y]) swap(x,y); par[y] = x; size_[x] += size_[y]; } int size(int x){ x = find(x); return size_[x]; } bool same(int x,int y){ return find(x) == find(y); } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector<ll> a(n); rep(i,n) cin >> a[i]; vector<char> res(n); vector<vector<pair<int,int> > > p; vector<pair<int,int> > tmp; int id = 0; while(id!=n){ int k = 0; if(a[id]==1){ while(id!=n&&a[id]==1){ id++; k++; } tmp.push_back(MP(0,k)); }else{ if(a[id]==0){ p.push_back(tmp); tmp.clear(); tmp.push_back(MP(3,0)); p.push_back(tmp); tmp.clear(); id++; }else{ tmp.push_back(MP(1,a[id])); id++; } } } p.push_back(tmp); id = 0; for(auto& x:p){ if(x.size()==0)continue; if(x[0].first==3){ res[id] = '+'; id++; continue; } int m = x.size(); MPI sm = 0; MPI K = 1; bool fflag = 0; rep(i,m){ if(x[i].first==0){ if(i!=0&&i!=m-1){ sm += x[i].second; } }else{ K *= x[i].second; if(K >= 2000000000000000000LL){ fflag = 1; break; } } } if(fflag){ rep(i,m){ if(x[i].first==0){ if(i==0||i==m-1){ rep(j,x[i].second){ res[id] = '+'; id++; } }else{ rep(j,x[i].second){ res[id] = '*'; id++; } } }else{ res[id] = '*'; id++; if(i==m-2&&x[i+1].first==0){ res[id-1] = '+'; } } } res[id-1] = '+'; }else{ MPI mx = 0; int mxbit = 0; rep(bit,1<<(m-1)){ UnionFind uf(m); rep(i,m-1){ if((bit>>i)&1){ uf.unite(i,i+1); } } MPI S = 0; MPI tmp = 1; bool flag = 1; rep(i,m){ if(i==m-1||!uf.same(i,i+1)){ if(flag){ S += x[i].second; }else{ if(x[i].first==0){ }else{ tmp *= x[i].second; } S += tmp; } flag = 1; tmp = 1; }else{ flag = 0; if(x[i].first==0){ }else{ tmp *= x[i].second; } } } if(chmax(mx,S)){ mxbit = bit; } } UnionFind uf(m); rep(i,m-1){ if((mxbit>>i)&1){ uf.unite(i,i+1); } } bool flag = 0; rep(i,m){ if(i==m-1||!uf.same(i,i+1)){ if(x[i].first==0){ rep(j,x[i].second){ res[id] = '+'; id++; } }else{ res[id] = '+'; id++; } flag = 1; }else{ if(x[i].first==0){ rep(j,x[i].second){ res[id] = '*'; id++; } }else{ res[id] = '*'; id++; } flag = 0; } } } } mod ans = 0; mod PP = 1; rep(i,n){ PP *= a[i]; if(i!=n-1){ if(res[i]=='+'){ ans += PP; PP = 1; } } } ans += PP; cout << ans << endl; return 0; }