AtCoder ARC #212 : F - Add Integer

あと少しというところで時間切れ。
https://atcoder.jp/contests/arc212/tasks/arc212_f

問題

正整数N,M,Xが与えられる。
以下を満たす整数列AにおけるA[0]*A[1]の総和を求めよ。

• AはN要素の整数列で、各要素は0以上M以下
• A[i+2]=A[i+1]-A[i]またはA[i+2]=A[i+1]+A[i]のいずれかを満たす
• A[N-1]=X

解法

Aの各要素を前から決めて行こうとすると、加算と減算どちらが生じるか考えるのが大変。
逆に後ろから考えると、A[i]=A[i+1]-A[i+2]またはA[i]=A[i+2]-A[i+1]だが、Aは0以上との条件からA[i]=|A[i+1]-A[i+2]|となる。
よって、後ろ2要素を決めればそれ以前の要素は確定する。

A[N-1]=Xは固定なので、A[N-2]を総当たりしよう。
そこからA[0]、A[1]を求める際、愚直にやるとA[N-2]１パターンにつきO(N)かかるので、以下２つの周期性を使い高速化しよう。

• A[i]=A[i-1]=xとすると、それ以前の要素は0,x,x,0,x,x,0,x,x...と3要素ずつ周期的になる
• A[i]=x、A[i-1]=yとし、xがyよりかなり大きい場合、A[i]以前の要素はx,y,x-y,x-2y,y,x-3y,x-4y,y,....と、３要素毎にxからyが1回余分に引かれた値が洋上する。

int N,M,X;
const ll mo=998244353;
map<pair<int,int>,ll> F,T;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>X;
	
	ll ret=0;
	FOR(i,M+1) {
		int step=N-2;
		int a=X,b=i;
		while(step) {
			if(a==b&&step>=3) {
				step%=3;
			}
			else if(b&&a>=2*b&&step>=3) {
				int c=min(a/b/2,step/3);
				a-=2*c*b;
				step-=3*c;
			}
			else {
				a=abs(b-a);
				swap(a,b);
				step--;
			}
		}
		(ret+=1LL*a*b)%=mo;
	}
	
	cout<<ret%mo<<endl;
}

まとめ

逆順にやることに気付いたが、それを高速化する時間がなかった。