Facebook hacker cup qualification C. Find the Min

2013-01-31

22:35 |

m[0] = a, m[i] = ( b * m[i-1] + c ) % r (0＜i＜k), m[i] = m[i-k]からm[i-1]までに含まれない0以上の数(k≦i) のとき、m[n-1] を求める問題。
1≦k≦10^5, k＜n≦10^9, 0≦a,b,c≦10^9, 1≦r≦10^9

うゲェ

小さいのから埋めてくのでm[k]からm[2k]は0〜kが重複なくふくまれる
その後、m[2k+1] を求めるにあたって直前の k 個は 0〜kが重複なく含まれるとこから m[k] が抜けたものなので、そこに含まれないのは m[k] となり、
結局 m[2k+1]==m[k] になるというふうにして以下繰り返すので、m[i] の値としては k+1 周期になる。ある程度進んだあとに (n-1-i)%(k+1)==0なる i で打ち切る。
ということで、ある程度m[i]の値を求める部分を工夫して速くすればいい
「m[i-(k-1)]からm[i]までに現れる数字→その個数」という配列を用意して１こ進める度に更新してく
次の数字はO(k)で探す

accepted

気づかなかったけど O(k^2) なので実は危なかったのでは

int main() {
	int T;
	cin>>T;
	REP(ttt, T) {
		ll N,K,A,B,C,R;
		cin>>N>>K>>A>>B>>C>>R;
		
		VI w(K);
		w[0] = A;
		RANGE(i, 1, K) {
			w[i] = (B * w[i - 1] + C) % R;
		}
		VI ww(K+2); // [0, K+2)
		REP(j, K) if(w[j]<ww.size()) ww[w[j]]++;
		
		ll ans = -1;
		RANGE(i, K, N) {
			ll nxt = -1;
			REP(j, ww.size()) {
				if(ww[j]==0) {
					nxt = j;
					break;
				}
			}
			assert(nxt!=-1);
			
			int rm = w[i%K];
			if(rm<ww.size()) ww[rm]--;
			
			int add = nxt;
			if(add<ww.size()) ww[add]++;
			
			w[i%K] = nxt;
			
//			if((N-1-i)%(K+1)==0) {
//				cout<<i<<" "<<nxt<<endl;
//			}
			ans = nxt;
			if(5*K<N && (N-1-i)%(K+1)==0) break;
		}
		
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
//		break;
	}
	return 0;
}