写在前面:昨天写T1做法汇总的时候,本来敲了数学,还有两个是模拟和构造,但是这么久的T1都没考数学就删掉了,今天再补上
弹弹游戏
首先,数据范围 $ 10^9 $ ,显然不是正常可以过的
然后观察数据只输入 $ n,m $ 要么数学要么dp,考虑数学
首先一个小结论:每个点若被经过,只会被经过一次或两次,这是大容斥的基础
证明?要么左上到右下,要么右上到左下,再被经过必定重复
然后:经过的所有点数?
弹弹问题经典构造:翻折4次+平移构造坐标
得到:总情况为 $ lcm(n-1,m-1) $
考虑减去经过2遍的
如上图
黑色有多少个?首项d+1,后面公差2d, $ (n-d-1)/2d +1 $ ,注意到最后一列如果有的话也做不成经过两次,所以 $ (n-d-1-1)/2d +1$,从上往下同理,$ (m-d-1-1)/2d+1 $,两列相乘得到黑色个数
红色有多少个?首项 $ 2d+1 $ ,公差 $ 2d $
同理减去末尾
$ ((n-1-1)/(2 \times d)) \times ((m-1-1)/(2 \times d)) $
此外特别注意,每一项的除法都应该是下取整,所以妙用括号不可少,还有就是等差数列求项数的加1千万不要忘,错出来的(
$ over $