PKU2680

http://acm.pku.edu.cn/JudgeOnline/problem?id=2680
まぁ問題文の詳しい説明は省略。
今回は多倍長演算問題なので打倒Javaを目標にコード短縮。目標達成したので公開
まだ無駄があるようなないような

この手の問題はどうやって計算するかでコードの長さの大部分が決まります。
そのため、どの数式で答えを出すかがショートコードでは非常に重要となります。
今回、自分が選んだのは漸化式で出す方法です。

さて、この問題の答えは以下の漸化式で求められます。

また、この式のの部分は多倍長演算のcarry部分に突っ込めば無駄なく処理できます。

では後は具体的なコードで。

char*c;v,t[1025][99];
main(n){
	for(;n<<22;v=n%2*2-1,strrev(t+n++))
		for(396[c=t+n]=48;*c|v;v/=10)
			c++[396]=(v+=*c*2%48)%10+48;
	while(~scanf("%d",&n))puts(t-~n);
}

自分でも、もはや何をしているのかわからないカオスコードです。
前半部はTLE回避のために配列にcacheする部分。
後半部は配列上のデータを順に表示するだけです。