Codeforces 392(#230 Div1) C. Yet Another Number Sequence

問題

フィボナッチ数Fiは
F1 = 1, F2 = 2, Fi+2 = Fi+1 + Fiであらわされる数列である。
n, kが与えられたとき、
Σ[1≦i≦n] Fi * i^kをmod 10^9 + 7で求めよ。

制約条件

n≦10^17
k≦40

方針

Fi * i^j (0≦j≦40)を Fi-1 * (i-1) ^ l (0≦l≦40)の式で表せれば、
行列の累乗を使って和を求めてやることができそう。


Fi+1 * (i+1) ^ k = (Fi + Fi-1) * Σ[0≦j≦k]kCj * i^jで、
Fi-1 * i^jの部分は更に展開できて、
Fi-1 * (i-1 + 1)^j = Fi-1 * Σ[0≦l≦j]jCl * (i-1)^l


となるので、Fi+1 * (i+1) ^ kは、Fi * i^jとFi-1 * (i-1)^jの定数倍の和の形で書くことができる。

ベクトル
[Fi * i^0, Fi * i^1, ... Fi * i^k, Fi-1 * (i-1)^0, Fi-1 * (i-1)^1, ..., Fi-1 * (i-1)^k, sum]'
というベクトルに左から掛けるとiが1増えるような行列Aは、上の考察から書くことができて、
A^nは繰り返し二乗法を使えば80^3 * lognくらいの時間計算量で計算できる。

ソースコード

ll C[50][50];

int main(){
	rep(i, 50) rep(j, i+1) C[i][j] = j==0||j==i ? 1 : (C[i-1][j] + C[i-1][j-1]) % mod;
	
	ll n, p;
	cin >> n >> p;
	M m(83, vi(83));
	
	rep(k, 41) rep(i, k + 1){
		m[k][i] += C[k][i];
		rep(j, i+1) (m[k][j+41] += C[k][i] * C[i][j] % mod) %= mod;
	}
	rep(i, 41) m[i+41][i] = 1;
	m[82][p] = 1;
	m[82][82] = 1;
	
	m = pow(m, n-1);
	
	M a(83, vi(1));
	rep(i, 41){
		a[i][0] = i == 0 ? 2 : (a[i-1][0] * 2) % mod;
		a[i+41][0] = 1;
	}
	a[82][0] = 1;
	a = m * a;
	
	cout << a[82][0] << endl;
	
	return 0;
}