[ABC256G] Black and White Stones-环形-矩阵优化DP
wflengxuenong
·
·
个人记录
- 题目大意：
有一个 n 边形，每条边上有 d+1个石子，相邻两边公用一个石子。石子有白色或者黑色。问一共有多少种方案使得所有边上的白色石子数量相同。对 998244353 取模。
- 题目分析
独立思考完成。
每条边的白点数一致。\
算上重复的端点，每条边为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,0*a00+fi-1,1*a10 \space \space \space a00 a10 fi-1,0$ \
$fi1=fi-1,0*a01+fi-1,1*a11 \space \space \space a01,a11 fi-1,1
然后通过矩阵快速幂求出$fn0+fn1$ 记作f(t)
最后的答案：sigma(ft)(t=0..n)