#275328 (C++14) No.718 行列のできるフィボナッチ数列道場 (1)

提出ソース

結果

問題	No.718 行列のできるフィボナッチ数列道場 (1)
ユーザー	kjnh10
提出日時	2018-07-28 00:03:46
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	816 ms / 2,000 ms
コード長	7,210 bytes
コンパイル時間	2,338 ms
コンパイル使用メモリ	185,912 KB
実行使用メモリ	4,384 KB
最終ジャッジ日時	2023-09-19 04:09:01
合計ジャッジ時間	9,556 ms
ジャッジサーバーID （参考情報）	judge14 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	801 ms 4,380 KB
testcase_01	AC	182 ms 4,380 KB
testcase_02	AC	525 ms 4,380 KB
testcase_03	AC	174 ms 4,376 KB
testcase_04	AC	816 ms 4,380 KB
testcase_05	AC	548 ms 4,376 KB
testcase_06	AC	274 ms 4,380 KB
testcase_07	AC	111 ms 4,380 KB
testcase_08	AC	792 ms 4,380 KB
testcase_09	AC	417 ms 4,380 KB
testcase_10	AC	3 ms 4,380 KB
testcase_11	AC	3 ms 4,380 KB
testcase_12	AC	3 ms 4,380 KB
testcase_13	AC	3 ms 4,380 KB
testcase_14	AC	6 ms 4,384 KB
testcase_15	AC	9 ms 4,384 KB
testcase_16	AC	9 ms 4,380 KB
testcase_17	AC	9 ms 4,380 KB
testcase_18	AC	9 ms 4,376 KB
testcase_19	AC	12 ms 4,380 KB
testcase_20	AC	1 ms 4,376 KB
testcase_21	AC	335 ms 4,380 KB
testcase_22	AC	2 ms 4,380 KB

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

ソースコード

raw source code

using namespace std;
#include <iostream>
#include <bits/stdc++.h>

