yukicoder : No.997 Jumping Kangaroo

こっちのほうが典型でとっつきやすい。
https://yukicoder.me/problems/no/997

問題

(WK+1)個の石が並んでおり、0～WKの番号がついている。
Wの倍数の番号の石は白く、他は黒い。
今0番の石から初めて、1回のジャンプで1～2W個先の石に移動すること繰り返し、最後WK番の石に移動することを考える。
ただし、(複数回のジャンプを合わせて)着地せず飛び越してしまう白石が2個以上あってはいけない。

条件を満たす移動経路は何通りか。

解法

f(n) := 条件に違反せずn*Wの石に着地する手順
とする。問題文の条件より白石を2つ飛ばすことはないので、
f(n) = A * f(n-1) + B*(n-2)
とかける。Aはジャンプを繰り返しちょうどW個の石を飛ぶ飛び方で、Bはジャンプを繰り返しちょうどW個の位置には着地せず2W個目の石に着地する飛び方である。
Wは大きくないので、A,Bは愚直にDPで求められる。

Kは大きいが、フィボナッチ数列の要領で行列累乗に持ち込めばOK。

ll dp[181];
int N,W;
ll K;
int A[81];
ll mo=1000000007;

const int MAT=2;
ll G[MAT][MAT],G2[MAT][MAT];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void powmat(ll p,int n,ll a[MAT][MAT],ll r[MAT][MAT]) {
	int i,x,y,z;
	ll a2[MAT][MAT];
	FOR(x,n) FOR(y,n) a2[x][y]=a[x][y];
	FOR(x,n) FOR(y,n) r[x][y]=(x==y);
	while(p) {
		ll h[MAT][MAT];
		if(p%2) {
			FOR(x,n) FOR(y,n) h[x][y]=0;
			FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (r[x][z]*a2[z][y]) % mo;
			FOR(x,n) FOR(y,n) r[x][y]=h[x][y]%mo;
		}
		FOR(x,n) FOR(y,n) h[x][y]=0;
		FOR(x,n) FOR(z,n) FOR(y,n) h[x][y] += (a2[x][z]*a2[z][y]) % mo;
		FOR(x,n) FOR(y,n) a2[x][y]=h[x][y]%mo;
		p>>=1;
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>W>>K;
	FOR(i,N) cin>>A[i];
	dp[0]=1;
	FOR(i,2*W) if(i!=W) {
		FOR(j,N) (dp[i+A[j]]+=dp[i])%=mo;
	}
	G[0][1]=dp[2*W];
	G[0][0]=dp[W];
	G[1][0]=1;
	powmat(K,2,G,G2);
	cout<<(G2[1][0]*dp[W]+G2[1][1])%mo<<endl;
	
	
}

まとめ

昔Tech Winという雑誌で「フリーゲームソフト作者によるパズルゲーム特集」というのがあって、Jumping Kというゲームがあったのを思い出した。