洛谷省选春令营--期望
题目描述
你在一个无穷大的二维平面上,可以进行移动。每次移动可以向上、下、左、右四个方向移动一个格子。比如当前的坐标为 ((0, 0)),移动一次后可以到达 ((1, 0), (0, 1), (0, -1), (-1, 0)) 四个坐标中的一个。
初始时你在 ((0, 0)),现在随机移动 (n) 次,求:期望可以访问多少个不同的点。
可以证明,答案乘以 (4^n) 是一个整数,你只需要输出答案乘以 (4^n) 再模 (998244353) 的结果即可。
数据范围
对于 (20\%) 的数据,满足 (1 leq n leq 10)。
对于 (40\%) 的数据,满足 (1 leq n leq 100)。
对于 (80\%) 的数据,满足 (1 leq n leq 1000)。
对于 (100\%) 的数据,满足 (1 leq n leq 100000)。
题解
对于第一部分分: 直接暴力搜索即可
对于第二部分分: 采用(O(n^3))算法
设g[x]表示从一个点出发, 走x步不经过原点的方案数, f[x][y]表示从原点出发到点(x, y)的路径条数(无限制)
也就是强制使一个点最后一次被经过时计算
可以设三维动态规划(时间, x, y)来计算方案数
对于第三部分分: (O(n^2))算法
设f[x]表示走x步到一个以前为经过的点的路径数, g[x]为走x步又回到原点的路径数
则
第一个式子, 易知要回到原点, 向上走的步数和向下走的步数相等, 向右向左也是, 所以向上走的步数加向右走的步数等于(frac i2), 先从i步中选一半出来是向上和向右为A组, 另一半为B组, 再和之前独立重新选出来一半, 这一半中和A组的交集向上走, 和B组的交集向左走, 模拟一下可以发现满足条件
另一种理解方式, 还是先选出来两个组, 枚举向上走的个数i, A组为(frac 2n choose i), B组一样
然后说f, 就是走i步有(4^i)条路径, 再减去以前到过此点的路径条数即可
对于最后部分分: (O(nlog_n))
观察f的递推式
多项式求逆就好了