結果
| 問題 | No.3662 yuu Hates Sigma Problem |
| コンテスト | |
| ユーザー |
 kuromath
|
| 提出日時 | 2026-08-30 14:26:51 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0) |
| 結果 |
AC
|
| 実行時間 | 16 ms / 2,000 ms |
| + 986µs | |
| コード長 | 13,857 bytes |
| 記録 | |
| コンパイル時間 | 4,469 ms |
| コンパイル使用メモリ | 380,600 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2026-08-30 14:27:00 |
| 合計ジャッジ時間 | 6,715 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| subtask1. | 20 % | AC * 19 |
| subtask2. | 30 % | AC * 13 |
| subtask3. | 50 % | AC * 49 |
| 合計 | 2.5 * 100% = 250 点 |
ソースコード
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
// using mint = modint1000000007;
#endif
//#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using pq_g = priority_queue<T, vector<T>, greater<T>>;
#define overload3(a, b, c, d, ...) d
#define overload4(a, b, c, d, e, ...) e
#define rep1(n) for (ll i = 0; i < (n); i++)
#define rep2(i, n) for (ll i = 0; i < (n); i++)
#define rep3(i, a, b) for (ll i = (a); i < (b); i++)
#define rep4(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for (ll i = (n) - 1; i >= 0; i--)
#define rrep2(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define rrep3(i, a, b) for (ll i = (b) - 1; i >= (a); i--)
#define rrep4(i, a, b, c) for (ll i = (a) + ((b) - (a) - 1) / (c) * (c); i >= (a); i -= (c))
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define all1(v) (v).begin(), (v).end()
#define all2(v, n) (v).begin(), (v).begin() + (n)
#define all3(v, a, b) (v).begin() + (a), (v).begin() + (b)
#define all(...) overload3(__VA_ARGS__, all3, all2, all1)(__VA_ARGS__)
#define rall(v) (v).rbegin(), (v).rend()
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end())
#define NP next_permutation
#define endl '\n'
#define INT(...) int __VA_ARGS__; read(__VA_ARGS__);
#define LL(...) long long __VA_ARGS__; read(__VA_ARGS__);
#define ULL(...) unsigned long long __VA_ARGS__; read(__VA_ARGS__);
#define STR(...) string __VA_ARGS__; read(__VA_ARGS__);
#define CHAR(...) char __VA_ARGS__; read(__VA_ARGS__);
#define LD(...) long double __VA_ARGS__; read(__VA_ARGS__);
#define VEC(type, name, size) vector<type> name(size); read(name);
#define VV(type, name, h, w) vector<vector<type>> name(h, vector<type>(w)); read(name);
#ifdef LOCAL
#define debug(...) debug_impl(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) ((void)0)
#endif
inline void Yes(bool a = true) { cout << (a ? "Yes" : "No") << endl; }
inline void No(bool a = true) { cout << (a ? "No" : "Yes") << endl; }
inline void YES(bool a = true) { cout << (a ? "YES" : "NO") << endl; }
inline void NO(bool a = true) { cout << (a ? "NO" : "YES") << endl; }
inline void Takahashi(bool a = true) { cout << (a ? "Takahashi" : "Aoki") << endl; }
inline void Alice(bool a = true) { cout << (a ? "Alice" : "Bob") << endl; }
inline void Possible(bool a = true) { cout << (a ? "Possible" : "Impossible") << endl; }
constexpr int INF = 1001001001;
constexpr ll LINF = 4004004004004004004LL;
constexpr ld pi = 3.14159265358979323846;
constexpr ld eps = 1e-9;
constexpr int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
constexpr int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };
ll modPow(ll a, ll n, ll mod = LINF) { ll ret = 1; ll x = a % mod; while (n) { if (n & 1) ret = ret * x % mod; x = x * x % mod; n >>= 1; } return ret; }
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int popcount(int x) { return __builtin_popcount(x); }
ll popcount(ll x) { return __builtin_popcountll(x); }
ll isqrt(ll x) { ll n = sqrtl(x); while ((n + 1) * (n + 1) <= x) n++; while (n * n > x) n--; return n; }
template<typename T> T floor(T a, T b) { return a / b - (a % b && (a ^ b) < 0); }
template<typename T> T ceil(T a, T b) { return floor(a + b - 1, b); }
template<typename T> T bmod(T a, T b) { return a - b * floor(a, b); }
template<typename T> pair<T, T> divmod(T a, T b) { return { floor(a, b), a - b * floor(a, b) }; }
template<typename T> auto MIN(const vector<T> &a) { return *min_element(all(a)); }
template<typename T> auto MAX(const vector<T> &a) { return *max_element(all(a)); }
template<typename T> auto SUM(const vector<T> &a) { return accumulate(all(a), T(0)); }
template<typename T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
template<typename T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
void cincout() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
namespace fastio {
class Scanner {
static constexpr int BUF_SIZE = 1 << 25;
char* buf;
int pos = 0, len = 0;
FILE* file;
inline void load() {
int rest = len - pos;
if (rest < 0) rest = 0;
std::memmove(buf, buf + pos, rest);
len = rest + static_cast<int>(std::fread(buf + rest, 1, BUF_SIZE - rest, file));
pos = 0;
buf[len] = '\0';
}
inline void skip_space() {
while (buf[pos] == ' ' || buf[pos] == '\n' || buf[pos] == '\r' || buf[pos] == '\t') {
pos++;
if (pos >= len) load();
}
}
public:
explicit Scanner(FILE* f = stdin) : file(f) {
buf = new char[BUF_SIZE + 1];
load();
}
~Scanner() { delete[] buf; }
Scanner(const Scanner&) = delete;
Scanner& operator=(const Scanner&) = delete;
inline char get_char() {
if (pos >= len) load();
return buf[pos++];
}
template <typename T, typename std::enable_if<std::is_integral<T>::value, int>::type = 0>
inline T read() {
if (pos + 32 >= len) load();
skip_space();
bool neg = false;
if (buf[pos] == '-') { neg = true; pos++; }
T x = 0;
while (buf[pos] >= '0' && buf[pos] <= '9') {
x = x * 10 + static_cast<T>(buf[pos] - '0');
pos++;
if (pos >= len) load();
}
return neg ? static_cast<T>(-x) : x;
}
inline double read_double() {
if (pos + 64 >= len) load();
skip_space();
bool neg = false;
if (buf[pos] == '-') { neg = true; pos++; }
double x = 0;
while (buf[pos] >= '0' && buf[pos] <= '9') {
x = x * 10 + (buf[pos] - '0');
pos++;
if (pos >= len) load();
}
if (buf[pos] == '.') {
pos++;
double f = 1;
while (buf[pos] >= '0' && buf[pos] <= '9') {
f *= 0.1;
x += (buf[pos] - '0') * f;
pos++;
if (pos >= len) load();
}
}
return neg ? -x : x;
}
inline std::string read_string() {
skip_space();
std::string s;
while (buf[pos] > ' ') {
s += buf[pos++];
if (pos >= len) load();
}
return s;
}
inline std::string read_line() {
std::string s;
while (true) {
char c = buf[pos];
if (c == '\n' || c == '\0') { pos++; break; }
s += c;
pos++;
if (pos >= len) load();
}
return s;
}
Scanner& operator>>(short& x) { x = read<short>(); return *this; }
Scanner& operator>>(int& x) { x = read<int>(); return *this; }
Scanner& operator>>(long& x) { x = read<long>(); return *this; }
Scanner& operator>>(long long& x) { x = read<long long>(); return *this; }
Scanner& operator>>(unsigned short& x) { x = read<unsigned short>(); return *this; }
Scanner& operator>>(unsigned& x) { x = read<unsigned>(); return *this; }
Scanner& operator>>(unsigned long& x) { x = read<unsigned long>(); return *this; }
Scanner& operator>>(unsigned long long& x) { x = read<unsigned long long>(); return *this; }
Scanner& operator>>(double& x) { x = read_double(); return *this; }
Scanner& operator>>(std::string& s) { s = read_string(); return *this; }
Scanner& operator>>(char& c) {
skip_space();
c = buf[pos++];
if (pos >= len) load();
return *this;
}
};
class Printer {
static constexpr int BUF_SIZE = 1 << 25;
char* buf;
int idx = 0;
FILE* file;
static const char* digit_table() {
static const char table[201] =
"00010203040506070809"
"10111213141516171819"
"20212223242526272829"
"30313233343536373839"
"40414243444546474849"
"50515253545556575859"
"60616263646566676869"
"70717273747576777879"
"80818283848586878889"
"90919293949596979899";
return table;
}
public:
explicit Printer(FILE* f = stdout) : file(f) { buf = new char[BUF_SIZE]; }
~Printer() { flush(); delete[] buf; }
Printer(const Printer&) = delete;
Printer& operator=(const Printer&) = delete;
inline void flush() {
if (idx > 0) {
std::fwrite(buf, 1, idx, file);
idx = 0;
}
}
inline void write_char(char c) {
if (idx >= BUF_SIZE) flush();
buf[idx++] = c;
}
inline void write_raw(const char* s, int n) {
if (idx + n >= BUF_SIZE) flush();
std::memcpy(buf + idx, s, n);
idx += n;
}
template <typename T, typename std::enable_if<std::is_integral<T>::value, int>::type = 0>
inline void write_int(T x) {
if (idx + 32 >= BUF_SIZE) flush();
const char* table = digit_table();
if (x == 0) { buf[idx++] = '0'; return; }
using U = typename std::make_unsigned<T>::type;
U ux;
bool neg = false;
if (std::is_signed<T>::value && x < 0) {
neg = true;
ux = static_cast<U>(0) - static_cast<U>(x);
} else {
ux = static_cast<U>(x);
}
if (neg) buf[idx++] = '-';
char tmp[24];
int tlen = 0;
while (ux >= 100) {
unsigned r = static_cast<unsigned>(ux % 100) * 2;
ux /= 100;
tmp[tlen++] = table[r + 1];
tmp[tlen++] = table[r];
}
if (ux < 10) {
tmp[tlen++] = static_cast<char>('0' + ux);
} else {
unsigned r = static_cast<unsigned>(ux) * 2;
tmp[tlen++] = table[r + 1];
tmp[tlen++] = table[r];
}
while (tlen > 0) buf[idx++] = tmp[--tlen];
}
inline void write_double(double x, int precision = 15) {
if (x < 0) { write_char('-'); x = -x; }
long long ip = static_cast<long long>(x);
write_int(ip);
write_char('.');
double frac = x - static_cast<double>(ip);
for (int i = 0; i < precision; i++) {
frac *= 10;
int d = static_cast<int>(frac);
write_char(static_cast<char>('0' + d));
frac -= d;
}
}
inline void write_str(const std::string& s) { write_raw(s.data(), static_cast<int>(s.size())); }
using OstreamManip = std::ostream& (*)(std::ostream&);
Printer& operator<<(OstreamManip) {
write_char('\n');
flush();
return *this;
}
Printer& operator<<(short x) { write_int(x); return *this; }
Printer& operator<<(int x) { write_int(x); return *this; }
Printer& operator<<(long x) { write_int(x); return *this; }
Printer& operator<<(long long x) { write_int(x); return *this; }
Printer& operator<<(unsigned short x) { write_int(x); return *this; }
Printer& operator<<(unsigned x) { write_int(x); return *this; }
Printer& operator<<(unsigned long x) { write_int(x); return *this; }
Printer& operator<<(unsigned long long x) { write_int(x); return *this; }
Printer& operator<<(double x) { write_double(x); return *this; }
Printer& operator<<(char c) { write_char(c); return *this; }
Printer& operator<<(const std::string& s) { write_str(s); return *this; }
Printer& operator<<(const char* s) { write_raw(s, static_cast<int>(std::strlen(s))); return *this; }
};
inline Scanner& getline(Scanner& in, std::string& s) {
s = in.read_line();
return in;
}
inline Scanner& scanner_instance() {
static Scanner s;
return s;
}
inline Printer& printer_instance() {
static Printer p;
return p;
}
template <typename T>
inline void read(T& x) {
scanner_instance() >> x;
}
template <typename T, typename... Rest>
inline void read(T& x, Rest&... rest) {
read(x);
read(rest...);
}
template <typename T>
inline void write(const T& x) {
printer_instance() << x;
}
template <typename T, typename... Rest>
inline void write(const T& x, const Rest&... rest) {
write(x);
write(rest...);
}
inline void print() {
printer_instance() << '\n';
}
template <typename T>
inline void print(const T& x) {
printer_instance() << x << '\n';
}
template <typename T, typename... Rest>
inline void print(const T& x, const Rest&... rest) {
printer_instance() << x << ' ';
print(rest...);
}
inline void flush() {
printer_instance().flush();
}
} // namespace fastio
using fastio::read;
using fastio::write;
using fastio::print;
void solve() {
ll N;
read(N);
vector<ll> A(N);
for (auto &x : A) read(x);
mint ans = 0;
mint sum = SUM(A);
for (int bit = 0; bit < 20; bit++) {
ans += sum * N * (1LL << bit);
for (int k = 0; k < 2; k++) {
mint s = 0, c = 0;
for (int i = 0; i < N; i++) if (((i >> bit) & 1) == k) s += A[i], c++;
ans -= s * c * (1LL << bit);
}
}
print(ans.val());
}
int main() {
cincout();
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}