#854197 (C++23) No.891 隣接3項間の漸化式

提出ソース

結果

問題	No.891 隣接3項間の漸化式
ユーザー	AC2K
提出日時	2023-03-31 15:45:59
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	9,318 bytes
コンパイル時間	3,054 ms
コンパイル使用メモリ	253,852 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-22 20:13:58
合計ジャッジ時間	4,736 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 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	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	RE	-
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,944 KB
testcase_17	RE	-
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	RE	-
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	RE	-
testcase_24	AC	2 ms 6,940 KB
testcase_25	AC	2 ms 6,940 KB
testcase_26	AC	2 ms 6,944 KB
testcase_27	AC	2 ms 6,944 KB
testcase_28	AC	2 ms 6,940 KB
testcase_29	AC	2 ms 6,944 KB
testcase_30	AC	2 ms 6,944 KB
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	2 ms 6,944 KB
testcase_33	AC	2 ms 6,940 KB
testcase_34	AC	2 ms 6,944 KB
testcase_35	AC	2 ms 6,940 KB
testcase_36	AC	2 ms 6,944 KB
testcase_37	AC	2 ms 6,940 KB
testcase_38	AC	2 ms 6,940 KB
testcase_39	AC	2 ms 6,940 KB
testcase_40	AC	2 ms 6,940 KB
testcase_41	AC	2 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 1 "test/yuki/No.891.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/891"

#line 2 "template.hpp"
#include<bits/stdc++.h>
using namespace std;
#define rep(i, N)  for(int i=0;i<(N);i++)
#define all(x) (x).begin(),(x).end()
#define popcount(x) __builtin_popcount(x)
using i128=__int128_t;
using ll = long long;
using ld = long double;
using graph = vector<vector<int>>;
using P = pair<int, int>;
constexpr int inf = 1e9;
constexpr ll infl = 1e18;
constexpr ld eps = 1e-6;
const long double pi = acos(-1);
constexpr uint64_t MOD = 1e9 + 7;
constexpr uint64_t MOD2 = 998244353;
constexpr int dx[] = { 1,0,-1,0 };
constexpr int dy[] = { 0,1,0,-1 };
template<class T>static constexpr inline void chmax(T&x,T y){if(x<y)x=y;}
template<class T>static constexpr inline void chmin(T&x,T y){if(x>y)x=y;}
#line 1 "math/gcd.hpp"
template<typename T>
static constexpr inline T _gcd(T a,T b){
    T s = a, t = b;
    while (s % t != 0) {
        T u = s % t;

        s = t;
        t = u;
    }
    return t;
}
template<typename T>
static constexpr inline T ext_gcd(T a, T b, T &x, T &y) {
    x = 1, y = 0;
    T nx = 0, ny = 1;
    while(b) {
        T q = a / b;
        tie(a, b) = make_pair(b, a % b);
        tie(x, nx) = make_pair(nx, x - nx*q);
        tie(y, ny) = make_pair(ny, y - ny*q);
    }
    return a;
}
/// @return ax+by=gcd(a,b)なるx,yを格納する,返り値にgcd(a,b)

/// @brief gcd(ユークリッドの互除法など)
#line 3 "math/static_modint.hpp"
template<__uint64_t mod>
class static_modint {
private:
	using mint = static_modint<mod>;
	using i64 = long long;
	using u64 = unsigned long long;
	using u128 = __uint128_t;
	using i128 = __int128_t;

	u64 v;
	u64 normalize(i64 v_) const {
		v_ %= mod;
		if (v_ < 0) {
			v_ += mod;
		}
		return v_;
	}
public:
	constexpr static_modint() :v(0) {}
	constexpr static_modint(const i64& v_) :v(normalize(v_)) { }

	//operator
	constexpr u64 val() const {
		return v;
	}
	constexpr mint& operator+=(const mint& rhs) {
		v += rhs.val();
		if (v >= mod) {
			v -= mod;
		}
		return (*this);
	}
	constexpr mint& operator-=(const mint& rhs) {
		v += mod - rhs.val();
		if (v >= mod) {
			v -= mod;
		}
		return (*this);
	}
	constexpr mint& operator*=(const mint& rhs) {
		v = (u128)v * rhs.val() % mod;
		return (*this);
	}


