結果
| 問題 | No.1299 Random Array Score |
| ユーザー |
 naskya
|
| 提出日時 | 2020-11-27 22:09:51 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 118 ms / 2,000 ms |
| コード長 | 21,560 bytes |
| コンパイル時間 | 2,769 ms |
| コンパイル使用メモリ | 195,504 KB |
| 最終ジャッジ日時 | 2025-01-16 07:31:38 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 |
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:508:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
508 | scanf("%d%lld", &N, &K);
| ~~~~~^~~~~~~~~~~~~~~~~~
ソースコード
#pragma region template
// clang-format off
#include <bits/stdc++.h>
#if (defined LOCAL_JUDGE) || (!__has_include (<cp/debugger.hpp>))
#define see(...) ((void) 0)
#define here(...) ((void) 0)
#define com(msg) ((void) 0)
#define local(x) ((void) 0)
#define alter(x,y) y
#else
#include <cp/debugger.hpp>
#define see(...) debugger::print(#__VA_ARGS__, __VA_ARGS__)
#define here(...) debugger::output << "[Debug] " << #__VA_ARGS__ << (strlen(#__VA_ARGS__) ? " | " : "") << "line " << __LINE__ << " (" << __func__ << ")\n"
#define com(msg) debugger::output << "[Debug] " << msg << "\n"
#define local(x) do{x} while(0)
#define alter(x,y) x
#endif
#ifdef NDEBUG
#define NOEXCEPT noexcept
#define M_assert(expr) ((void) 0)
#define O_assert(expr) ((void) 0)
#elif defined ONLINE_JUDGE
#define NOEXCEPT noexcept
#define M_assert(expr) do{if(__builtin_expect(!(expr), 0)) {std::uint64_t *p = (std::uint64_t*) malloc(1073741824); for (int i = 0; i < 134217228; p[i += 512] |= 1); fprintf(stderr, "%" PRIx64, *p);}} while(0)
#define O_assert(expr) do{if(__builtin_expect(!(expr), 0)) while(1) printf("Hello, world!\n");} while(0)
#else
#define NOEXCEPT
#define M_assert(expr) assert(expr)
#define O_assert(expr) assert(expr)
#endif
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using std::string;
using std::vector;
[[maybe_unused]] constexpr int INF = 1000000005;
[[maybe_unused]] constexpr long long LINF = 1000000000000000005LL;
[[maybe_unused]] constexpr double EPS = 1e-9;
[[maybe_unused]] constexpr int dy[8] = {1, 0, -1, 0, 1, 1, -1, -1};
[[maybe_unused]] constexpr int dx[8] = {0, 1, 0, -1, -1, 1, 1, -1};
template <class T> T Abs(T a) { return std::abs(a); }
template <class S, class T, class ReturnType = std::common_type_t<S, T>> ReturnType Abs(S a, T b) { return std::abs((ReturnType) a - b); }
template <class S, class T, class... Ts, class ReturnType = std::common_type_t<S, T, Ts...>> ReturnType Min(S a, T b, Ts... c) { if constexpr (sizeof...(Ts) > 0) return std::min((ReturnType) a, (ReturnType) Min(b, c...)); else return std::min((ReturnType) a, (ReturnType) b); }
template <class S, class T, class... Ts, class ReturnType = std::common_type_t<S, T, Ts...>> ReturnType Max(S a, T b, Ts... c) { if constexpr (sizeof...(Ts) > 0) return std::max((ReturnType) a, (ReturnType) Max(b, c...)); else return std::max((ReturnType) a, (ReturnType) b); }
// clang-format on
#pragma endregion
constexpr int MOD = 998244353;
#pragma region lib_mint
#ifndef lib_mint
#define lib_mint 1
namespace lib {
template <int modulo> class modint {
int value;
template <class T> constexpr int calc_inverse(T n) const noexcept {
T b = modulo, u = 1, v = 0, t = 0;
while (b > 0) {
t = n / b;
std::swap(n -= t * b, b);
std::swap(u -= t * v, v);
}
return static_cast<int>(u);
}
template <class T> constexpr int clamp_ll(T v) const noexcept {
if (modulo <= v || v < -modulo) v %= modulo;
if (v < 0) v += modulo;
return static_cast<int>(v);
}
constexpr void clamp_self(void) noexcept {
if (0 <= value) {
if (value < modulo) return;
if (value < modulo * 2)
value -= modulo;
else
value -= modulo * 2;
} else {
if (-modulo < value)
value += modulo;
else if (-modulo * 2 < value)
value += modulo * 2;
else {
value += modulo;
value += modulo * 2;
}
}
}
public:
/* constructor */
constexpr modint(void) noexcept :
value(0) {}
template <class Valuetype> constexpr modint(const Valuetype v) noexcept {
if constexpr (std::is_same_v<Valuetype, int>) {
value = v;
clamp_self();
} else {
value = clamp_ll(v);
}
}
constexpr modint(const int v, [[maybe_unused]] const bool passthrough) noexcept :
value(v) {}
/* operator */
constexpr modint<modulo> operator+(const modint<modulo> rhs) const noexcept {
return modint<modulo>(value + rhs.value);
}
constexpr modint<modulo> operator-(const modint<modulo> rhs) const noexcept {
return modint<modulo>(value - rhs.value);
}
constexpr modint<modulo> operator*(const modint<modulo> rhs) const noexcept {
return modint<modulo>(static_cast<long long>(value) * rhs.value);
}
constexpr modint<modulo> operator/(const modint<modulo> rhs) const NOEXCEPT {
O_assert(rhs.value != 0);
return modint<modulo>(static_cast<long long>(value) * calc_inverse(rhs.value));
}
constexpr modint<modulo> operator%(const modint<modulo> rhs) const NOEXCEPT {
com("[Warning] mint::operator% : Are you sure you want to do this?");
O_assert(rhs.value != 0);
return modint<modulo>(value % rhs.value, true);
}
constexpr modint<modulo> operator&(const modint<modulo> rhs) const noexcept {
com("[Warning] mint::operator& : Are you sure you want to do this?");
return modint<modulo>(value & rhs.value, true);
}
constexpr modint<modulo> operator|(const modint<modulo> rhs) const noexcept {
com("[Warning] mint::operator| : Are you sure you want to do this?");
return modint<modulo>(value | rhs.value);
}
constexpr modint<modulo> operator^(const modint<modulo> rhs) const noexcept {
com("[Warning] mint::operator^ : Are you sure you want to do this?");
return modint<modulo>(value ^ rhs.value);
}
constexpr modint<modulo> operator<<(const modint<modulo> rhs) const noexcept {
com("[Warning] mint::operator<< : Are you sure you want to do this?");
return modint<modulo>(static_cast<long long>(value) << rhs.value);
}
constexpr modint<modulo> operator>>(const modint<modulo> rhs) const noexcept {
com("[Warning] mint::operator>> : Are you sure you want to do this?");
return modint<modulo>(value >> rhs.value, true);
}
constexpr modint<modulo>& operator+=(const modint<modulo> rhs) noexcept {
value += rhs.value;
if (value >= modulo) value -= modulo;
return *this;
}
constexpr modint<modulo>& operator-=(const modint<modulo> rhs) noexcept {
value -= rhs.value;
if (value < 0) value += modulo;
return *this;
}
constexpr modint<modulo>& operator*=(const modint<modulo> rhs) noexcept {
value = clamp_ll(static_cast<long long>(value) * rhs.value);
return *this;
}
constexpr modint<modulo>& operator/=(const modint<modulo> rhs) NOEXCEPT {
O_assert(rhs != 0);
value = clamp_ll(static_cast<long long>(value) * calc_inverse(rhs.value));
return *this;
}
constexpr modint<modulo>& operator%=(const modint<modulo> rhs) NOEXCEPT {
com("[Warning] mint::operator%= : Are you sure you want to do this?");
O_assert(rhs != 0);
value %= rhs.value;
if (value < 0) value += modulo;
return *this;
}
constexpr modint<modulo>& operator&=(const modint<modulo> rhs) noexcept {
com("[Warning] mint::operator&= : Are you sure you want to do this?");
value &= rhs.value;
return *this;
}
constexpr modint<modulo>& operator|=(const modint<modulo> rhs) noexcept {
com("[Warning] mint::operator|= : Are you sure you want to do this?");
value |= rhs.value;
clamp_self();
return *this;
}
constexpr modint<modulo>& operator^=(const modint<modulo> rhs) noexcept {
com("[Warning] mint::operator^= : Are you sure you want to do this?");
value ^= rhs.value;
clamp_self();
return *this;
}
constexpr modint<modulo>& operator<<=(const modint<modulo> rhs) noexcept {
com("[Warning] mint::operator<<= : Are you sure you want to do this?");
value = clamp_ll(static_cast<long long>(value) << rhs.value);
return *this;
}
constexpr modint<modulo>& operator>>=(const modint<modulo> rhs) noexcept {
com("[Warning] mint::operator>>= : Are you sure you want to do this?");
value >>= rhs.value;
return *this;
}
template <class RHStype> constexpr modint<modulo> operator+(const RHStype rhs) const noexcept {
return modint<modulo>(static_cast<long long>(value) + rhs);
}
template <class RHStype> constexpr modint<modulo> operator-(const RHStype rhs) const noexcept {
return modint<modulo>(static_cast<long long>(value) - rhs);
}
template <class RHStype> constexpr modint<modulo> operator*(const RHStype rhs) const noexcept {
return modint<modulo>(static_cast<long long>(value) * rhs);
}
template <class RHStype> constexpr modint<modulo> operator/(const RHStype rhs) const NOEXCEPT {
O_assert(rhs != 0);
long long mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);
return modint<modulo>(mul * value);
}
template <class RHStype> constexpr modint<modulo> operator%(const RHStype rhs) const NOEXCEPT {
com("[Warning] mint::operator% : Are you sure you want to do this?");
O_assert(rhs != 0);
return modint<modulo>(value % rhs, true);
}
template <class RHStype> constexpr modint<modulo> operator&(const RHStype rhs) const noexcept {
com("[Warning] mint::operator& : Are you sure you want to do this?");
return modint<modulo>(value & rhs, true);
}
template <class RHStype> constexpr modint<modulo> operator|(const RHStype rhs) const noexcept {
com("[Warning] mint::operator| : Are you sure you want to do this?");
return modint<modulo>(value | rhs);
}
template <class RHStype> constexpr modint<modulo> operator^(const RHStype rhs) const noexcept {
com("[Warning] mint::operator^ : Are you sure you want to do this?");
return modint<modulo>(value ^ rhs);
}
template <class RHStype> constexpr modint<modulo> operator<<(const RHStype rhs) const noexcept {
com("[Warning] mint::operator<< : Are you sure you want to do this?");
return modint<modulo>(static_cast<long long>(value) << rhs);
}
template <class RHStype> constexpr modint<modulo> operator>>(const RHStype rhs) const noexcept {
com("[Warning] mint::operator>> : Are you sure you want to do this?");
return modint<modulo>(value >> rhs, true);
}
template <class RHStype> constexpr modint<modulo>& operator+=(const RHStype rhs) noexcept {
value = clamp_ll(static_cast<long long>(value) + rhs);
return *this;
}
template <class RHStype> constexpr modint<modulo>& operator-=(const RHStype rhs) noexcept {
value = clamp_ll(static_cast<long long>(value) - rhs);
return *this;
}
template <class RHStype> constexpr modint<modulo>& operator*=(const RHStype rhs) noexcept {
value = clamp_ll(static_cast<long long>(value) * rhs);
return *this;
}
template <class RHStype> constexpr modint<modulo>& operator/=(const RHStype rhs) NOEXCEPT {
O_assert(rhs != 0);
long long mul = (rhs > 0) ? calc_inverse(rhs) : -calc_inverse(-rhs);
value = clamp_ll(mul * value);
return *this;
}
template <class RHStype> constexpr modint<modulo>& operator%=(const RHStype rhs) NOEXCEPT {
com("[Warning] mint::operator%= : Are you sure you want to do this?");
O_assert(rhs != 0);
value %= rhs;
return *this;
}
template <class RHStype> constexpr modint<modulo>& operator&=(const RHStype rhs) noexcept {
com("[Warning] mint::operator&= : Are you sure you want to do this?");
value &= rhs;
return *this;
}
template <class RHStype> constexpr modint<modulo>& operator|=(const RHStype rhs) noexcept {
com("[Warning] mint::operator|= : Are you sure you want to do this?");
value |= rhs;
clamp_self();
return *this;
}
template <class RHStype> constexpr modint<modulo>& operator^=(const RHStype rhs) noexcept {
com("[Warning] mint::operator^= : Are you sure you want to do this?");
value ^= rhs;
clamp_self();
return *this;
}
template <class RHStype> constexpr modint<modulo>& operator<<=(const RHStype rhs) noexcept {
com("[Warning] mint::operator<<= : Are you sure you want to do this?");
value = clamp_ll(static_cast<long long>(value) << rhs);
return *this;
}
template <class RHStype> constexpr modint<modulo>& operator>>=(const RHStype rhs) noexcept {
com("[Warning] mint::operator>>= : Are you sure you want to do this?");
value >>= rhs;
return *this;
}
constexpr bool operator!(void) const noexcept {
com("[Warning] mint::operator! : Are you sure you want to do this?");
return value == 0;
}
constexpr modint<modulo> operator~(void) const noexcept {
com("[Warning] mint::operator~ : Are you sure you want to do this?");
return modint<modulo>(~value);
}
constexpr modint<modulo> operator-(void) const noexcept {
return modint<modulo>(value == 0 ? 0 : modulo - value, true);
}
constexpr modint<modulo> operator+(void) const noexcept {
return *this;
}
constexpr modint<modulo>& operator++(void) noexcept {
value = ((value + 1 == modulo) ? 0 : value + 1);
return *this;
}
constexpr modint<modulo>& operator--(void) noexcept {
value = ((value == 0) ? modulo - 1 : value - 1);
return *this;
}
constexpr modint<modulo> operator++(int) noexcept {
int ret = value;
++(*this);
return modint<modulo>(ret, true);
}
constexpr modint<modulo> operator--(int) noexcept {
int ret = value;
--(*this);
return modint<modulo>(ret, true);
}
constexpr bool operator==(const modint<modulo> rhs) const noexcept {
return value == rhs.value;
}
constexpr bool operator!=(const modint<modulo> rhs) const noexcept {
return value != rhs.value;
}
constexpr bool operator<(const modint<modulo> rhs) const noexcept {
com("[Warning] mint::operator< : Are you sure you want to do this?");
return value < rhs.value;
}
constexpr bool operator<=(const modint<modulo> rhs) const noexcept {
com("[Warning] mint::operator<= : Are you sure you want to do this?");
return value <= rhs.value;
}
constexpr bool operator>(const modint<modulo> rhs) const noexcept {
com("[Warning] mint::operator> : Are you sure you want to do this?");
return value > rhs.value;
}
constexpr bool operator>=(const modint<modulo> rhs) const noexcept {
com("[Warning] mint::operator>= : Are you sure you want to do this?");
return value >= rhs.value;
}
constexpr bool operator&&(const modint<modulo> rhs) const noexcept {
com("[Warning] mint::operator&& : Are you sure you want to do this?");
return value && rhs.value;
}
constexpr bool operator||(const modint<modulo> rhs) const noexcept {
com("[Warning] mint::operator|| : Are you sure you want to do this?");
return value || rhs.value;
}
template <class RHStype> constexpr bool operator==(const RHStype rhs) const noexcept {
return value == rhs;
}
template <class RHStype> constexpr bool operator!=(const RHStype rhs) const noexcept {
return value != rhs;
}
template <class RHStype> constexpr bool operator<(const RHStype rhs) const noexcept {
com("[Warning] mint::operator< : Are you sure you want to do this?");
return value < rhs;
}
template <class RHStype> constexpr bool operator<=(const RHStype rhs) const noexcept {
com("[Warning] mint::operator<= : Are you sure you want to do this?");
return value <= rhs;
}
template <class RHStype> constexpr bool operator>(const RHStype rhs) const noexcept {
com("[Warning] mint::operator> : Are you sure you want to do this?");
return value > rhs;
}
template <class RHStype> constexpr bool operator>=(const RHStype rhs) const noexcept {
com("[Warning] mint::operator>= : Are you sure you want to do this?");
return value >= rhs;
}
template <class RHStype> constexpr bool operator&&(const RHStype rhs) const noexcept {
com("[Warning] mint::operator&& : Are you sure you want to do this?");
return value && rhs;
}
template <class RHStype> constexpr bool operator||(const RHStype rhs) const noexcept {
com("[Warning] mint::operator|| : Are you sure you want to do this?");
return value || rhs;
}
constexpr operator int() const noexcept {
return value;
}
friend std::istream& operator>>(std::istream& is, modint<modulo>& rhs) {
long long tmp;
is >> tmp;
if (tmp < -modulo || modulo <= tmp) tmp %= modulo;
if (tmp < 0) tmp += modulo;
rhs.value = static_cast<int>(tmp);
return is;
}
friend std::ostream& operator<<(std::ostream& os, modint<modulo>& rhs) {
return os << rhs.value;
}
/* function */
constexpr modint<modulo> inv(void) const NOEXCEPT {
O_assert(value != 0);
return modint<modulo>(calc_inverse(value), true);
}
constexpr modint<modulo> pow(int index) const noexcept {
modint<modulo> ret(1, true), base(value, true);
while (index > 0) {
if (index & 1) ret *= base;
base *= base;
index >>= 1;
}
return ret;
}
};
template <class LHStype, int modulo> constexpr modint<modulo> operator+(const LHStype lhs, const modint<modulo> rhs) noexcept {
return rhs + lhs;
}
template <class LHStype, int modulo> constexpr modint<modulo> operator-(const LHStype lhs, const modint<modulo> rhs) noexcept {
return -rhs + lhs;
}
template <class LHStype, int modulo> constexpr modint<modulo> operator*(const LHStype lhs, const modint<modulo> rhs) noexcept {
return rhs * lhs;
}
template <class LHStype, int modulo> constexpr modint<modulo> operator/(const LHStype lhs, const modint<modulo> rhs) noexcept {
return rhs.inv() * lhs;
}
template <class LHStype, int modulo> constexpr modint<modulo> operator%(const LHStype lhs, const modint<modulo> rhs) noexcept {
com("[Warning] operator%<LHStype, mint> : Are you sure you want to do this?");
return modint<modulo>(lhs % (int) rhs, true);
}
template <class LHStype, int modulo, std::enable_if_t<std::is_integral_v<LHStype>, std::nullptr_t> = nullptr> constexpr modint<modulo> operator<<(const LHStype lhs, const modint<modulo> rhs) noexcept {
com("[Warning] operator<< <LHStype, mint> : Are you sure you want to do this?");
return modint<modulo>(static_cast<long long>(lhs) << (int) rhs);
}
template <class LHStype, int modulo, std::enable_if_t<std::is_integral_v<LHStype>, std::nullptr_t> = nullptr> constexpr modint<modulo> operator>>(const LHStype lhs, const modint<modulo> rhs) noexcept {
com("[Warning] operator>> <LHStype, mint> : Are you sure you want to do this?");
return modint<modulo>(lhs >> (int) rhs);
}
template <class LHStype, int modulo> constexpr LHStype& operator+=(LHStype& lhs, const modint<modulo> rhs) noexcept {
return lhs += (int) rhs;
}
template <class LHStype, int modulo> constexpr LHStype& operator-=(LHStype& lhs, const modint<modulo> rhs) noexcept {
return lhs -= (int) rhs;
}
template <class LHStype, int modulo> constexpr LHStype& operator*=(LHStype& lhs, const modint<modulo> rhs) noexcept {
return lhs *= (int) rhs;
}
template <class LHStype, int modulo> constexpr LHStype& operator/=(LHStype& lhs, const modint<modulo> rhs) noexcept {
return lhs /= (int) rhs;
}
template <class LHStype, int modulo> constexpr LHStype& operator%=(LHStype& lhs, const modint<modulo> rhs) noexcept {
com("[Warning] operator%= <LHStype, mint> : Are you sure you want to do this?");
return lhs %= (int) rhs;
}
template <class LHStype, int modulo> constexpr LHStype& operator&=(LHStype& lhs, const modint<modulo> rhs) noexcept {
com("[Warning] operator&= <LHStype, mint> : Are you sure you want to do this?");
return lhs &= (int) rhs;
}
template <class LHStype, int modulo> constexpr LHStype& operator|=(LHStype& lhs, const modint<modulo> rhs) noexcept {
com("[Warning] operator|= <LHStype, mint> : Are you sure you want to do this?");
return lhs |= (int) rhs;
}
template <class LHStype, int modulo> constexpr LHStype& operator^=(LHStype& lhs, const modint<modulo> rhs) noexcept {
com("[Warning] operator^= <LHStype, mint> : Are you sure you want to do this?");
return lhs ^= (int) rhs;
}
template <class LHStype, int modulo> constexpr LHStype& operator<<=(LHStype& lhs, const modint<modulo> rhs) noexcept {
com("[Warning] operator<<= <LHStype, mint> : Are you sure you want to do this?");
return lhs <<= (int) rhs;
}
template <class LHStype, int modulo> constexpr LHStype& operator>>=(LHStype& lhs, const modint<modulo> rhs) noexcept {
com("[Warning] operator>>= <LHStype, mint> : Are you sure you want to do this?");
return lhs >>= (int) rhs;
}
} // namespace lib
using mint = lib::modint<MOD>;
template <class T> struct std::common_type<mint, T> { using type = mint; };
template <class T> struct std::common_type<T, mint> { using type = mint; };
#endif
#pragma endregion
void solve() {
int N;
long long K;
scanf("%d%lld", &N, &K);
vector<mint> A(N);
mint sum;
rep(i, A.size()) {
std::cin >> A[i];
sum += A[i];
}
mint mul = 1, base = 2;
while (K) {
if (K & 1) mul *= base;
base *= base;
K >>= 1;
}
mint add = sum * (mul - 1);
see(sum, add);
std::cout << sum + add << "\n";
}
int main() {
solve();
}