結果
問題 | No.2394 部分和乗総和 |
ユーザー |
|
提出日時 | 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 |
ソースコード
// #ifndef ONLINE_JUDGE#if __has_include("all.h")#include "all.h"#else#include <bits/extc++.h>#include <atcoder/all>#endifusing 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;}