kmjp's blog

競技プログラミング参加記です

yukicoder : No.980 Fibonacci Convolution Hard

yukicoder

勉強になりました。
https://yukicoder.me/problems/no/980

問題

整数pに対し、以下の数列を考える。

  • a_1 = 0
  • a_2 = 1
  • a_n = pa_{n-1} + a_{n-2} (n \ge 3)

クエリとして正整数qが与えられる。以下の値をmod 10^9+7で答えよ。

  • \displaystyle S_q = \sum_{s+t=q, 1 \le s,t \le q-1} a_s \cdot a_t

解法

いくつかの解法がある。自分が最初思いついたのは数列を求めた後Garner法を使った任意modでのNTTだった。
Editorialの解法も興味深いが、自分はTLで(最近流行りの？)母関数解法を見かけたのでそちらで解いた。

まず、数列aが1-indexedだと面倒なので、0-indexedで考える。すなわちa_0=0, a_1=1だし、クエリはqから2を引いておいて \displaystyle S_q = \sum_{s+t=q, 0 \le s,t \le q} a_s \cdot a_tを求めればよい。
まず元の数列aの母関数f(x)を求めよう。f(x)=yと置くと
\displaystyle y-a_0-a_1x = px(y-a_0x) + x^2yなので式変形すると \displaystyle f(x) = \frac{x}{1-px-x^2}となる。
次にS_qを考えるわけだが、これは式の形を考えるとS_qの母艦数g(x)=f^2(x)であることがわかる。
すると \displaystyle g(x)=f^2(x) = \frac{x^2}{x^4+2px^3+(p^2-2)x^2-2px+1}となる。
よってもとに戻すと \displaystyle S_q = 2pS_{q-1} + (2-p^2)S_{q-2}-2pS_{q-3}-S_{q-4}となるので、S_0～S_3を最初に求めておけばあとはS_qを順次前計算できる。

int N;
ll P;
ll mo=1000000007;
ll A[2020202];
int Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>P;
	A[2]=1;
	A[3]=2*P%mo;
	for(i=4;i<=2020101;i++) {
		A[i]=2*P*A[i-1]%mo+(2-P*P%mo)*A[i-2]%mo-2*P%mo*A[i-3]%mo-A[i-4];
		A[i]=(A[i]%mo+mo)%mo;
	}
	
	
	cin>>Q;
	while(Q--) {
		cin>>x;
		cout<<A[x-2]<<endl;
	}
}

まとめ

母関数を使うテク、まだ慣れてないので徐々に慣れないとな。