Մեջբերում soultaker-ի խոսքերից Նայել գրառումը
Կառաջարկեմ նույն խնդիրը, երբ տարիների քանակը կարող է լինել մինչև 1 000 000 000, իսկ պատասխանի փոխարեն պետք է տպել քանակը 1 000 003 -ի վրա բաժանվելուց ստացվող մնացորդը (մեծ թվերից խուսափելու համար):
Երկար հանրահաշիվ գրելու հավես չկա, բայց դրա վրա մտածել կարելի ա: Իմ գրած լուծումը փաստորեն O(N) ա, նույնիսկ եթե n-րդ անդամի համար ինչ-որ բանաձև գտնեմ, չգիտեմ O(N)-ից ավելի լավ ժամանակում կլինի հաշվել, թե չէ : Իսկ եթե պետք ա, որ մի 10 րոպեի մեջ տեղավորվի, գրածս լուծումը կարելի ա հեշտությամբ ձևափոխել, որ հիշողության օգտագործումը O(1) լինի:
Կոդ:
#include <iostream>
#include <time.h>

using namespace std;

#define MOD 1000000

double getTime()
{
	return (double(clock())/CLK_TCK);
}

int F[2][40], N;

int main()
{
	cin >> N;
	double startTime = getTime();
	F[0][15] = 1;
	for (int i = 1, x = 1; i <= N; i++, x ^= 1)
	{
		int s = 0;
		for (int j = 15; j < 35; j++)
			s = (s + F[x ^ 1][j]) % MOD;
		F[x][1] = s;
		for (int j = 2; j <= 35; j++)
			F[x][j] = F[x ^ 1][j - 1];
	}
	int ans = 0;
	for (int i = 1; i <= 35; i++)
		ans = (ans + F[x ^ 1][i]) % MOD;
	cout << ans << endl;
	cout << "Time: " << getTime() - startTime << endl;
	return 0;
}
Իմ մոտ 450 վրկ. էր 1,000,000,000-ի համար: