結果

問題 No.891 隣接3項間の漸化式
コンテスト
ユーザー mtsd
提出日時 2019-09-20 21:27:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,113 bytes
コンパイル時間 1,035 ms
コンパイル使用メモリ 111,428 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-14 16:19:17
合計ジャッジ時間 2,237 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  constexpr bool operator==(const modint rhs) noexcept{
  return (*this).value()==rhs.value();
  }
  inline constexpr bool operator!=(const modint rhs) noexcept{
  return !(*this==rhs);
  }
};


int main(){
    int aa,bb,n;
    cin >> aa >> bb >> n;
    modint<mod> p[2][2]={};
    p[0][0] = aa;
    p[0][1] = bb;
    p[1][0] = 1;
    p[1][1] = 0;
    modint<mod> res[2][2]={};
    res[0][0] = 1;
    res[1][1] = 1;
    while(n){
        if(n & 1){
            modint<mod> res2[2][2]={};
    
            rep(i,2){
                rep(j,2){
                    rep(k,2){
                        res2[i][j] += res[i][k]*p[k][j];
                    }
                }
            }
            rep(i,2){
                rep(j,2){
                    res[i][j] = res2[i][j];
                }
            }
        }
        modint<mod> res2[2][2]={};
    
        rep(i,2){
            rep(j,2){
                rep(k,2){
                    res2[i][j] += p[i][k]*p[k][j];
                }
            }
        }
        rep(i,2){
            rep(j,2){
                p[i][j] = res2[i][j];
            }
        }
        n >>= 1;
    }
    modint<mod> ans=res[1][0];
    cout << ans.value() << endl;
    return 0;
}
0