#define infile "../test/sample-1.in"
#define int long long
// #define INF 2147483647
#define INF 1000000000000000000LL
#define MOD 1000000007LL
// {{{ define basic macro
// #define rep(i, x) for(int i = 0; i < (int)(x); i++)
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define reps(i,x) for(int i = 1; i <= (int)(x); i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define RFOR(i, m, n) for(int i = m;i >= n;i--)
#define foreach(x,a) for(auto& (x) : (a) )
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(x) (x).begin(),(x).end()
#define sum(v) accumulate(all(v), 0)
#define sz(x) ((int)(x).size())
template<class T> inline void chmax(T &a, const T &b) { if(a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }
// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}
#define fill(x,y) memset(x,y,sizeof(x))
#define pb(a) push_back(a)
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ten(n) ((int)1e##n)

template <class T = int>
T in() {T x; cin>>x; return (x);}

struct Fast {
  Fast(){
    std::cin.tie(0);
    ios::sync_with_stdio(false);
  }
} fast;
// }}}
//{{{ dump macro
#ifdef PCM
  #include "dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif
//}}}
//{{{ others
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<long long> vll;
typedef vector<vll> vvll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<vii> vvii;
typedef tuple<int,int,int> iii;
typedef set<int> si;
typedef complex<double> pnt;
typedef vector<pnt> vpnt;
typedef priority_queue<pii, vii, greater<pii> > spq;  //pop, topで最小値
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};
//}}}


int solve(){
  vvi x;
  x.pb(vi({1, 0, 0}));/*{{{*/
  x.pb(vi({36891058,908460138,964927951}));
  x.pb(vi({708713046,371975563,946533617}));
  x.pb(vi({832459368,967988087,509786860}));
  x.pb(vi({555285113,392460984,207105907}));
  x.pb(vi({355333862,864787550,200000007}));
  x.pb(vi({534952325,4660654,371423623}));
  x.pb(vi({457037277,393241336,407794103}));
  x.pb(vi({445100786,530142919,885945115}));
  x.pb(vi({780396802,662356693,73070046}));
  x.pb(vi({999999973,21,999999734}));
  x.pb(vi({823366807,964730508,978161894}));
  x.pb(vi({715243378,47291577,287143675}));
  x.pb(vi({24131371,897801569,250793022}));
  x.pb(vi({361986899,558994539,758601952}));
  x.pb(vi({79187200,219772980,200012817}));
  x.pb(vi({909494817,173410246,54967674}));
  x.pb(vi({718800694,485645421,496453263}));
  x.pb(vi({999574610,455258545,726782935}));
  x.pb(vi({375999376,777695784,672638455}));
  x.pb(vi({1597,999999020,999397937}));
  x.pb(vi({264869286,749206315,838357449}));
  x.pb(vi({674848433,405320339,779553125}));
  x.pb(vi({33366209,835338478,990409271}));
  x.pb(vi({431330760,334795872,27390880}));
  x.pb(vi({922867773,805882474,228284466}));
  x.pb(vi({718791584,845057847,942232496}));
  x.pb(vi({759330350,781424045,264550114}));
  x.pb(vi({574892880,72705620,123981650}));
  x.pb(vi({547632659,785941725,439990192}));
  x.pb(vi({999924982,46368,671232238}));
  x.pb(vi({727776849,822572946,276715547}));
  x.pb(vi({566880502,902652630,186591601}));
  x.pb(vi({407656820,841290252,582453221}));
  x.pb(vi({365467528,705599596,693070236}));
  x.pb(vi({546027777,903751015,623800565}));
  x.pb(vi({307300980,108871225,452136886}));
  x.pb(vi({592673115,787424730,365644695}));
  x.pb(vi({980460233,127577343,900717152}));
  x.pb(vi({885265840,283043407,385708940}));
  x.pb(vi({3524578,997821698,410141410}));
  x.pb(vi({529619056,589865503,872850958}));
  x.pb(vi({681768169,170006352,28107846}));
  x.pb(vi({806763391,624019965,483840929}));
  x.pb(vi({391695550,502023354,578609710}));
  x.pb(vi({413826897,717820129,499553298}));
  x.pb(vi({838062468,37994620,923868375}));
  x.pb(vi({385033448,209613911,713286550}));
  x.pb(vi({343476498,931159308,758759346}));
  x.pb(vi({844873162,911018251,819634879}));
  x.pb(vi({834419866,102334155,510853745}));
  x.pb(vi({380127701,453748616,105335718}));
  x.pb(vi({390015786,107048889,847424535}));
  x.pb(vi({674464076,829771610,254470054}));
  x.pb(vi({224841755,699302941,298551243}));
  x.pb(vi({4108204,358703167,890320855}));
  x.pb(vi({303763304,105381649,525352914}));
  x.pb(vi({310754962,360721530,857760585}));
  x.pb(vi({876144487,107935489,681148200}));
  x.pb(vi({405695833,899099104,548456798}));
  x.pb(vi({778742000,192473059,44066357}));
  x.pb(vi({604379130,83949699,603077492}));
  x.pb(vi({987490029,798695907,237828250}));
  x.pb(vi({493425268,376714645,131564763}));
  x.pb(vi({40742042,630738657,323979426}));
  x.pb(vi({393087522,423131148,438560380}));
  x.pb(vi({885062356,9067912,530005158}));
  x.pb(vi({9483443,836474305,364311742}));
  x.pb(vi({477732907,995872758,535307981}));
  x.pb(vi({87422827,831324169,624510285}));
  x.pb(vi({564706400,851432142,743595923}));
  x.pb(vi({214053392,600615566,886680257}));
  x.pb(vi({197953180,354243748,39519988}));
  x.pb(vi({134548496,464640208,108960298}));
  x.pb(vi({860282292,655980397,724037382}));
  x.pb(vi({520778395,754133024,12431477}));
  x.pb(vi({98306258,468426494,196023050}));
  x.pb(vi({243523224,324986415,178248829}));
  x.pb(vi({670409052,86045214,743558048}));
  x.pb(vi({485431333,28665233,745732999}));
  x.pb(vi({680057396,790216554,72124658}));
  x.pb(vi({335111523,687118902,300236456}));
  x.pb(vi({708710588,551848063,982785105}));
  x.pb(vi({182795469,785195740,343811684}));
  x.pb(vi({525990521,538182908,626511910}));
  x.pb(vi({130328088,132616976,997709618}));
  x.pb(vi({494543560,974887031,92863609}));
  x.pb(vi({544925113,889164309,30851551}));
  x.pb(vi({13041873,960002226,497292916}));
  x.pb(vi({97304683,821409901,208207434}));
  x.pb(vi({472596219,8390086,435523618}));
  x.pb(vi({35705139,104796271,735173949}));
  x.pb(vi({492649422,708897480,967192012}));
  x.pb(vi({274064524,631160278,683421425}));
  x.pb(vi({418163403,49423109,987738762}));
  x.pb(vi({353801518,12869153,932680483}));
  x.pb(vi({658146590,711883378,753961026}));
  x.pb(vi({144996647,884291363,911124200}));
  x.pb(vi({716622931,793850486,781900333}));
  x.pb(vi({941248608,365069693,768071074}));
  x.pb(vi({107920472,815449418,128493982}));/*}}}*/
  int n;cin>>n;
  int y = n/100000000LL;

  int ppf = x[y][0];
  int pf = x[y][1];
  int s=x[y][2];
  int f;
  rep(i, 1, n%100000000LL + 1){
    f = (ppf%MOD) + (pf%MOD);
    f %= MOD;
    s += (f*f)%MOD;
    s %= MOD;
    ppf = pf;
    pf = f;
  }

  cout << s << endl;

  return 0;
}

signed main() { //{{{
#ifdef INPUT_FROM_FILE
  std::ifstream in(infile);
  std::cin.rdbuf(in.rdbuf());
#endif
  solve();
  return 0;
} //}}}

yukicoder

結果

テストケース

ソースコード