	constexpr mint operator+(const mint& r) const {
		return mint(*this) += r;
	}
	constexpr mint operator-(const mint& r) const {
		return mint(*this) -= r;
	}
	constexpr mint operator*(const mint& r) const {
		return mint(*this) *= r;
	}

	constexpr mint& operator+=(const i64& rhs) {
		(*this) += mint(rhs);
		return (*this);
	}
	constexpr mint& operator-=(const i64& rhs) {
		(*this) -= mint(rhs);
		return (*this);
	}
	constexpr mint& operator*=(const i64& rhs) {
		(*this) *= mint(rhs);
		return (*this);
	}
	constexpr friend mint operator+(const i64& l, const mint& r) {
		return mint(l) += r;
	}
	constexpr friend mint operator-(const i64& l, const mint& r) {
		return mint(l) -= r;
	}
	constexpr friend mint operator*(const i64& l, const mint& r) {
		return mint(l) *= r;
	}

	constexpr mint operator+(const i64& r) {
		return mint(*this) += r;
	}
	constexpr mint operator-(const i64& r) {
		return mint(*this) -= r;
	}
	constexpr mint operator*(const i64& r) {
		return mint(*this) *= r;
	}


	constexpr mint& operator=(const i64& r) {
		return (*this) = mint(r);
	}

	constexpr bool operator==(const mint& r) const {
		return (*this).val() == r.val();
	}
	constexpr mint pow(u128 e) const {
		mint ans(1), base(*this);
		while (e) {
			if (e & 1) {
				ans *= base;
			}
			base *= base;
			e >>= 1;
		}
		return ans;
	}

	constexpr mint inv() const {
		ll x, y;
        auto d = ext_gcd((ll)mod, (ll)v, x, y);
        assert(d == 1);
        return mint(y);
	}

	constexpr mint& operator/=(const mint& r) {
		return (*this) *= r.inv();
	}
	constexpr friend mint operator/(const mint& l, const i64& r) {
		return mint(l) /= mint(r);
	}

	//iostream
	constexpr friend ostream& operator<<(ostream& os, const mint& mt) {
		os << mt.val();
		return os;
	}
	constexpr friend istream& operator>>(istream& is, mint& mt) {
		i64 v_;
		is >> v_;
		mt = v_;
		return is;
	}
};
template<__uint32_t mod>
class static_modint32 {
private:
	using mint = static_modint32<mod>;
	using i32 = __int32_t;
	using u32 = __uint32_t;
	using i64 = __int64_t;
	using u64 = __uint64_t;

	u32 v;
	inline u32 normalize(i64 v_) const {
		v_ %= mod;
		if (v_ < 0) {
			v_ += mod;
		}
		return v_;
	}
public:
	constexpr static_modint32() :v(0) {}
	constexpr static_modint32(const i64& v_) :v(normalize(v_)) { }

	//operator
	constexpr u64 val() const {
		return (u64)v;
	}
	constexpr mint& operator+=(const mint& rhs) {
		v += rhs.val();
		if (v >= mod) {
			v -= mod;
		}
		return (*this);
	}
	constexpr mint& operator-=(const mint& rhs) {
		v += mod - rhs.val();
		if (v >= mod) {
			v -= mod;
		}
		return (*this);
	}
	constexpr mint& operator*=(const mint& rhs) {
		v = (u64)v * rhs.val() % mod;
		return (*this);
	}

	constexpr mint operator+(const mint& r) const {
		return mint(*this) += r;
	}
	constexpr mint operator-(const mint& r) const {
		return mint(*this) -= r;
	}
	constexpr mint operator*(const mint& r) const {
		return mint(*this) *= r;
	}

	constexpr mint& operator+=(const i64& rhs) {
		(*this) += mint(rhs);
		return (*this);
	}
	constexpr mint& operator-=(const i64& rhs) {
		(*this) -= mint(rhs);
		return (*this);
	}
	constexpr mint& operator*=(const i64& rhs) {
		(*this) *= mint(rhs);
		return (*this);
	}
	constexpr friend mint operator+(const i64& l, const mint& r) {
		return mint(l) += r;
	}
	constexpr friend mint operator-(const i64& l, const mint& r) {
		return mint(l) -= r;
	}
	constexpr friend mint operator*(const i64& l, const mint& r) {
		return mint(l) *= r;
	}

