SRM403 500 : TheLuckySequence

テスト前は良くない。

問題概要

• 4と7のみで構成される数字がラッキーナンバーです。
• ラッキナンバーをlength個並べた数列Aがあったとして、
  A[i]の一番左の数とA[i+1]の一番右の数が一致していた場合それはラッキーな配列です。
  例）{447,74,4444,447} 
• 今 配列number[i]と、長さ lengthが与えられます。
• 各A[i]の要素は必ずnumber[j]のどれかに一致していなければいけません。
• ラッキーな配列は何通りありえますか？

解法

• dp + ダブリング
• まず、ラッキーナンバー以外は使わないのでnumber[i]からラッキーナンバーだけを抽出します。
• こうして出来た新しいnumber[i]の要素数がlengthより大きい場合は普通に
  dp[今幾つ目のを見ているか][あといくつ数字を使うか]=何通り？
  でDPして終わり。
• もしlengthより小さい場合はnumber[i]の要素数に対してまず上のdpをしてやります。
• すると
   4から始まって4で終わる通り数 と
   4から始まって7で終わる通り数 と
   7から始まって4で終わる通り数 と
   7から始まって7で終わる通り数 に場合わけできます。
• 4->7 = 4->4 * 4->7 + 4->7 * 7->7 のような式で 組み合わせをつなぎ合わせることができます。（ソースのxros関数を参照 )
• これを利用して2^k回繰り返した時の通りの数が分かるので
  ダブリングによってlengthの値が巨大なときも対応することができます。
• あまりが出てしまった場合はもう一度、DPしてxrosの式で掛けあわせます。

ソースコード

感想

解法思い付いたときはすげえ教育的良問だ！

と思ったのも束の間実装に１時間以上かかるとは思わなかった。

最初、二次元配列のコピー怖くてずらずら書いてたらコードがやばいことになったのでこれでもマシになった方。

時間ないに思い付くことが出来ても解ける気がしない。

迅速な実装力が必要（もっと賢い方法があるのかなぁ‥）