JOI 2009 春合宿 day1-1 sequence3
- 問題
- 解き方
偶奇のみに注目すればよく、mod 2 で考える。
与えられた漸化式によって出来る bit 列は、初めの長さ m のビット列さえ決まれば一意に定まるので、m bit分のパターンに注目すれば良さそう。
0と1しか取らないので、各位置をスタート地点とみなして 2^m 通りくらい試せばループする(m bit分を1セットとして区切ってやろうとすると空間計算量がm倍になるので注意)。
- 提出
偶奇のみに注目すればよく、mod 2 で考える。
与えられた漸化式によって出来る bit 列は、初めの長さ m のビット列さえ決まれば一意に定まるので、m bit分のパターンに注目すれば良さそう。
0と1しか取らないので、各位置をスタート地点とみなして 2^m 通りくらい試せばループする(m bit分を1セットとして区切ってやろうとすると空間計算量がm倍になるので注意)。