	constexpr mint operator+(const i64& r) {
		return mint(*this) += r;
	}
	constexpr mint operator-(const i64& r) {
		return mint(*this) -= r;
	}
	constexpr mint operator*(const i64& r) {
		return mint(*this) *= r;
	}


	constexpr mint& operator=(const i64& r) {
		return (*this) = mint(r);
	}

	constexpr bool operator==(const mint& r) const {
		return (*this).val() == r.val();
	}
	constexpr mint pow(u64 e) const {
		mint ans(1), base(*this);
		while (e) {
			if (e & 1) {
				ans *= base;
			}
			base *= base;
			e >>= 1;
		}
		return ans;
	}

	constexpr mint inv() const {
        ll x, y;
        auto d = ext_gcd((ll)mod, (ll)v, x, y);
        assert(d == 1);
        return mint(y);
    }

	constexpr mint& operator/=(const mint& r) {
		return (*this) *= r.inv();
	}
    constexpr mint operator/(const mint& r) { return mint(*this) *= r.inv(); }
    constexpr friend mint operator/(const mint& l, const i64& r) {
		return mint(l) /= mint(r);
	}

	//iostream
	constexpr friend ostream& operator<<(ostream& os, const mint& mt) {
		os << mt.val();
		return os;
	}
	constexpr friend istream& operator>>(istream& is, mint& mt) {
		i64 v_;
		is >> v_;
		mt = v_;
		return is;
	}

};
///@brief static modint(静的modint)
///@docs docs/math/static_modint.md
#line 1 "math/matrix.hpp"
template<typename T>
class Matrix {
    vector<vector<T>> dat;
    int h = 0, w = 0;

  public:
    Matrix(const vector<vector<T>>& dat)
        : dat(dat), h(dat.size()), w(dat.front().size()) {}

    Matrix(int h_, int w_, const T& v = T())
        : dat(h_, vector<T>(w_, v)){}
        
    using mat = Matrix<T>;
    //access
    vector<T>& operator[](int i) { return dat[i]; }

    //operator
    mat& operator+=(const mat& r) {
        assert(r.h == this->h);
        assert(r.w == this->w);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                dat[i][j] += r.dat[i][j];
            }
        }
        return (*this);
    }
    mat& operator-=(const mat&r){
        assert(r.h == this->h);
        assert(r.w == this->w);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                dat[i][j] -= r.dat[i][j];
            }
        }
        return (*this);
    }
    
    mat& operator*=(const mat& r) {
        int ha = dat.size(), wa = dat.front().size();
        int hb = r.dat.size(), wb = r.dat.front().size();
        assert(wa == hb);

        vector<vector<T>> res(ha, vector<T>(wb));
        for (int i = 0; i < ha; i++) {
            for (int k = 0; k < wa; k++){
                for (int j = 0; j < wb; j++) {
                    res[i][j] += dat[i][k] * r.dat[k][j];
                }
            }
        }

        swap(res, dat);
        return (*this);
    }

    mat operator+(const mat& r) { return mat(*this) += r; }
    mat operator-(const mat& r) { return mat(*this) -= r; }
    mat operator*(const mat& r) { return mat(*this) *= r; }

    mat pow(__int64_t e) const {
        assert(e > 0);
        int n = dat.size();
        mat res(n, n, 0);
        mat pr(*this);
        for (int i = 0; i < n; i++) res[i][i] = 1;

        while (e) {
            if (e & 1) res *= pr;
            pr *= pr;
            
            e >>= 1;
        }
        
        return res;
    }
};
/// @brief maxtirx(行列)
/// @docs docs/math/matrix.md
#line 6 "test/yuki/No.891.test.cpp"
using mint = static_modint32<MOD>;
int main() {
    int a, b, n;
    cin >> a >> b >> n;
    Matrix<mint> A({{a, b}, {1, 0}});
    A = A.pow(n);
    cout << A[1][0] << '\n';
}