YukicoderContest276 B問題P2 「Random Array Score」
https://gyazo.com/a42226ad28852b791ef53abb366beb03
問題概要
制約
解法・お気持ち
これ難しい気がする
現在の$ Aについて
$ S = \sum_i A_iとする。
ここで、それぞれが選ばれる確率は$ \frac{1}{N}である。
よって、$ iの要素によって増える期待値は$ A_i \times \frac{1}{N} \times N
である。
( * N は、 A_i の値を次のN個に足すため また1/Nは選ばれる確率)
よって、結局$ iの要素によって増える期待値は$ A_iであり、全体出会わせると$ Sになる。
よって、倍に増えていく。
計算量
$ O(N \log K)
新たな学び
期待値は 確率変数 * 確率
後ろから考える
反省点
コード
code: cpp
template<int_fast64_t Modulas = 1000000007ul>
class ModInt {
using u64 = int_fast64_t;
public:
u64 x;
constexpr ModInt() : x(0) {}
constexpr ModInt(int_fast64_t v) : x((v % Modulas + Modulas) % Modulas) {}
constexpr ModInt operator+(const ModInt rhs) const noexcept {
return ModInt(*this) += rhs;
}
constexpr ModInt operator-(const ModInt rhs) const noexcept {
return ModInt(*this) -= rhs;
}
constexpr ModInt operator*(const ModInt rhs) const noexcept {
return ModInt(*this) *= rhs;
}
constexpr ModInt operator/(const ModInt rhs) const noexcept {
return ModInt(*this) /= rhs;
}
constexpr ModInt operator/(const long long rhs) const noexcept {
return ModInt(*this) /= rhs;
}
constexpr ModInt operator+=(const ModInt rhs) noexcept {
x += rhs.x;
if (x >= Modulas) x -= Modulas;
return *this;
}
constexpr ModInt operator+=(const long long rhs) noexcept {
auto hs = ModInt<Modulas>(rhs);
(*this) += hs;
return *this;
}
constexpr ModInt operator-=(const ModInt rhs) noexcept {
if (x < rhs.x) x += Modulas;
x -= rhs.x;
return *this;
}
constexpr ModInt operator-=(const long long rhs) noexcept {
auto hs = ModInt<Modulas>(rhs);
(*this) -= hs;
return *this;
}
constexpr ModInt operator*=(const ModInt rhs) noexcept {
x = x * rhs.x % Modulas;
return *this;
}
constexpr ModInt operator*=(const long long rhs) noexcept {
auto hs = ModInt<Modulas>(rhs);
(*this) *= hs;
return *this;
}
constexpr ModInt &operator/=(ModInt rhs) noexcept {
u64 exp = Modulas - 2;
while (exp > 0) {
if (exp & 1ul) *this *= rhs;
rhs *= rhs;
exp >>= 1ul;
}
return *this;
}
constexpr ModInt &operator/=(long long rhs) noexcept {
auto hs = ModInt<Modulas>(rhs);
(*this) /= hs;
return *this;
}
constexpr ModInt &operator++() noexcept {
x++;
if (x >= Modulas) x -= Modulas;
return *this;
}
constexpr ModInt &operator--() noexcept {
if (x == 0) x += Modulas;
x--;
return *this;
}
constexpr bool operator<(const ModInt rhs) const noexcept {
return x < rhs.x;
}
constexpr bool operator==(const ModInt rhs) const noexcept {
return this->x == rhs.x;
}
constexpr bool operator!=(const ModInt rhs) const noexcept {
return !(*this == rhs);
}
friend istream &operator>>(istream &in, ModInt &m) {
in >> m.x;
if (m.x < 0) m.x += Modulas;
m.x %= Modulas;
return in;
}
friend ostream &operator<<(ostream &out, const ModInt &p) {
out << p.x;
return out;
}
constexpr ModInt pow(u64 p) const {
ModInt ret(1);
ModInt mul(x);
while (p > 0) {
if (p & 1ul) ret *= mul;
mul *= mul;
p >>= 1ul;
}
return ret;
}
constexpr ModInt operator~() const noexcept {
u64 exp = Modulas - 2;
return pow(exp);
}
constexpr static ModInt arith_sum(ModInt<Modulas> a, ModInt<Modulas> d, ModInt<Modulas> n) noexcept {
return (a * ModInt<Modulas>(2) + (n - 1) * d) * n / ModInt<Modulas>(2);
}
};
constexpr LL mod = 998244353;
int main() {
LL N, K;
cin >> N >> K;
vector<LL> a(N);
cin >> a;
LL S = accumulate(a.begin(), a.end(), 0LL);
auto ans = ModInt<mod>(2).pow(K) * ModInt<mod>(S);
cout << ans << endl;
return 0;
}