526互联

[ZJOI2009] 多米诺骨牌

发布时间 2023-11-23 16:31:05作者: pidan007

脑子没了

直接做 \(2^{28}\) 肯定是不行的，所以必定要施加容斥，先考虑对行列均进行容斥，也就是枚举哪些行间、列间没有任何骨牌跨过，可以发现，这些行列将网格划分成了若干矩形，那么只要算出这些矩形的方案乘起来就行了，矩形的方案容易直接插头 \(dp\) 算

但是并没有起到优化的效果，因此考虑只对行进行容斥，列用带容斥系数的 \(dp\) 来算，发现这样就做完了