本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-05 09:54:31

• 题目大意： 有一个 $n$ 边形，每条边上有 $d+1$个石子，相邻两边公用一个石子。石子有白色或者黑色。问一共有多少种方案使得所有边上的白色石子数量相同。对 998244353 取模。

$n≤10^{12},d≤10^4$。

• 题目分析 独立思考完成。

每条边的白点数一致。
算上重复的端点，每条边为D+1个数,里面有0...D+1个黑点。黑白是对称的，实际可算一半。
设白点数为t
要考虑端点的情况:
$a00=c(d-1,t-2) $
$a01=a10=c(d-1,t-1) $
$a11=c(d-1,t)$
然后把这n条边连起来。n这么大，基本要o（1）或者 矩阵快速幂转移
设把i条边连起来的方案数为f[i][0/1]
设1号边起点。f[i][0/1]代表连接了第i条边后的右端点颜色。
$fi0=fi-1,0a00+fi-1,1a10 \space \space \space a00 a10 fi-1,0$
$fi1=fi-1,0a01+fi-1,1a11 \space \space \space a01,a11 fi-1,1$

然后通过矩阵快速幂求出$fn0+fn1$  记作f(t) 
	最后的答案：sigma(ft)(t=0..n)