結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
ユーザー kmjpkmjp
提出日時 2018-07-27 23:26:24
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 896 ms / 2,000 ms
コード長 11,034 bytes
コンパイル時間 1,339 ms
コンパイル使用メモリ 159,136 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 05:16:13
合計ジャッジ時間 8,285 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 660 ms
5,248 KB
testcase_01 AC 388 ms
5,376 KB
testcase_02 AC 60 ms
5,376 KB
testcase_03 AC 374 ms
5,376 KB
testcase_04 AC 688 ms
5,376 KB
testcase_05 AC 113 ms
5,376 KB
testcase_06 AC 592 ms
5,376 KB
testcase_07 AC 236 ms
5,376 KB
testcase_08 AC 633 ms
5,376 KB
testcase_09 AC 896 ms
5,376 KB
testcase_10 AC 5 ms
5,376 KB
testcase_11 AC 4 ms
5,376 KB
testcase_12 AC 5 ms
5,376 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 10 ms
5,376 KB
testcase_15 AC 17 ms
5,376 KB
testcase_16 AC 19 ms
5,376 KB
testcase_17 AC 17 ms
5,376 KB
testcase_18 AC 19 ms
5,376 KB
testcase_19 AC 24 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 720 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

ll memo[][4]={
	{1,1,0,1},
{50000000LL,364822946,980450965,952454297},
{100000000LL,908460138,36891058,964927951},
{150000000LL,646371660,711518700,947284727},
{200000000LL,371975563,708713046,946533617},
{250000000LL,431043837,778512760,989939305},
{300000000LL,967988087,832459368,509786860},
{350000000LL,417590676,85825486,927352261},
{400000000LL,392460984,555285113,207105907},
{450000000LL,541353446,450662765,553493376},
{500000000LL,864787550,355333862,200000007},
{550000000LL,869935040,903026782,743511666},
{600000000LL,4660654,534952325,371423623},
{650000000LL,418078,114446478,343507214},
{700000000LL,393241336,457037277,407794103},
{750000000LL,4258201,823155482,747701232},
{800000000LL,530142919,445100786,885945115},
{850000000LL,918528888,257923320,835147394},
{900000000LL,662356693,780396802,73070046},
{950000000LL,993450205,599405538,341817344},
{1000000000LL,21,999999973,999999734},
{1050000000LL,846771862,325949238,502497646},
{1100000000LL,964730508,823366807,978161894},
{1150000000LL,539061078,382169137,307876327},
{1200000000LL,47291577,715243378,287143675},
{1250000000LL,745198009,582486863,268103036},
{1300000000LL,897801569,24131371,250793022},
{1350000000LL,373656446,851337637,220720494},
{1400000000LL,558994539,361986899,758601952},
{1450000000LL,426323253,45888384,781091568},
{1500000000LL,219772980,79187200,200012817},
{1550000000LL,654406853,565725343,39099133},
{1600000000LL,173410246,909494817,54967674},
{1650000000LL,397941010,117599414,586305515},
{1700000000LL,485645421,718800694,496453263},
{1750000000LL,230908390,102136029,51456160},
{1800000000LL,455258545,999574610,726782935},
{1850000000LL,475514225,519713698,190989458},
{1900000000LL,777695784,375999376,672638455},
{1950000000LL,672663640,482666013,346879212},
{2000000000LL,999999020,1597,999397937},
{2050000000LL,836899827,699934968,59843110},
{2100000000LL,749206315,264869286,838357449},
{2150000000LL,17757856,326531994,535764657},
{2200000000LL,405320339,674848433,779553125},
{2250000000LL,544649992,844604882,713457458},
{2300000000LL,835338478,33366209,990409271},
{2350000000LL,20556488,901305862,202775036},
{2400000000LL,334795872,431330760,27390880},
{2450000000LL,421453810,392583208,315585580},
{2500000000LL,805882474,922867773,228284466},
{2550000000LL,372943093,507882293,548274711},
{2600000000LL,845057847,718791584,942232496},
{2650000000LL,296354585,358381106,632755781},
{2700000000LL,781424045,759330350,264550114},
{2750000000LL,143047546,376451197,816043545},
{2800000000LL,72705620,574892880,123981650},
{2850000000LL,732302705,315533049,678583913},
{2900000000LL,785941725,547632659,439990192},
{2950000000LL,391358946,715292019,220598626},
{3000000000LL,46368,999924982,671232238},
{3050000000LL,818936556,777107504,571245648},
{3100000000LL,822572946,727776849,276715547},
{3150000000LL,626319704,270827257,124713839},
{3200000000LL,902652630,566880502,186591601},
{3250000000LL,656252556,721083970,332496193},
{3300000000LL,841290252,407656820,582453221},
{3350000000LL,660188632,787287157,303781270},
{3400000000LL,705599596,365467528,693070236},
{3450000000LL,765347824,502700973,716279068},
{3500000000LL,903751015,546027777,623800565},
{3550000000LL,817267909,563807061,3180015},
{3600000000LL,108871225,307300980,452136886},
{3650000000LL,673393600,38488723,905693828},
{3700000000LL,787424730,592673115,365644695},
{3750000000LL,45856997,204657838,956635496},
{3800000000LL,127577343,980460233,900717152},
{3850000000LL,106258885,650233111,443696495},
{3900000000LL,283043407,885265840,385708940},
{3950000000LL,933466038,898609339,514285409},
{4000000000LL,997821698,3524578,410141410},
{4050000000LL,673082321,776012610,679293647},
{4100000000LL,589865503,529619056,872850958},
{4150000000LL,545216266,944587025,707676539},
{4200000000LL,170006352,681768169,28107846},
{4250000000LL,611480100,264448773,105635803},
{4300000000LL,624019965,806763391,483840929},
{4350000000LL,950578032,96198025,242483605},
{4400000000LL,502023354,391695550,578609710},
{4450000000LL,607198721,980471236,512306877},
{4500000000LL,717820129,413826897,499553298},
{4550000000LL,215465457,993186036,470018793},
{4600000000LL,37994620,838062468,923868375},
{4650000000LL,54146439,832648934,233509070},
{4700000000LL,209613911,385033448,713286550},
{4750000000LL,701673616,4630487,478481798},
{4800000000LL,931159308,343476498,758759346},
{4850000000LL,273529742,123510951,559574147},
{4900000000LL,911018251,844873162,819634879},
{4950000000LL,735737583,50069349,807291540},
{5000000000LL,102334155,834419866,510853745},
{5050000000LL,546194588,750300092,629823236},
{5100000000LL,453748616,380127701,105335718},
{5150000000LL,748515983,333582883,717397248},
{5200000000LL,107048889,390015786,847424535},
{5250000000LL,604182954,849823797,805719845},
{5300000000LL,829771610,674464076,254470054},
{5350000000LL,662644186,691405710,857531668},
{5400000000LL,699302941,224841755,298551243},
{5450000000LL,696312499,415151264,944991009},
{5500000000LL,358703167,4108204,890320855},
{5550000000LL,55855689,756449583,328289318},
{5600000000LL,105381649,303763304,525352914},
{5650000000LL,781723795,827011659,448820505},
{5700000000LL,360721530,310754962,857760585},
{5750000000LL,975483289,577709280,52685746},
{5800000000LL,107935489,876144487,681148200},
{5850000000LL,37843332,544752241,536437737},
{5900000000LL,899099104,405695833,548456798},
{5950000000LL,486867813,748131286,178131345},
{6000000000LL,192473059,778742000,44066357},
{6050000000LL,655772232,959883325,340578923},
{6100000000LL,83949699,604379130,603077492},
{6150000000LL,274532785,377017593,588039164},
{6200000000LL,798695907,987490029,237828250},
{6250000000LL,991921272,793833055,118050107},
{6300000000LL,376714645,493425268,131564763},
{6350000000LL,905145457,407733836,329894868},
{6400000000LL,630738657,40742042,323979426},
{6450000000LL,666114064,507419503,82835832},
{6500000000LL,423131148,393087522,438560380},
{6550000000LL,159317181,453683822,64501406},
{6600000000LL,9067912,885062356,530005158},
{6650000000LL,204835455,297803373,313338976},
{6700000000LL,836474305,9483443,364311742},
{6750000000LL,450612130,843033549,798959260},
{6800000000LL,995872758,477732907,535307981},
{6850000000LL,947833675,273133904,358503572},
{6900000000LL,831324169,87422827,624510285},
{6950000000LL,381475374,787760461,328584572},
{7000000000LL,851432142,564706400,743595923},
{7050000000LL,632510732,135183955,27855009},
{7100000000LL,600615566,214053392,886680257},
{7150000000LL,348443220,946590379,85029062},
{7200000000LL,354243748,197953180,39519988},
{7250000000LL,775517598,840022891,730864932},
{7300000000LL,464640208,134548496,108960298},
{7350000000LL,795519643,145104138,220437360},
{7400000000LL,655980397,860282292,724037382},
{7450000000LL,996326724,736132270,873689389},
{7500000000LL,754133024,520778395,12431477},
{7550000000LL,456236860,920410944,26313171},
{7600000000LL,468426494,98306258,196023050},
{7650000000LL,591009897,176229915,90295131},
{7700000000LL,324986415,243523224,178248829},
{7750000000LL,845746762,799714204,250389174},
{7800000000LL,86045214,670409052,743558048},
{7850000000LL,413974258,617954369,680940578},
{7900000000LL,28665233,485431333,745732999},
{7950000000LL,583789742,227127313,8014425},
{8000000000LL,790216554,680057396,72124658},
{8050000000LL,616223581,686470846,135425954},
{8100000000LL,687118902,335111523,300236456},
{8150000000LL,348635994,133234909,71099802},
{8200000000LL,551848063,708710588,982785105},
{8250000000LL,558751888,725091355,900843974},
{8300000000LL,785195740,182795469,343811684},
{8350000000LL,705431595,772371734,175355691},
{8400000000LL,538182908,525990521,626511910},
{8450000000LL,506530244,894364059,149632636},
{8500000000LL,132616976,130328088,997709618},
{8550000000LL,397550553,287002118,8667026},
{8600000000LL,974887031,494543560,92863609},
{8650000000LL,17699582,419390685,968014196},
{8700000000LL,889164309,544925113,30851551},
{8750000000LL,799290343,570399136,809944342},
{8800000000LL,960002226,13041873,497292916},
{8850000000LL,595376346,683010963,477342001},
{8900000000LL,821409901,97304683,208207434},
{8950000000LL,180406948,537255912,359251725},
{9000000000LL,8390086,472596219,435523618},
{9050000000LL,404981171,600686514,857223824},
{9100000000LL,104796271,35705139,735173949},
{9150000000LL,265665181,791368954,832233301},
{9200000000LL,708897480,492649422,967192012},
{9250000000LL,963143862,80683669,431772218},
{9300000000LL,631160278,274064524,683421425},
{9350000000LL,49195630,553424623,789570416},
{9400000000LL,49423109,418163403,987738762},
{9450000000LL,196751983,228757258,365536401},
{9500000000LL,12869153,353801518,932680483},
{9550000000LL,858887289,590489615,101813519},
{9600000000LL,711883378,658146590,753961026},
{9650000000LL,577109763,112408030,317020930},
{9700000000LL,884291363,144996647,911124200},
{9750000000LL,587607390,391526600,296761552},
{9800000000LL,793850486,716622931,781900333},
{9850000000LL,603337683,280530601,812848706},
{9900000000LL,365069693,941248608,768071074},
{9950000000LL,937083772,521845005,860537547},
{10000000000LL,815449418,107920472,128493982},
{10050000000LL,349661522,81263199,757540818},
{10100000000LL,387456403,986746965,228658074},
{10150000000LL,165100590,672424519,667783094},
{10200000000LL,129970615,136766746,609970889},
{10250000000LL,173486920,482776237,20434929},
{10300000000LL,550271411,936172001,967263183},
{10350000000LL,982373823,216671174,406540668},
{10400000000LL,138930990,820329685,312921012},
{10450000000LL,246126625,354044899,589199170},
{10500000000LL,262532840,241000685,428102405},
{10550000000LL,234747151,959986180,693768280},
{10600000000LL,566594448,572566934,899109573},
{10650000000LL,858141753,297431947,697173869},
{10700000000LL,549141931,640232534,820244220},
{10750000000LL,583162530,27850797,142796785},
{10800000000LL,729025205,305680608,156730381},
{10850000000LL,47752756,132050888,479740031},
{10900000000LL,20314654,664011056,924641467},
{10950000000LL,776656083,936029035,847101659},
{11000000000LL,665487541,455141639,150693116},
};
ll N;
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	x=0;
	while(N>=memo[x+1][0]) x++;
	
	ll pre=memo[x][2],cur=memo[x][1];
	ll sum=memo[x][3];
	ll now=memo[x][0];
	
	while(now<N) {
		now++;
		ll nex=(cur+pre)%mo;
		(sum+=nex*nex)%=mo;
		pre=cur;
		cur=nex;
	}
	cout<<sum<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}
0