問題はこちら
No.657 テトラナッチ数列 Easy - yukicoder
T0=1として、n=0から数列が始まるとしてよい。
フィボナッチ数列同様、直前の4項を持って漸化式で求めることができる。
直前の4項は17^4=83521状態なので、高々83521の周期を持つ。
具体的に計算することで4912の周期をもつことがわかるので逐次計算すれば良い。
int main(){ int q; scanf("%d",&q); while(q--){ long n; scanf("%ld",&n); n%=4912; int a=1,b=0,c=0,d=0; while(n--){ int t=(a+b+c+d)%17; a=b; b=c; c=d; d=t; } printf("%d\n",a); } }
この手のものはループでやるか再帰でやるか悩むが、代入が多いので再帰でやったほうがよさそう。
出力まで再帰関数のなかでやってしまうことにするといろいろ噛み合う。
main再帰より通常の再帰の方が1B短い
i,n; main(a,b,c,d){n--%4912<1?++i>2&&printf("%d\n",d),~scanf("%d",&n)&&main(0,0,0,1):main((a+b+c+d)%17,a,b,c);}
n; f(a,b,c,d){n--%4912?f(b,c,d,(a+b+c+d)%17):printf("%d\n",a);} main(i){for(;~scanf("%d",&n);--i&&f(1,0,0,0));}
これで完成……といいたいところだが、%17をつける位置を第4引数から第3引数に変更することでカッコを外せる。
これにより第4引数は再帰のたびに大きくなることになるが、a+b+c<51なので1回の再帰で高々51しか増加せず、再帰回数は4912回以下なのでオーバーフローの心配はない
n; f(a,b,c,d){n--%4912?f(b,c,d,(a+b+c+d)%17):printf("%d\n",a);} main(i){for(;~scanf("%d",&n);--i&&f(1,0,0,0));}
107B