思路
容易看出来是个 DP 题，但是你发现 DP 的起点是不好确定的，于是假定第一条边的起点是黑色。然后你发现设为白色的贡献与黑色是相同的，于是直接令第一条边的起点是黑色，最后答案乘以 \(2\) 即可。
然后就可以愉快的 DP 了。
首先枚举每条边白色点的数量 \(k\)，定义 \(dp_{i,0/1}\) 表示确定了前 \(i\) 条边，且第 \(i\) 条边的终点为 黑色/白色。转移就比较显然了，递推起点为 \(dp_{0,0} = 1\)：
\[\left\{\begin{matrix} dp_{i,0} = dp_{i - 1,0} \times \binom{d - 1}{k} + dp_{i - 1,1} \times \binom{d - 1}{k - 1}\\ dp_{i,1} = dp_{i - 1,0} \times \binom{d - 1}{k - 1} + dp_{i - 1,1} \times \binom{d - 1}{k - 2} \end{matrix}\right. \]但是这样转移的复杂度高达 \(\Theta(nd)\)，但是仔细观察发现这个式子与矩阵乘法类似。
令 \(c_1 = \binom{d - 1}{k},c_2 = \binom{d - 1}{k - 1},c_3 = \binom{d - 1}{k - 2}\)。
于是考虑维护 \(\begin{bmatrix} dp_{i,0} & dp_{i,1} \end{bmatrix}\) 这个矩阵，它将转移为 \(\begin{bmatrix} dp_{i,0} \times c_1 + dp_{i,1} \times c_2 & dp_{i,0} \times c_2 + dp_{i,1} \times c_3 \end{bmatrix}\)。
容易构造出转移矩阵：
\[\begin{bmatrix} c_1 & c_2\\ c_2 & c_3 \end{bmatrix} \]直接矩阵快速幂优化即可。
Code
#include <bits/stdc++.h>
#define re register
#define int long long
#define Add(a,b) (((a) % mod + (b) % mod) % mod)
#define Mul(a,b) (((a) % mod) * ((b) % mod) % mod)
using namespace std;
const int N = 1e7 + 10,M = 1e4 + 10,mod = 998244353;
int n,d,ans;
int fac[M],inv[M];
struct mat{
int n,m;
int mt[5][5];
mat(int a,int b){
n = a;
m = b;
memset(mt,0,sizeof(mt));
}
mat friend operator *(const mat &a,const mat &b){
mat t(a.m,b.m);
for (re int i = 1;i <= a.n;i++){
for (re int j = 1;j <= b.m;j++){
for (re int k = 1;k <= a.m;k++) t.mt[i][j] = Add(t.mt[i][j],Mul(a.mt[i][k],b.mt[k][j]));
}
}
return t;
}
}base(2,2),dp(1,2);
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
inline int qmival(int a,int b){
int res = 1;
while (b){
if (b & 1) res = Mul(res,a);
a = Mul(a,a); b >>= 1;
}
return res;
}
inline mat qmi(mat a,int b){
mat c(a.n,a.n);
for (re int i = 1;i <= c.n;i++) c.mt[i][i] = 1;
while (b){
if (b & 1) c = c * a;
a = a * a;
b >>= 1;
}
return c;
}
inline void init(){
fac[0] = 1;
for (re int i = 1;i <= d;i++) fac[i] = Mul(fac[i - 1],i);
inv[d] = qmival(fac[d],mod - 2);
for (re int i = d - 1;~i;i--) inv[i] = Mul(inv[i + 1],i + 1);
}
inline int C(int n,int m){
if (n < m || m < 0) return 0;
return Mul(fac[n],Mul(inv[n - m],inv[m]));
}
inline int f(int k){
int c1 = C(d - 1,k),c2 = C(d - 1,k - 1),c3 = C(d - 1,k - 2);
dp.mt[1][1] = 1;
base.mt[1][1] = c1; base.mt[1][2] = c2; base.mt[2][1] = c2; base.mt[2][2] = c3;
mat ans = dp * qmi(base,n);
return Mul(ans.mt[1][1],2);
}
signed main(){
n = read(),d = read(); init();
for (re int i = 0;i <= d;i++) ans = Add(ans,f(i));
printf("%lld",ans);
return 0;
}