yukicoder : No.2989 Fibonacci Prize

この知識は最近も出てきたので覚えてた。
https://yukicoder.me/problems/no/2989

問題

整数N,Mが与えられる。
フィボナッチ数列f(n)において、

• f(L)+f(L+1)+...+f(R)がNの倍数で、かつf(M)以下となるような(L,R)の組み合わせを求めよ。

解法

M≦2の場合は愚直に試せばよい。
M＞2の場合、まずf(M)以下となる条件を考えると、

• R≦M-2
• (L,R)=(M-2,M-1)
• (L,R)=(M-1,M-1)
• (L,R)=(M,M)

のいずれかである。

f(n) % N はおよそ6N以下の周期性を持つ。
またその周期Lに対し、f(1)～f(L)の和はNの倍数である。
ここから、f(n)までのprefix sumをNで割った余りが、R≦M-2以下で何個あるかはO(N)で求められる。
よってR≦M-2のケースにおける(L,R)の組み合わせはO(N)で算出できる。

残り3ケースも、周期性からf(M-2),f(M-1),f(M)をNで割った余りは容易に算出できるので、それぞれ実際に値を見てみればよい。

ll N,M,L;
ll F[1<<22];
ll cnt[1<<22];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	if(N==1&&M==1) {
		cout<<2<<endl;
		return;
	}
	
	
	map<pair<int,int>,int> memo;
	F[1]=F[2]=1%N;
	memo[{1%N,1%N}]=1;
	for(i=3;i<=1<<21;i++) {
		F[i]=(F[i-1]+F[i-2])%N;
		if(memo.count({F[i-1],F[i]})) {
			L=i-2;
			break;
		}
		memo[{F[i-1],F[i]}]=i-1;
	}
	assert(L);
	
	ll ret=0;
	// F[M]
	if(F[M%L]==0) ret++;
	if(M-1>0&&F[(M-1)%L]==0) ret++;
	if(M-2>0&&(F[(M-1)%L]+F[(M-2)%L])%N==0) ret++;
	M-=2;
	
	if(M>=1) {
		cnt[0]++;
		int cur=0;
		for(i=1;i<=L;i++) {
			cur=(cur+F[i%L])%N;
			cnt[cur]+=M/L;
			if(i<=M%L) cnt[cur]++;
		}
		FOR(i,N) ret+=1LL*cnt[i]*(cnt[i]-1)/2;
	}
	
	
	cout<<ret<<endl;
	
}

まとめ

なんで周期が6N程度に収まるかの理屈はよく理解できてないな…。