結果
問題 | No.2171 OR Assignment |
ユーザー | 👑 Nachia |
提出日時 | 2022-12-23 22:40:24 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 26 ms / 3,500 ms |
コード長 | 8,742 bytes |
コンパイル時間 | 838 ms |
コンパイル使用メモリ | 79,248 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-18 07:04:55 |
合計ジャッジ時間 | 2,358 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 1 ms
6,816 KB |
testcase_04 | AC | 1 ms
6,816 KB |
testcase_05 | AC | 1 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,820 KB |
testcase_09 | AC | 2 ms
6,820 KB |
testcase_10 | AC | 1 ms
6,816 KB |
testcase_11 | AC | 1 ms
6,820 KB |
testcase_12 | AC | 13 ms
6,816 KB |
testcase_13 | AC | 14 ms
6,820 KB |
testcase_14 | AC | 14 ms
6,816 KB |
testcase_15 | AC | 7 ms
6,820 KB |
testcase_16 | AC | 7 ms
6,816 KB |
testcase_17 | AC | 8 ms
6,816 KB |
testcase_18 | AC | 15 ms
6,820 KB |
testcase_19 | AC | 14 ms
6,820 KB |
testcase_20 | AC | 19 ms
6,820 KB |
testcase_21 | AC | 18 ms
6,820 KB |
testcase_22 | AC | 20 ms
6,820 KB |
testcase_23 | AC | 23 ms
6,816 KB |
testcase_24 | AC | 26 ms
6,816 KB |
testcase_25 | AC | 24 ms
6,816 KB |
testcase_26 | AC | 24 ms
6,816 KB |
testcase_27 | AC | 24 ms
6,816 KB |
testcase_28 | AC | 25 ms
6,816 KB |
testcase_29 | AC | 25 ms
6,816 KB |
testcase_30 | AC | 25 ms
6,816 KB |
testcase_31 | AC | 23 ms
6,816 KB |
ソースコード
#line 2 "nachia\\math-modulo\\static-modint.hpp" #include <vector> #include <utility> #line 2 "nachia\\math\\ext-gcd.hpp" #line 4 "nachia\\math\\ext-gcd.hpp" #include <algorithm> #include <cassert> namespace nachia{ // ax + by = gcd(a,b) std::pair<long long, long long> ExtGcd(long long a, long long b){ long long x = 1, y = 0; while(b){ long long u = a / b; std::swap(a-=b*u, b); std::swap(x-=y*u, y); } return std::make_pair(x, y); } } // namespace nachia #line 5 "nachia\\math-modulo\\static-modint.hpp" namespace nachia{ template<unsigned int MOD> struct StaticModint{ private: using u64 = unsigned long long; unsigned int x; public: using my_type = StaticModint; template< class Elem > static Elem safe_mod(Elem x){ if(x < 0){ if(0 <= x+MOD) return x + MOD; return MOD - ((-(x+MOD)-1) % MOD + 1); } return x % MOD; } StaticModint() : x(0){} StaticModint(const my_type& a) : x(a.x){} StaticModint& operator=(const my_type&) = default; template< class Elem > StaticModint(Elem v) : x(safe_mod(v)){} unsigned int operator*() const noexcept { return x; } my_type& operator+=(const my_type& r) noexcept { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator+(const my_type& r) const noexcept { my_type res = *this; return res += r; } my_type& operator-=(const my_type& r) noexcept { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; } my_type operator-(const my_type& r) const noexcept { my_type res = *this; return res -= r; } my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; } my_type& operator*=(const my_type& r)noexcept { x = (u64)x * r.x % MOD; return *this; } my_type operator*(const my_type& r) const noexcept { my_type res = *this; return res *= r; } my_type pow(unsigned long long i) const noexcept { my_type a = *this, res = 1; while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; } return res; } my_type inv() const { return my_type(ExtGcd(x, MOD).first); } unsigned int val() const noexcept { return x; } static constexpr unsigned int mod() { return MOD; } static my_type raw(unsigned int val) noexcept { auto res = my_type(); res.x = val; return res; } my_type& operator/=(const my_type& r){ return operator*=(r.inv()); } my_type operator/(const my_type& r) const { return operator*(r.inv()); } }; } #line 2 "nachia\\misc\\fastio.hpp" #include <cstdio> #include <cctype> #include <cstdint> #include <string> namespace nachia{ struct CInStream{ private: static const unsigned int INPUT_BUF_SIZE = 1 << 17; unsigned int p = INPUT_BUF_SIZE; static char Q[INPUT_BUF_SIZE]; public: using MyType = CInStream; char seekChar() noexcept { if(p == INPUT_BUF_SIZE){ size_t len = fread(Q, 1, INPUT_BUF_SIZE, stdin); if(len != INPUT_BUF_SIZE) Q[len] = '\0'; p = 0; } return Q[p]; } void skipSpace() noexcept { while(isspace(seekChar())) p++; } uint32_t nextU32() noexcept { skipSpace(); uint32_t buf = 0; while(true){ char tmp = seekChar(); if('9' < tmp || tmp < '0') break; buf = buf * 10 + (tmp - '0'); p++; } return buf; } int32_t nextI32() noexcept { skipSpace(); if(seekChar() == '-'){ p++; return (int32_t)(-nextU32()); } return (int32_t)nextU32(); } uint64_t nextU64() noexcept { skipSpace(); uint64_t buf = 0; while(true){ char tmp = seekChar(); if('9' < tmp || tmp < '0') break; buf = buf * 10 + (tmp - '0'); p++; } return buf; } int64_t nextI64() noexcept { skipSpace(); if(seekChar() == '-'){ p++; return (int64_t)(-nextU64()); } return (int64_t)nextU64(); } char nextChar() noexcept { skipSpace(); char buf = seekChar(); p++; return buf; } std::string nextToken(){ skipSpace(); std::string buf; while(true){ char ch = seekChar(); if(isspace(ch) || ch == '\0') break; buf.push_back(ch); p++; } return buf; } MyType& operator>>(unsigned int& dest) noexcept { dest = nextU32(); return *this; } MyType& operator>>(int& dest) noexcept { dest = nextI32(); return *this; } MyType& operator>>(unsigned long& dest) noexcept { dest = nextU64(); return *this; } MyType& operator>>(long& dest) noexcept { dest = nextI64(); return *this; } MyType& operator>>(unsigned long long& dest) noexcept { dest = nextU64(); return *this; } MyType& operator>>(long long& dest) noexcept { dest = nextI64(); return *this; } MyType& operator>>(std::string& dest){ dest = nextToken(); return *this; } MyType& operator>>(char& dest) noexcept { dest = nextChar(); return *this; } } cin; struct FastOutputTable{ char LZ[1000][4] = {}; char NLZ[1000][4] = {}; constexpr FastOutputTable(){ using u32 = uint_fast32_t; for(u32 d=0; d<1000; d++){ LZ[d][0] = ('0' + d / 100 % 10); LZ[d][1] = ('0' + d / 10 % 10); LZ[d][2] = ('0' + d / 1 % 10); LZ[d][3] = '\0'; } for(u32 d=0; d<1000; d++){ u32 i = 0; if(d >= 100) NLZ[d][i++] = ('0' + d / 100 % 10); if(d >= 10) NLZ[d][i++] = ('0' + d / 10 % 10); if(d >= 1) NLZ[d][i++] = ('0' + d / 1 % 10); NLZ[d][i++] = '\0'; } } }; struct COutStream{ private: using u32 = uint32_t; using u64 = uint64_t; using MyType = COutStream; static const u32 OUTPUT_BUF_SIZE = 1 << 17; static char Q[OUTPUT_BUF_SIZE]; static constexpr FastOutputTable TB = FastOutputTable(); u32 p = 0; static constexpr u32 P10(u32 d){ return d ? P10(d-1)*10 : 1; } static constexpr u64 P10L(u32 d){ return d ? P10L(d-1)*10 : 1; } template<class T, class U> static void Fil(T& m, U& l, U x) noexcept { m = l/x; l -= m*x; } void next_dig9(u32 x){ u32 y; Fil(y, x, P10(6)); nextCstr(TB.LZ[y]); Fil(y, x, P10(3)); nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]); } public: void nextChar(char c){ Q[p++] = c; if(p == OUTPUT_BUF_SIZE){ fwrite(Q, p, 1, stdout); p = 0; } } void nextEoln(){ nextChar('\n'); } void nextCstr(const char* s){ while(*s) nextChar(*(s++)); } void nextU32(uint32_t x){ u32 y = 0; if(x >= P10(9)){ Fil(y, x, P10(9)); nextCstr(TB.NLZ[y]); next_dig9(x); } else if(x >= P10(6)){ Fil(y, x, P10(6)); nextCstr(TB.NLZ[y]); Fil(y, x, P10(3)); nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]); } else if(x >= P10(3)){ Fil(y, x, P10(3)); nextCstr(TB.NLZ[y]); nextCstr(TB.LZ[x]); } else if(x >= 1) nextCstr(TB.NLZ[x]); else nextChar('0'); } void nextI32(int32_t x){ if(x >= 0) nextU32(x); else{ nextChar('-'); nextU32((u32)-x); } } void nextU64(uint64_t x){ u32 y = 0; if(x >= P10L(18)){ Fil(y, x, P10L(18)); nextU32(y); Fil(y, x, P10L(9)); next_dig9(y); next_dig9(x); } else if(x >= P10L(9)){ Fil(y, x, P10L(9)); nextU32(y); next_dig9(x); } else nextU32(x); } void nextI64(int64_t x){ if(x >= 0) nextU64(x); else{ nextChar('-'); nextU64((u64)-x); } } void writeToFile(bool flush = false){ fwrite(Q, p, 1, stdout); if(flush) fflush(stdout); p = 0; } COutStream(){ Q[0] = 0; } ~COutStream(){ writeToFile(); } MyType& operator<<(unsigned int tg){ nextU32(tg); return *this; } MyType& operator<<(unsigned long tg){ nextU64(tg); return *this; } MyType& operator<<(unsigned long long tg){ nextU64(tg); return *this; } MyType& operator<<(int tg){ nextI32(tg); return *this; } MyType& operator<<(long tg){ nextI64(tg); return *this; } MyType& operator<<(long long tg){ nextI64(tg); return *this; } MyType& operator<<(const std::string& tg){ nextCstr(tg.c_str()); return *this; } MyType& operator<<(const char* tg){ nextCstr(tg); return *this; } MyType& operator<<(char tg){ nextChar(tg); return *this; } } cout; char CInStream::Q[INPUT_BUF_SIZE]; char COutStream::Q[OUTPUT_BUF_SIZE]; } // namespace nachia #line 4 "Main.cpp" constexpr const unsigned int MOD = 998244353; using Modint = nachia::StaticModint<MOD>; int main() { using nachia::cin, nachia::cout; int N; cin >> N; std::vector<int> cp = {0}; std::vector<Modint> dp = {1}; auto compressCp = [&](){ size_t p = 0; for(size_t i=1; i<cp.size(); i++){ if(cp[p] == cp[i]){ dp[p] += dp[i]; } else{ p++; cp[p] = cp[i]; dp[p] = dp[i]; } } cp.resize(p+1); dp.resize(p+1); }; for(int i=0; i<N; i++){ int a; cin >> a; cp.push_back(0); dp.push_back(0); for(auto& c : cp) c |= a; compressCp(); for(size_t j=1; j<cp.size(); j++) dp[j] += dp[j-1]; } Modint ans = 0; for(auto& a : dp) ans += a; cout << ans.val() << '\n'; return 0; }