結果

問題 No.1258 コインゲーム
ユーザー kuhaku
提出日時 2020-10-28 13:23:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 960 ms / 2,000 ms
コード長 7,610 bytes
コンパイル時間 2,186 ms
コンパイル使用メモリ 205,648 KB
最終ジャッジ日時 2025-01-15 16:08:18
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
template <class T>
using Vec2 = vector<vector<T>>;
#define REP(i, m, n) for(ll i = (m); i < (n); ++i)
#define REPN(i, m, n) for(ll i = (m); i <= (n); ++i)
#define REPR(i, m, n) for(ll i = (m)-1; i >= (n); --i)
#define REPNR(i, m, n) for(ll i = (m); i >= (n); --i)
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <class T1, class T2>
bool chmax(T1 &a, const T2 b){if(a < b){a = b; return true;} return false;}
template <class T1, class T2>
bool chmin(T1 &a, const T2 b){if(a > b){a = b; return true;} return false;}
ll pow2(const int n){return (1LL << n);}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for (const T &i : v) os << i << ' ';
    return os;
}
void co() { cout << '\n'; }
template <class Head, class... Tail>
void co(Head&& head, Tail&&... tail) {
    cout << head << ' ';
    co(forward<Tail>(tail)...);
}
void ce() { cerr << '\n'; }
template <class Head, class... Tail>
void ce(Head&& head, Tail&&... tail) {
    cerr << head << ' ';
    ce(forward<Tail>(tail)...);
}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const int n){cout << fixed << setprecision(n);}
constexpr int INF = 1000000001;
constexpr ll LINF = 1000000000000000001;
constexpr ll MOD = 1000000007;
constexpr ll MOD_N = 998244353;
constexpr ld EPS = 1e-11;
const double PI = acos(-1);

template <int mod>
struct ModInt {
    int64_t x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &rhs) {
        if((x += rhs.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator-=(const ModInt &rhs) {
        if((x += mod - rhs.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &rhs) {
        x = (int) (1LL * x * rhs.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &rhs) {
        *this *= rhs.inverse();
        return *this;
    }

    ModInt &operator++() {
        if((++x) >= mod) x -= mod;
        return *this;
    }

    ModInt operator++(int) {
        ModInt tmp(*this);
        operator++();
        return tmp;
    }

    ModInt &operator--() {
        if((x += mod - 1) >= mod) x -= mod;
        return *this;
    }

    ModInt operator--(int) {
        ModInt tmp(*this);
        operator--();
        return tmp;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt &rhs) const { return ModInt(*this) += rhs; }

    ModInt operator-(const ModInt &rhs) const { return ModInt(*this) -= rhs; }

    ModInt operator*(const ModInt &rhs) const { return ModInt(*this) *= rhs; }

    ModInt operator/(const ModInt &rhs) const { return ModInt(*this) /= rhs; }

    bool operator==(const ModInt &rhs) const { return x == rhs.x; }

    bool operator!=(const ModInt &rhs) const { return x != rhs.x; }

    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while (b > 0) {
            t = a / b;
            swap(a -= t * b, b);
            swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const {
        ModInt res(1), mul(x);
        while (n > 0) {
            if(n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }

    friend ostream &operator<<(ostream &os, const ModInt &rhs) {
        return os << rhs.x;
    }

    friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t;
        is >> t;
        a = ModInt< mod >(t);
        return (is);
    }

    int to_int() const { return x; }

    static int get_mod() { return mod; }
};
using Mint = ModInt<MOD>;

template <class T>
struct Matrix {
    vector<vector<T>> v;

    Matrix(int64_t x) {
        v.resize(x);
        for (int64_t i = 0; i < x; ++i) v[i].resize(x);
    }

    Matrix(int64_t x, int64_t y) {
        v.resize(x);
        for (int64_t i = 0; i < x; ++i) v[i].resize(y);
    }

    Matrix(vector<vector<T>> _v) : v(_v) {}

    const vector<T> &operator[](const int64_t i) const {
        assert(i >= 0 && i < v.size());
        return v[i];
    }
    vector<T> &operator[](const int64_t i) {
        assert(i >= 0 && i < v.size());
        return v[i];
    }

    Matrix &operator+=(const Matrix &rhs) {
        assert(v.size() == rhs.v.size());
        assert(v[0].size() == rhs.v[0].size());
        for (int64_t i = 0; i < v.size(); ++i) {
            for (int64_t j = 0; j < v[0].size(); ++j) v[i][j] += rhs.v[i][j];
        }
        return *this;
    }

    Matrix &operator-=(const Matrix &rhs) {
        assert(v.size() == rhs.v.size());
        assert(v[0].size() == rhs.v[0].size());
        for (int64_t i = 0; i < v.size(); ++i) {
            for (int64_t j = 0; j < v[0].size(); ++j) v[i][j] -= rhs.v[i][j];
        }
        return *this;
    }

    Matrix &operator*=(const Matrix &rhs) {
        assert(v[0].size() == rhs.v.size());
        int64_t x = v.size(), y = rhs.v[0].size(), z = rhs.v.size();
        vector<vector<T>> tmp(x, vector<T>(y));
        for (int64_t i = 0; i < x; ++i) {
            for (int64_t j = 0; j < y; ++j) {
                for (int64_t k = 0; k < z; ++k) tmp[i][j] += v[i][k] * rhs.v[k][j];
            }
        }
        swap(v, tmp);
        return *this;
    }

    Matrix operator-() const {
        vector<vector<T>> tmp = v;
        for (auto& i : tmp)
            for (auto& j : i) j *= T(-1);
        return Matrix(tmp);
    }

    Matrix operator+(const Matrix &rhs) const { return Matrix(*this) += rhs; }
    Matrix operator-(const Matrix &rhs) const { return Matrix(*this) -= rhs; }
    Matrix operator*(const Matrix &rhs) const { return Matrix(*this) *= rhs; }

    Matrix pow(int64_t n) const {
        Matrix res(v), mul(v);
        res.unit_matrix();
        while (n > 0) {
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }

    void unit_matrix() {
        assert(v.size() == v[0].size());
        int64_t n = v.size();
        for (int64_t i = 0; i < n; ++i) {
            v[i].assign(n, T(0));
            v[i][i] = T(1);
        }
    }

    Matrix transposed() const {
        int64_t x = v[0].size(), y = v.size();
        vector<vector<T>> res(x, vector<T>(y));
        for (int64_t i = 0; i < x; ++i) {
            for (int64_t j = 0; j < y; ++j) {
                res[i][j] = v[j][i];
            }
        }
        return Matrix(res);
    }

    void debug_print() const {
        for(auto i : v) {
            cerr << "[";
            for (auto j : i) cerr << j << ", ";
            cerr << "]" << endl;
        }
    }
};

void solve() {
    ll n, m, x;
    cin >> n >> m >> x;

    Vec2<Mint> a = {{1, m}, {m, 1}};
    Matrix<Mint> v(a);
    v = v.pow(n);

    co(v[x][0]);
}

int main(void) {
    ll t;
    cin >> t;
    while (t--) solve();

    return 0;
}
0