結果

問題 No.891 隣接3項間の漸化式
ユーザー AC2KAC2K
提出日時 2023-03-28 13:32:39
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 8,078 bytes
コンパイル時間 3,156 ms
コンパイル使用メモリ 255,112 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-20 03:43:32
合計ジャッジ時間 4,523 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 1 ms
6,944 KB
testcase_11 AC 1 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 1 ms
6,940 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,944 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 2 ms
6,948 KB
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 2 ms
6,944 KB
testcase_25 AC 2 ms
6,940 KB
testcase_26 AC 1 ms
6,940 KB
testcase_27 AC 2 ms
6,944 KB
testcase_28 AC 2 ms
6,940 KB
testcase_29 AC 2 ms
6,940 KB
testcase_30 AC 2 ms
6,940 KB
testcase_31 AC 2 ms
6,940 KB
testcase_32 AC 1 ms
6,940 KB
testcase_33 AC 2 ms
6,944 KB
testcase_34 AC 2 ms
6,944 KB
testcase_35 AC 1 ms
6,940 KB
testcase_36 AC 2 ms
6,940 KB
testcase_37 AC 2 ms
6,948 KB
testcase_38 AC 1 ms
6,944 KB
testcase_39 AC 1 ms
6,940 KB
testcase_40 AC 2 ms
6,940 KB
testcase_41 AC 1 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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/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:
	static_modint() :v(0) {}
	static_modint(const i64& v_) :v(normalize(v_)) { }

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


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

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

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


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

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

	mint inv() const {
		return pow(mod - 2);
	}

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

	//iostream
	friend ostream& operator<<(ostream& os, const mint& mt) {
		os << mt.val();
		return os;
	}
	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 = unsigned long long;

	u32 v;
	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 {
		return pow(mod - 2);
	}

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

	//iostream
	friend ostream& operator<<(ostream& os, const mint& mt) {
		os << mt.val();
		return os;
	}
	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));
        rep(i, ha) rep(k, wa) rep(j, wb) { 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';
}
0