yukicoder : No.510 二次漸化式

いろいろ想定解以外で解いてしまった。
http://yukicoder.me/problems/no/510

問題

以下の漸化式を考える。

• 
• 
• 

初期状態で数列x,yの各要素は0とする。
以下のクエリを順次処理せよ。

• xまたはyの1要素を変更する。
• a_i % (10^9+7)を答える。

解法

想定解は、SegTreeを用いた行列積。
の4値からなるベクトルからを計算するための行列を求め、その積を求めていけばよい。

ただ、この問題はN,Qが小さく、X,Yの多くは0である。
よって適当に計算をさぼりつつ毎回a_iを計算しても間に合ってしまう。

int N,Q;
ll X[101010];
ll Y[101010];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	while(Q--) {
		cin>>s>>x;
		if(s=="x") cin>>X[x];
		else if(s=="y") cin>>Y[x];
		else if(s=="a") {
			ll A=1,B=1;
			FOR(i,x) {
				if(X[i]) (A += X[i]*B%mo*B)%=mo;
				if(Y[i]) B = (B*Y[i]+1)%mo;
				else B=1;
			}
			cout<<A<<endl;
		}
	}
}

まとめ

行列積解法思いつかずゴリ押ししてしまったけど、まぁ計算時間を見積もるスキルも重要ということで勘弁してください。