插头DP 专题训练 动态规划

插头DP 专题训练

做了接近一天插头DP,感觉大体上比较理解了。 首先,这玩意主要是处理棋盘上路径/回路的计数或是最值查询,数据范围的特点是列数比较小(大概在10左右),行数可以稍多一些,有时候数据不保证行数大于列数,需要对矩阵进行旋转后再做。 主要是引入了插头的概念,DP时逐格转移,并状压轮廓线上m+1个插头的状态(···
BZOJ4652 [NOI2016]循环之美 数学

BZOJ4652 [NOI2016]循环之美

题目链接(UOJ) 反演+杜教筛神题,大概可以推到多数人解法的84分那里,剩下的部分会一种记忆化的方法(复杂度玄学,但是跑的比他们快)。 首先,不管是打表还是瞎猜得到题目要求的式子,之后化简成这个样子: $$\sum_{i=1}^{n} \sum _{j=1}^{m} [gcd(i,j)=1]\, ···