SRM 475 600pt: RabbitIncreasing

TopCoder

問題概要

a[0]=1, b[0]=1である。a[n+1]=b[n], b[n+1]=a[n]+b[n]、ただし、いくつかのnについてはb[n+1]=a[n]/2である。a[K]+b[K]をmod 10^9+9(=:P)で求める問題。K<10^7。

考えたこと

  • (当時は行列計算実装している間に終わった記憶がある)
  • 漸化式の形に落とすことはできた。
  • mod Pの中で割り切れない可能性のある割り算ってどうするんだ？
  • そもそも1とP+1では割った結果が違うんだから、mod Pの値だけでは情報が足りないことは分かる。
  • でもそれ以上が分からない。
  • 結局諦めてEditorialを読んだ。
  • mod 2^55(55は割り算が生じる回数の上界)での値も覚えておけばよいらしい。なるほど賢い。
  • この問題正解者が少なかったっぽい。
  • 行列累乗でさらに計算量を落とすこともできる。面倒だけど。

practiceで通ったコード

計算量O(K)。

#include <vector>
using namespace std;

typedef unsigned long long uint64;

const uint64 MOD = (int)(1e+9 + 9);
const int MAX_K = (int)(1e+7);

bool leave[MAX_K+1];

struct RabbitIncreasing {

	int getNumber(vector <int> leaving, int k) {
		if(leaving[0] == 1){
			return 0;
		}

		for(int i=0; i<(int)leaving.size(); i++){
			leave[leaving[i]] = true;
		}

		uint64 zero_mod = 1, zero = 1, one_mod = 0, one = 0;
		for(int y=2; y<=k; y++){
			uint64 tmp_mod = one_mod, tmp = one;
			if(leave[y]){
				if(zero%2 != zero_mod%2){
					zero_mod += MOD;
				}
				one_mod = zero_mod / 2;
				one = zero / 2;
			}
			else{
				one_mod = (one_mod + zero_mod) % MOD;
				one += zero;
			}
			zero_mod = tmp_mod;
			zero = tmp;
		}

		return (int)((zero_mod + one_mod) % MOD);
	}

};