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

• 問題: No.891 隣接3項間の漸化式
• ユーザー: だいこん
• 提出日時: 2026-08-02 16:22:41
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 3,788 bytes
• コンパイル時間: 5,208 ms
• コンパイル使用メモリ: 397,696 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-08-02 16:22:49
• 合計ジャッジ時間: 7,392 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 39

ソースコード

#include <cstdio>
#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#include <map>
using namespace atcoder;
#endif

using namespace std;
using namespace atcoder;

//マクロ
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using Graph = vector<vector<ll>>;

#define rep(i, x, limit) for (int i = (int)x; i < (int)limit; i++)
#define REP(i, x, limit) for (int i = (int)x; i <= (int)limit; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define el '\n'
#define spa " "
#define Yes cout << "Yes" << el
#define No cout << "No" << el
#define YES cout << "YES" << el
#define NO cout << "NO" << el
#define eps (1e-10)
#define Equals(a,b) (fabs((a) - (b)) < eps )


// --- modint を出力するためのオーバーロード ---
#if __has_include(<atcoder/all>)
template <int m>
ostream& operator<<(ostream& os, const static_modint<m>& v) {
    return os << v.val();
}
template <int id>
ostream& operator<<(ostream& os, const dynamic_modint<id>& v) {
    return os << v.val();
}
#endif

// --- 容器の中身を出力するための汎用オーバーロード ---
template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { return os << "(" << p.first << ", " << p.second << ")"; }

// begin() と end() を持つコンテナ (vector, set, map, deque 等) を全て自動判定して出力
// ※ string は一文字ずつ分割されないように除外
template<class T, class = decltype(begin(declval<T>())), class = enable_if_t<!is_same_v<T, string>>>
ostream& operator<<(ostream& os, const T& c) {
    os << "{";
    for (auto it = begin(c); it != end(c); ++it) {
        if (it != begin(c)) os << ", ";
        os << *it;
    }
    return os << "}";
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", _debug(__VA_ARGS__)
#else
#define debug(...) void(0)
#endif

void _debug() { cerr << endl; }
template <typename Head, typename... Tail>
void _debug(Head H, Tail... T) {
    cerr << H << (sizeof...(T) ? ", " : "");
    _debug(T...);
}

const double pi = 3.141592653589793238;
const int inf = 1073741823;
const ll infl = 1LL << 60;
const string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string abc = "abcdefghijklmnopqrstuvwxyz";
//マクロ終わり

struct xyi {
    ll x, y, i;
    
    // ↓ デバッグ出力用の魔法の1行を追加するだけ ↓
    friend ostream& operator<<(ostream& os, const xyi& s) {
        return os << "(" << s.x << ", " << s.y << ", " << s.i << ")";
    }
};



//基本1-indexとして扱う
void solve() {
    ll a,b,n;
    cin >> a >> b >> n;
    vector<vector<modint1000000007>> d(2,vector<modint1000000007>(2));
    d={{a,b},{1,0}};
    vector<vector<vector<modint1000000007>>> dd(100,vector<vector<modint1000000007>>(2,vector<modint1000000007>(2)));
    dd[0] = d;
    rep(i,1,100){
        //dd[i]を求める
        rep(j,0,2)rep(k,0,2)rep(l,0,2){
            dd[i][j][k] += dd[i-1][j][l]*dd[i-1][l][k];
        }
    }
    vector<vector<modint1000000007>> ad(2,vector<modint1000000007>(2)),bd(2,vector<modint1000000007>(2));
    debug(dd);
    ad={{0,0},{0,0}};
    bd={{1,0},{0,1}};
    ll bb = 0;
    while(1){
        if((n>>bb) == 0)break;
        if((n>>bb)%2 == 1){
            ad={{0,0},{0,0}};
            debug(bb,ad,bd,dd[bb]);
            rep(j,0,2)rep(k,0,2)rep(l,0,2){
                ad[j][k] += bd[j][l]*dd[bb][l][k];
            }
            bd = ad;
        }
        debug(ad);
        bb++;
    }
    debug(ad);
    cout << ad[1][0].val() << el;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // int t; cin >> t; while(t--) // 複数テストケースの場合はこれを使う
    solve();
    return 0;
}