結果
問題 | No.1578 A × B × C |
ユーザー | Ebishu |
提出日時 | 2021-07-02 21:35:25 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 12,627 bytes |
コンパイル時間 | 3,253 ms |
コンパイル使用メモリ | 203,388 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-29 11:08:38 |
合計ジャッジ時間 | 3,921 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 1 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 1 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 1 ms
5,376 KB |
ソースコード
#include <algorithm>#include <array>#include <bitset>#include <cassert>#include <climits>#include <cmath>#include <complex>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <map>#include <numeric>#include <optional>#include <queue>#include <random>#include <set>#include <stack>#include <string>#include <tuple>#include <unordered_map>#include <unordered_set>#include <vector>using namespace std;using lint = long long;using P = pair<lint, lint>;#define rep(i, n) for (lint i = 0; i < (lint)(n); ++i)#define rep1(i, n) for (lint i = 1; i < (lint)(n); ++i)#define repn(i, a, b) for(lint i = (a); i < (lint)(b); ++i)#define rep_inv(i, n) for (lint i = (n); i >= 0; --i)#define all(vec) (vec).begin(), (vec).end()constexpr lint Mod = /**/ 1000'000'007LL /*/ 998244353LL /**/;constexpr lint Inf = 1'000'000'000'000'000'010LL;constexpr int IntInf = 1000'000'010;constexpr double Pi = 3.141592653589793238;constexpr double InvPi = 0.318309886183790671;const int di[4] = { 0,1,0,-1 }, dj[4] = { 1,0,-1,0 };#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;using mint = static_modint<Mod>;inline istream& operator>>(istream & is, mint & rhs) {long long tmp;is >> tmp;rhs = tmp;return is;}inline ostream& operator<<(ostream & os, const mint & rhs) { return os << rhs.val(); }#endiftemplate<typename T> using prique = priority_queue<T>;template<typename T> using prique_inv = priority_queue<T, vector<T>, greater<T>>;template<typename T> inline istream& operator>>(istream& is, vector<T>& v) { for (auto&& e : v) is >> e; return is; }template<typename T> inline istream& operator>>(istream& is, complex<T>& c) {double real, imag;is >> real >> imag;c.real(real);c.imag(imag);return is;}template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) {size_t i = 0, n = v.size();for (const auto& e : v) {os << e;if (++i < n) os << " ";}return os;}template<typename T, typename U> inline bool chmin(T& a, const U b) { return a > b ? a = b, true : false; }template<typename T, typename U> inline bool chmax(T& a, const U b) { return a < b ? a = b, true : false; }template<typename T, typename U> inline istream& operator>>(istream& is, pair<T, U>& rhs) { return is >> rhs.first >> rhs.second; }template<typename T, typename U> inline ostream& operator<<(ostream& os, const pair<T, U>& rhs) { return os << "{" << rhs.first << ", " << rhs.second<< "}"; }template<typename T> T gcd(const vector<T>& vec) {T res = vec.front();for (T e : vec) {res = gcd(res, e);if (res == 1) return 1;}return res;}template<typename T> T gcd(initializer_list<T> init) {auto first = init.begin(), last = init.end();T res = *(first++);for (auto itr = first; itr != last; ++itr) {res = gcd(res, *itr);if (res == 1) return 1;}return res;}template<typename T> T lcm(const vector<T>& vec) {T res = vec.front();for (T e : vec) res = lcm(res, e);return res;}template<typename T> T lcm(initializer_list<T> init) {auto first = init.begin(), last = init.end();T res = *(first++);for (auto itr = first; itr != last; ++itr) {res = lcm(res, *itr);}return res;}template<typename T> T pow(T x, lint n) {T res = 1;while (n > 0) {if (n & 1) res *= x;x *= x;n >>= 1;}return res;}void out() {}template<typename T> void out(T x) { cout << x << endl; }template<typename T, typename... Args> void out(T x, Args... xs) {cout << x << ", ";out(xs...);}bool is_prime(lint x) {for (lint i = 2; i * i <= x; ++i) {if (x % i == 0) return false;}return 1 < x;}vector<lint> fact, fact_inv;void fact_init(lint n, lint m = Mod) {fact.resize(n + 1);fact_inv.resize(n + 1);vector<lint> inv(n + 1);inv[1] = 1;fact[0] = fact[1] = 1;fact_inv[0] = 1;for (lint i = 2; i <= n; ++i) {fact[i] = i * fact[i - 1] % m;inv[i] = m - m / i * inv[m % i] % m;}for (lint i = 1; i <= n; ++i) {fact_inv[i] = fact_inv[i - 1] * inv[i] % m;}}lint modinv(lint a, lint m = Mod) {lint b = m, u = 1, v = 0;while (b != 0) {lint t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}lint modpow(lint x, lint n, lint m = Mod) {lint res = 1;while (n > 0) {if (n & 1) res = res * x % m;x = x * x % m;n >>= 1;}return res;}lint intpow(lint x, lint n) {lint res = 1;while (n > 0) {if (n & 1) res *= x;x *= x;n >>= 1;}return res;}lint comb(lint n, lint r) {if (n < 0 || r < 0 || n < r) return 0;if (r == 0 || r == n) return 1;return fact[n] * fact_inv[n - r] % Mod * fact_inv[r] % Mod;}lint perm(lint n, lint r) {if (n < 0 || r < 0 || n < r) return 0;return fact[n] * fact_inv[n - r] % Mod;}template<typename T = int>vector<T> as_vector(const string& str) {const size_t n = str.size();vector<T> res(n);T* p_res = res.data();const char* p_str = str.data();for (size_t i = 0; i < n; ++i) {*p_res++ = T(*p_str++ - '0');}return res;}template<typename T>vector<T> compressed(vector<T> v) {sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());return v;}class Factring {private:const lint max_n;vector<lint> sieve;public:explicit Factring(lint max_n) noexcept: max_n{ max_n }, sieve{ max_n }{iota(sieve.begin(), sieve.end(), 0);for (lint i = 2; i * i < max_n; ++i) {if (sieve[i] < i) continue;for (lint j = i * i; j < max_n; j += i) {if (sieve[j] == j) sieve[j] = i;}}}unordered_map<lint, lint> calc(lint x) const noexcept {unordered_map<lint, lint> res;while (x > 1) {++res[sieve[x]];x /= sieve[x];}return res;}};struct UnionFind {const int n;vector<int> par, rank, siz, es;explicit UnionFind(int _n) noexcept: n(_n), par(n), rank(n), siz(n, 1), es(n){iota(par.begin(), par.end(), 0);}int root(int x) noexcept {if (par[x] == x) return x;return par[x] = root(par[x]);}bool same(int x, int y) noexcept { return root(x) == root(y); }void unite(int x, int y) noexcept {x = root(x); y = root(y);if (x == y) ++es[x];else if (rank[x] < rank[y]) {par[x] = y;siz[y] += siz[x];es[y] += es[x] + 1;}else {par[y] = x;if (rank[x] == rank[y]) ++rank[x];siz[x] += siz[y];es[x] += es[y] + 1;}}int count(int x) noexcept { return siz[root(x)]; }vector<vector<int>> groups() noexcept {vector<int> roots(n), group_size(n);for (int i = 0; i < n; ++i) {roots[i] = root(i);++group_size[roots[i]];}vector<vector<int>> res(n);for (int i = 0; i < n; ++i) {res.reserve(group_size[i]);}for (int i = 0; i < n; ++i) {res[roots[i]].push_back(i);}res.erase(remove_if(res.begin(), res.end(),[](const vector<int>& v) { return v.empty(); }),res.end());return res;}};template<typename T>class CumulativeSum {private:const int n;vector<T> dat;public:CumulativeSum() = default;explicit CumulativeSum(const int n) : n(n), dat(n + 1) {}CumulativeSum(const vector<T>& vec): n(vec.size()), dat(n + 1){for (int i = 0; i < n; ++i) dat[i + 1] = vec[i];}void add(const int i, const T& x) { dat[i + 1] += x; }void build() {for (int i = 0; i < n; ++i) {dat[i + 1] += dat[i];}}// [l, r)T sum(const int l, const int r) const { return dat[r] - dat[l]; }// [0, a)T sum(const int a) const { return dat[a]; }};template<typename T>class CumulativeSum2D {private:vector<vector<T>> dat;public:CumulativeSum2D() = default;explicit CumulativeSum2D(size_t n) : dat(n + 1, vector<T>(n + 1)) {}CumulativeSum2D(size_t h, size_t w) : dat(h + 1, vector<T>(w + 1)) {}CumulativeSum2D(const vector<vector<T>>& vec) noexcept {const size_t h = vec.size(), w = vec.front().size();dat.resize(h + 1, vector<T>(w + 1));for (size_t i = 0; i < h; ++i) {for (size_t j = 0; j < w; ++j) {dat[i + 1][j + 1] = dat[i][j + 1] + dat[i + 1][j] - dat[i][j] + vec[i][j];}}}void add(int h, int w, int v) noexcept {dat[h + 1][w + 1] += v;}void build() {const size_t h = dat.size(), w = dat.front().size();for (size_t i = 0; i < h; ++i) {for (size_t j = 0; j < w; ++j) {dat[i + 1][j + 1] = dat[i][j + 1] + dat[i + 1][j] - dat[i][j];}}}// [0, h) × [0, w)T sum(int h, int w) const noexcept {return sum(0, 0, h, w);}// [h1, h2) × [w1, w2)T sum(int h1, int w1, int h2, int w2) const noexcept {return dat[h2][w2] - dat[h1][w2] - dat[h2][w1] + dat[h1][w1];}};template<typename T>class BinaryIndexedTree {private:const int size;vector<T> dat;public:explicit BinaryIndexedTree(const int size) noexcept: size(size), dat(size + 1) {}explicit BinaryIndexedTree(const vector<T>& vec) noexcept: size(vec.size()), dat(size + 1){for (int i = 0; i < size; ++i) dat[i + 1] = vec[i];for (int i = 0; i <= size; ++i) {const int j = i + (i & -i);if (j <= size) dat[j] += dat[i];}}void add(const int a, const T w) noexcept {for (int x = a + 1; x <= size; x += (x & -x)) dat[x] += w;}void set(const int a, const T w) noexcept {add(a, w - dat[a]);}// [0, a)T sum(const int a) const noexcept {T res = 0;for (int x = a; x > 0; x -= x & -x) res += dat[x];return res;}// [a, b)T sum(const int a, const int b) const noexcept { return sum(b) - sum(a); }const T& operator[](const size_t x) const noexcept { return dat[x + 1]; }};template<typename T>lint inversion_number(const vector<T> vec) {vector<T> v = vec;sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());const int n = vec.size();lint res = 0;fenwick_tree<int> b(n);for (int i = 0; i < n; ++i) {const int j = lower_bound(v.begin(), v.end(), vec[i]) - v.begin();res += i - b.sum(0, j);b.add(j, 1);}return res;}template<typename T, typename U>T nearest_value(const vector<T>& v, const U& value) {auto itr = lower_bound(v.begin(), v.end(), value);if (itr == v.begin()) return *itr;if (itr == v.end()) return *prev(itr);return min(*itr - value, value - *prev(itr)) + value;}template<typename T>struct matrix {size_t row, column;vector<vector<T>> mat;matrix() = default;explicit matrix(size_t size): row(size), column(size), mat(size, vector<T>(size)){}matrix(size_t row, size_t column): row(row), column(column), mat(row, vector<T>(column)){}matrix(size_t row, size_t column, const T& val): row(row), column(column), mat(row, vector<T>(column, val)){}matrix(const vector<T>& vec): row(vec.size()), column(1){mat.resize(row, vector<T>(1));for (size_t i = 0; i < row; ++i) {mat[i][0] = vec[i];}}matrix(const vector<vector<T>>& mat): row(mat.size()), column(mat.front().size()), mat(mat){}matrix& operator=(const matrix& rhs) {row = rhs.row, column = rhs.column, mat = rhs.mat;return (*this);}matrix operator*(const matrix& rhs) const { return matrix(*this) *= rhs; }matrix& operator*=(const matrix& rhs) {matrix res(row, rhs.column);for (size_t k = 0; k < column; ++k) {for (size_t i = 0; i < row; ++i) {for (size_t j = 0; j < rhs.column; ++j) {res[i][j] += mat[i][k] * rhs[k][j];}}}return (*this) = res;}const vector<T>& operator[](const size_t index) const { return mat[index]; }vector<T>& operator[](const size_t index) { return mat[index]; }static matrix identity(size_t n) {matrix res(n);for (size_t i = 0; i < n; ++i) {res[i][i] = 1;}return res;}matrix pow(long long x) const {assert(row == column);matrix res = identity(row), base = (*this);while (x > 0) {if (x & 1) res *= base;base *= base;x >>= 1;}return res;}friend ostream& operator<<(ostream& os, const matrix& rhs) {for (size_t i = 0; i < rhs.row; ++i) {for (size_t j = 0; j < rhs.column; ++j) {os << rhs[i][j];if (j + 1 < rhs.column) os << " ";else os << "\n";}}return os;}};int main() {using mint2 = static_modint<Mod - 1>;mint a, b, c;lint k;cin >> a >> b >> c >> k;matrix<mint2> mat(3, 3);mat[0][0] = 0; mat[0][1] = 1; mat[0][2] = 1;mat[1][0] = 1; mat[1][1] = 0; mat[1][2] = 1;mat[2][0] = 1; mat[2][1] = 1; mat[2][2] = 0;mat = mat.pow(k);cout << a.pow((mat[0][0] + mat[1][0] + mat[2][0]).val()) * b.pow((mat[0][1] + mat[1][1] + mat[2][1]).val()) * c.pow((mat[0][2] + mat[1][2] +mat[2][2]).val()) << endl;}