阅读 80

棋盘多项式

首先考虑这个题如果确定了第一列和第一行那么就确定了,然后如果确定了一个三角那么就能确定第四个数

所以确定第一行且确定了第二行第一个数就能确定第二行

考虑dp,长度为i的连续段中黑白染色,染出的最大黑连续段为x的方案数

然后我们发现这个可以整除分块

然后这个转化为长度为i的连续段中,染出的最大黑连续段>=x的方案数

然后拆出来的这个g是个线性递推,快速幂秒了

另外的话有一个优化是把他抽象成走x+1步-1,走1步贡献+2

然后抽象出来组合意义是i*(m+1)

 

原文:https://www.cnblogs.com/wyxmrzakioi/p/15355135.html

文章分类
百科问答
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