結果

問題 No.1258 コインゲーム
ユーザー MisterMister
提出日時 2020-10-23 10:13:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 159 ms / 2,000 ms
コード長 3,614 bytes
コンパイル時間 912 ms
コンパイル使用メモリ 71,816 KB
最終ジャッジ日時 2025-01-15 12:47:14
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <array>
#include <atcoder/modint>
namespace ac = atcoder;
template <class T, int D>
struct Vector {
using V = std::array<T, D>;
V vec;
// constructor
Vector(T val = 0) { vec.fill(val); }
// getter
T& operator[](int i) { return vec[i]; }
T operator[](int i) const { return vec[i]; }
typename V::iterator begin() { return vec.begin(); }
typename V::iterator end() { return vec.end(); }
// arithmetic
Vector operator+(const Vector& v) const { return Vector(*this) += v; }
Vector operator-(const Vector& v) const { return Vector(*this) -= v; }
T operator*(const Vector& v) const {
T ret(0);
for (int i = 0; i < D; ++i) ret += vec[i] * v[i];
return ret;
}
// compound assignment
Vector& operator+=(const Vector& v) {
for (int i = 0; i < D; ++i) vec[i] += v[i];
return *this;
}
Vector& operator-=(const Vector& v) {
for (int i = 0; i < D; ++i) vec[i] -= v[i];
return *this;
}
};
template <class T, int D>
struct Matrix {
using M = std::array<std::array<T, D>, D>;
M mat;
// constructor
Matrix(T val = 0) {
for (auto& v : mat) v.fill(val);
}
static Matrix id() {
Matrix m;
for (int i = 0; i < D; ++i) m[i][i] = 1;
return m;
}
// getter
std::array<T, D>& operator[](int i) { return mat[i]; }
std::array<T, D> operator[](int i) const { return mat[i]; }
typename M::iterator begin() { return mat.begin(); }
typename M::iterator end() { return mat.end(); }
// arithmetic
Matrix operator+(const Matrix& m) const { return Matrix(*this) += m; }
Matrix operator-(const Matrix& m) const { return Matrix(*this) -= m; }
Matrix operator*(const Matrix& m) const { return Matrix(*this) *= m; }
template <class U>
Matrix pow(U k) {
Matrix ret = id();
Matrix a = *this;
while (k > 0) {
if (k & 1) ret *= a;
a *= a;
k >>= 1;
}
return ret;
}
// compound assignment
Matrix& operator+=(const Matrix& m) {
for (int i = 0; i < D; ++i) {
for (int j = 0; j < D; ++j) {
mat[i][j] += m[i][j];
}
}
return *this;
}
Matrix& operator-=(const Matrix& m) {
for (int i = 0; i < D; ++i) {
for (int j = 0; j < D; ++j) {
mat[i][j] -= m[i][j];
}
}
return *this;
}
Matrix& operator*=(const Matrix& m) {
M nmat;
for (auto& v : nmat) v.fill(0);
for (int i = 0; i < D; ++i) {
for (int j = 0; j < D; ++j) {
for (int k = 0; k < D; ++k) {
nmat[i][j] += mat[i][k] * m[k][j];
}
}
}
mat = nmat;
return *this;
}
// arithmetic with vector
using Vec = Vector<T, D>;
Vec operator*(const Vec& v) {
Vec ret;
for (int i = 0; i < D; ++i) {
for (int j = 0; j < D; ++j) {
ret[i] += mat[i][j] * v[j];
}
}
return ret;
}
};
using mint = ac::modint1000000007;
using Mat = Matrix<mint, 2>;
void solve() {
int n, m, x;
std::cin >> n >> m >> x;
auto mat = Mat::id();
for (int i = 0; i < 2; ++i) mat[i][1 - i] = m;
mat = mat.pow(n);
std::cout << (mat[x][0]).val() << "\n";
}
int main() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int q;
std::cin >> q;
while (q--) solve();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0