結果
| 問題 | No.718 行列のできるフィボナッチ数列道場 (1) |
| ユーザー |
 kjnh10
|
| 提出日時 | 2018-07-28 00:03:46 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 708 ms / 2,000 ms |
| コード長 | 7,210 bytes |
| コンパイル時間 | 1,757 ms |
| コンパイル使用メモリ | 188,404 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-07-05 16:43:55 |
| 合計ジャッジ時間 | 7,541 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 20 |
ソースコード
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//}}}//{{{ otherstypedef 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_FILEstd::ifstream in(infile);std::cin.rdbuf(in.rdbuf());#endifsolve();return 0;} //}}}