Atcoder Beginner Contest 265

发布于 2022-08-23  70 次阅读


E

这题的思路很简单,在map上跑dp都能过。但有个关于时间复杂度的问题困扰了我一天。

题意

初始在二维平面上的(0,0)点,接下来每一步可以有三种移动:
1. 从(x,y)移动到(x+A,y+B)
2. 从(x,y)移动到(x+C,y+D)
3. 从(x,y)移动到(x+E,y+F)
有一些障碍物不能走,问n次移动后有几种不同的路径。(1\leq n \leq 300

题解

每一步都有三个新方向可以走,那么走n步应该就是有3^n种情况,感觉是妥妥超时的。但看了题解发现就每一步暴力扩展即可。

通过打表和简单思考,发现其实每一步会扩展到很多重复的点。但奇怪的是,每一步重复的数量都是有规律的,最终每一步扩展到的点满足通项\frac{n(n-1)}{2}

想了很多线性代数方面的推论,比如线性相关之类的。但其实结论是交换律。假设第一步走到了(x+A,y+B),(x+C,y+D)两个点,下一步从这两个点扩展到达(x+A+A,y+B+B),(x+A+C,y+B+D),(x+C+A,y+D+B),(x+C+C,y+D+D)四个点。关注中间两个点,发现只是交换了加法顺序而已,所以其实是一个点。

所以每次扩展的时候并不是直接乘3,而是\sum^n_{i=1}i。(第一个点可以加上n种转移,第二个点可以加上n-1种。。。)

结论

遇事不决好好打表,简化问题一眼就能看出来了。也没有必要钻牛角尖。


盛夏日落迟 灯火未夜匆匆明