結果

問題 No.1578 A × B × C
ユーザー EbishuEbishu
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#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(); }
#endif
template<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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0