E的一个不同的解法

考虑dp，令f[i][0/1][0/1]表示考虑前i位，且当前位是奇数/偶数，上一位是奇数/偶数的方案数

以f[i][0][0]转移为例子，假如当前位是0，上一位是0，那么上上位就必须填0（三位之和为偶数）

f[i][0][0]=f[i-1][0][0]*(k/2)，k/2表示k内的偶数个数

由此可以类推f[i][0][1]，f[i][1][0]，f[i][1][1]的转移方程

发现i那一维可以滚动，并且这个玩意可以用矩阵快速幂优化，就可以通过了

//dp代码
#include<iostream>
using namespace std;
int n;
const long long mod=1e9+7;
long long k,f[2][2],g[2][2];
int main(){
	cin>>n>>k;
	g[0][0]=(k/2)*(k/2)%mod;
	g[0][1]=g[1][0]=(k/2)*((k+1)/2)%mod;
	g[1][1]=((k+1)/2)*((k+1)/2)%mod;
	for (int i=3;i<=n;++i){
		f[0][0]=g[0][0]*(k/2)%mod;
		f[0][1]=g[1][0]*((k+1)/2)%mod;
		f[1][0]=g[1][1]*(k/2)%mod;
		f[1][1]=g[0][1]*((k+1)/2)%mod;
		g[0][0]=f[0][0];
		g[0][1]=f[0][1];
		g[1][0]=f[1][0];
		g[1][1]=f[1][1];
	}
	cout<<(f[0][0]+f[0][1]+f[1][0]+f[1][1])%mod;
	return 0;
}
//矩阵快速幂优化后代码
#include<cstdio>
#include<cstring> 
#include<iostream>
using namespace std;
const int N=10;
const long long mod=1e9+7; 
int n;
long long k;
struct NODE{
	long long g[N][N];
}f,res;
void prepare(NODE &x){
	for (int i=1;i<=4;++i){
		for (int j=1;j<=4;++j){
			if (i==j) x.g[i][j]=1ll;
			else x.g[i][j]=0ll;
		}
	}
}
void mul(NODE &x,NODE &y,NODE &z){
	memset (z.g,0,sizeof (z.g));
	for (int i=1;i<=4;++i){
		for (int j=1;j<=4;++j){
			if (x.g[i][j]){
				for (int k=1;k<=4;++k){
					z.g[i][k]+=x.g[i][j]*y.g[j][k];
					z.g[i][k]%=mod;
				}
			}
		}
	}
}
void quickpow(long long k){
	prepare(res);
	NODE tmp=f,t;
	while (k){
		if (k&1){
			mul(res,tmp,t);res=t;
		}
		mul(tmp,tmp,t);tmp=t;
		k>>=1;
	}
}
long long h[10][10],ans[10][10];
int main(){
	scanf ("%d%lld",&n,&k);
	h[1][1]=(k/2)*(k/2)%mod;
	h[2][1]=h[3][1]=(k/2)*((k+1)/2)%mod;
	h[4][1]=((k+1)/2)*((k+1)/2)%mod;
	memset (f.g,0,sizeof (f.g));
	f.g[1][1]=k/2;
	f.g[2][3]=(k+1)/2;
	f.g[3][4]=k/2;
	f.g[4][2]=(k+1)/2;
	quickpow(n-2);
	long long anss=0;
	memset (ans,0,sizeof (ans));
	for (int i=1;i<=4;++i){
		ans[i][1]+=res.g[i][1]*h[1][1]%mod;
		ans[i][1]%=mod;
		ans[i][1]+=res.g[i][2]*h[2][1]%mod;
		ans[i][1]%=mod;
		ans[i][1]+=res.g[i][3]*h[3][1]%mod;
		ans[i][1]%=mod;
		ans[i][1]+=res.g[i][4]*h[4][1]%mod;
		ans[i][1]%=mod;
		anss+=ans[i][1];
		anss%=mod;
	}
	cout<<anss<<endl;
	return 0;
}