Autumn Fest 2012 : D Don't Think Seriously!

ここからは本番でLargeを解き切れなかった問題。
他人の回答を見て勉強しながらチャレンジしていきます。
http://autumn_fest.contest.atcoder.jp/tasks/autumn_fest_04

３項間漸化式で表される簡単な数列に対し、A[n]を回答する問題。
問題はn<2^31と範囲が異常に大きいこと。

最初、Smallに対しては答えが0～1998の約2000パターンしかないので、A[i]とA[i+1]からA[i+2]を求める遷移表を作り、グラフの経路圧縮をしようとした。
でも、そもそも遷移表が2000x2000になるので経路圧縮するとメモリに収まりきらない。

本番はここであきらめて終了。
さて、実際この処理をA[2^31]まで試すとどの位かかるか？実は1分足らずで終わる。

この問題はどのテストケースも数列は同じ。
ということで、実は1～2^31の途中経過を60か所覚えておいて、残りだけ計算すれば１秒以下で終わる。

下記解法では、いったんgen関数で1～2^31まで数列を回して、0x1000000毎に途中経過を出力している。
あとはその途中経過をソースに張り付けて、実際のテストケースでは途中経過から処理を再開するだけ。
問題文の「ネタ枠」ってのは途中経過を事前に計算しとく手法のことなのかな？

ll N,M;
ll tab[2][128][3]=
{
{
{16777216,702,1298},
{33554432,1578,585},
(略)
{2113929216,1446,293},
{2130706432,1720,1971},
},
{
{16777216,44434072,433204601},
{33554432,881904762,793484513},
(略)
{2113929216,162135320,316906385},
{2130706432,388073006,600892915},
}};

void gen(){
	int loop;
	ll a,b,c,I,M;
	
	FOR(i,loop) {
		M=(i==0)?1999:1000000007;
	
		a=0;
		b=1;
		for(I=1;I<1LL<<31;I++) {
			if((I&0xffffff)==0) _P("{%lld,%lld,%lld},\n",I,a,b);
			c=(a*a+b*b)%M;
			a=b;
			b=c;
		}
	}
	return;
}

void solve() {
	int x,y,i,j,p,rr,TM,TTC,id;
	ll a,b,c,I,ret;
	
	//gen();
	N=GETi();
	M=GETi();
	
	id=(M==1999)?0:1;
	ret=a=0;b=1;I=1;
	FOR(i,127) if(N>=tab[id][i][0]) {
			a=tab[id][i][1];
			b=tab[id][i][2];
			I=tab[id][i][0];
	}
	
	for(;I<=N;I++) {
		ret=a;
		c=(a*a+b*b)%M;
		a=b;
		b=c;
	}
	
	_P("%lld\n",ret);
	return;
}

まとめ

2^31のループといっても１分位で終わる。
いざというときは事前に手元で計算しておいて、途中経過を使うことを考えよう。

似た問題はGCJ2009 R1Aにもあったね。
スクリプト言語で愚直に実装すると、ギリギリタイムアウトしてしまうのだが、Analysisに「事前に計算しとけば？」って書かれてる。
http://code.google.com/codejam/contest/188266/dashboard#s=p0