Sequence(数列 -) - joi2009-day1 解説

筆者: qnighy

ボナッチのような漸化式で定義された数列の偶奇の規則性を調べる問題である。

O(Q)解法

数列を指定された通りに列挙すれば、p,qの大きさに比例する時間で計算できる。この方法では、30点を獲得することができる。

数列の変形

規則性を調べやすくするために、数列を変形しよう。

まず、この問題では、数列の偶奇以外の条件は意味をなさない。そこで全ての数列を0か1だと考える。

続いて、この問題では、数列の連続するm項を保持しておけば、次の項は定まる。そこで、数列の各項は、直前m個の項を二進法として解釈したものだと考える。

すると、この数列は、直前の値から決定できる簡単な漸化式になる。さらに、この数列の値は直後の値からも一意に決まる。

そのため、この数列は全域において何らかのループ構造を持っていることがわかる。

数列の解析

上記のように変形した数列のループ構造は、訪問フラグを立てつつ列挙していけばよいので、簡単に調べられる。

例えば、m=5のとき、数列は長さ1,3,7,21のループ構造を1つづつ持っている。

これを調べると、どのmについても、その中での最大のループ構造の長さをL[m]とすると、mについてのどのループ構造もその長さはL(m)の約数になることがわかる。(なぜかはわからないが)

具体的には、以下のような配列が定義できる。

int L[] = {-1, -1, 3, 7, 15, 21, 63, 127, 63, 73, 889, 1533, 3255, 7905, 11811, 32767, 255, 273, 253921, 413385, 761763, 5461, 4194303, 2088705, 2097151};

ということは、元の数列は、必ずL[m]個周期ではループしているということになる。

あとは、0からL[m]の範囲内で、出現する奇数の個数を数え上げ、p,qをL[m]で割った商と余りに応じて加減すれば答えは求まる。

この方法で満点を獲得できる。なお、ループ構造の検出は、このような定数を埋め込まずに、その場で解析しても構わない。