結果
問題 | No.1258 コインゲーム |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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; }