結果

問題 No.2394 部分和乗総和
ユーザー zer0-starzer0-star
提出日時 2023-07-31 20:11:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 46 ms / 2,000 ms
コード長 6,784 bytes
コンパイル時間 4,936 ms
コンパイル使用メモリ 304,260 KB
最終ジャッジ日時 2025-02-15 21:11:35
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// #ifndef ONLINE_JUDGE
#if __has_include("all.h")
#include "all.h"
#else
#include <bits/extc++.h>
#include <atcoder/all>
#endif
using ll = long long int;
template <class T>
bool chmin(T &x, const T val) {
if (x > val) {
x = val;
return true;
} else {
return false;
}
}
template <class T>
bool chmax(T &x, const T val) {
if (x < val) {
x = val;
return true;
} else {
return false;
}
}
template <class T, class U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
return is >> p.first >> p.second;
}
template <class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
for (T &x : v) is >> x;
return is;
}
template <class... T>
std::istream &operator>>(std::istream &is, std::tuple<T...> &tpl) {
[&is, &tpl ]<size_t... I>(std::index_sequence<I...>) {
(is >> ... >> std::get<I>(tpl));
}
(std::make_index_sequence<std::tuple_size_v<std::tuple<T...>>>{});
return is;
}
template <class mint, atcoder::internal::is_static_modint_t<mint> * = nullptr>
std::ostream &operator<<(std::ostream &os, const mint &v) {
return os << v.val();
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
for (int i = 0; i < v.size(); i++)
os << v[i] << (i == v.size() - 1 ? "" : " ");
return os;
}
struct Initialization {
Initialization() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
}
} initialization;
constexpr std::pair<int, int> dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
template <typename T>
using infs = std::numeric_limits<T>;
template <typename T>
class factorials {
size_t n;
std::vector<T> fact, inv_fact;
void extend(size_t m) {
if (m <= n) return;
fact.resize(m + 1);
inv_fact.resize(m + 1);
for (size_t i = n + 1; i <= m; i++) fact[i] = fact[i - 1] * i;
inv_fact[m] = fact[m].inv();
for (size_t i = m - 1; i >= n + 1; i--) inv_fact[i] = inv_fact[i + 1] * i;
n = m;
}
public:
factorials() : n(0), fact(1, 1), inv_fact(1, 1) {}
factorials(size_t n) : n(n), fact(n + 1), inv_fact(n + 1) {
fact[0] = 1;
for (size_t i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
inv_fact[n] = fact[n].inv();
for (size_t i = n; i >= 1; i--) inv_fact[i - 1] = inv_fact[i] * i;
}
T inv(int k) {
extend(k);
return inv_fact[k];
}
T operator()(int k) {
extend(k);
return fact[k];
}
T perm(int n, int k) {
if (n < k) return 0;
if (k < 0) return 0;
extend(n);
return fact[n] * inv_fact[n - k];
}
T choose(int n, int k) {
if (n < k) return 0;
if (k < 0) return 0;
extend(n);
return fact[n] * inv_fact[n - k] * inv_fact[k];
}
};
template <typename T>
class fps {
std::vector<T> v;
public:
using value_type = T;
using reference = T &;
using const_reference = const T &;
using iterator = typename std::vector<T>::iterator;
using const_iterator = typename std::vector<T>::const_iterator;
size_t size() const { return v.size(); }
const std::vector<T> &data() const { return v; }
explicit fps(int n) : v(n) {}
fps(const std::vector<T> &v) : v(v) {}
fps(std::vector<T> &&v) : v(v) {}
template <class InputIterator>
fps(InputIterator first, InputIterator last) : v(first, last) {}
void resize(int n) { v.resize(n); }
T &operator[](int i) { return v[i]; }
iterator begin() { return v.begin(); }
iterator end() { return v.end(); }
fps diff() {
std::vector<T> res(v.size() - 1);
for (int i = 0; i < res.size(); i++) res[i] = v[i + 1] * (i + 1);
return fps(res);
}
fps integral() {
std::vector<T> res(v.size() + 1);
for (int i = 0; i < v.size(); i++) res[i + 1] = v[i] / (i + 1);
return fps(res);
}
fps inv(int deg = -1) {
assert(v[0] != 0);
if (deg == -1) deg = size();
std::vector<T> res(deg);
res[0] = v[0].inv();
for (int d = 1; d < deg; d <<= 1) {
std::vector<T> f(2 * d), g(2 * d);
std::copy(v.begin(), v.begin() + std::min(2 * d, (int)v.size()),
std::back_inserter(f));
std::copy(res.begin(), res.begin() + d, std::back_inserter(g));
atcoder::internal::butterfly(f);
atcoder::internal::butterfly(g);
for (int i = 0; i < 2 * d; i++) f[i] *= g[i];
atcoder::internal::butterfly_inv(f);
for (int i = 0; i < d; i++) f[i] = 0;
atcoder::internal::butterfly(f);
for (int i = 0; i < 2 * d; i++) f[i] *= g[i];
atcoder::internal::butterfly_inv(f);
for (int i = d; i < std::min(2 * d, deg); i++) res[i] = -f[i];
}
res.resize(deg);
return res;
}
fps operator-() {
fps res(v.size());
for (int i = 0; i < v.size(); i++) res[i] = -v[i];
return res;
}
fps &operator+=(const fps &rhs) {
if (v.size() < rhs.v.size()) v.resize(rhs.v.size());
for (int i = 0; i < rhs.v.size(); i++) v[i] += rhs.v[i];
return *this;
}
fps &operator-=(const fps &rhs) {
if (v.size() < rhs.v.size()) v.resize(rhs.v.size());
for (int i = 0; i < rhs.v.size(); i++) v[i] -= rhs.v[i];
return *this;
}
fps &operator*=(const fps &rhs) {
return *this = atcoder::convolution(v, rhs.v);
}
fps &operator+=(const T &rhs) {
if (v.size() == 0) v.resize(1);
v[0] += rhs;
return *this;
}
fps &operator-=(const T &rhs) {
if (v.size() == 0) v.resize(1);
v[0] -= rhs;
return *this;
}
fps &operator*=(const T &rhs) {
for (int i = 0; i < v.size(); i++) v[i] *= rhs;
return *this;
}
fps &operator/=(const T &rhs) {
T rhs_inv = rhs.inv();
for (int i = 0; i < v.size(); i++) v[i] *= rhs_inv;
return *this;
}
friend fps operator+(const fps &lhs, const fps &rhs) {
return fps(lhs) += rhs;
}
friend fps operator-(const fps &lhs, const fps &rhs) {
return fps(lhs) -= rhs;
}
friend fps operator*(const fps &lhs, const fps &rhs) {
return fps(lhs) *= rhs;
}
friend fps operator+(const fps &lhs, const T &rhs) { return fps(lhs) += rhs; }
friend fps operator-(const fps &lhs, const T &rhs) { return fps(lhs) -= rhs; }
friend fps operator*(const fps &lhs, const T &rhs) { return fps(lhs) *= rhs; }
friend fps operator/(const fps &lhs, const T &rhs) { return fps(lhs) /= rhs; }
friend fps operator+(const T &lhs, const fps &rhs) { return fps(rhs) += lhs; }
friend fps operator-(const T &lhs, const fps &rhs) {
return -(fps(rhs) -= lhs);
}
friend fps operator*(const T &lhs, const fps &rhs) { return fps(rhs) *= lhs; }
};
using mint = atcoder::modint;
int main() {
ll n, m, b;
std::cin >> n >> m >> b;
std::vector<ll> a(n);
std::cin >> a;
mint::set_mod(b);
mint ans = 1;
for (int i = 0; i < n; i++) {
ans *= 1 + mint(m).pow(a[i]);
}
std::cout << ans.val() << std::endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0