$n$个人坐在一圈玩游戏, 分别标号$1 \sim n$. 初始每人手里有$k$张牌($2|k$). 一次洗牌, 每个人都会进行这样的操作: (当前手牌设为$x$)把 $\lfloor\frac{x}{2}\rfloor$ 张牌给左边的人, 把 $\lceil\frac{x}{2}\rceil$ 张牌给右边的人.

然而, 人群中有一个🤡, 每次他只会把所有牌给右边的人.

? p 用来询问当前局面, $p$ 号玩家有几张牌.

每次询问后都进行一次洗牌.

任务是用不超过 $1000$ 次询问, 找出🤡, ! p 用来回答找到的🤡.

$4 \le n \le 10^5, 2 \le k \le 10^9, 2 | k$

手玩可以发现, 🤡的牌数永远是 $k$, 而且在前 $\frac{n}{2}$ 次洗牌中, 🤡左边的人的牌比 $k$ 少, 右边的比 $k$ 多.

为什么要限制 $\frac{n}{2}$ 呢? 首先, 我们能用的询问很少, 根本到达不了 $\frac{n}{2}$, 所以可以直接假定就是前 $\frac{n}{2}$ 步. 其次, 大于这个数的时候, 就会出现少的和多的交换的情况, 这里不好处理, 我们就不处理.

证明一下:

$n$ 个连续的格子, 从左到右分别标号为 $1 \sim n$. 初始第 $i$ 个格子上的数为 $a_i$. 把从任意一点开始, 正好走 $k$ 步的一条路径成为合法路径. 每一步只能走相邻的格子, 且不能出界. 一条路径的价值是, 每一次走到一个格子, 价值就加上格子上的这个数.

给出$q$个修改, 每次只修改一个格子的数$a_i$, 输出每次修改后的所有路径价值之和模$10^9 + 7$.

$1 \le n, k, le 5000, 1 \le q \le 2 \cdot 10^5, 1 \le a_i \le 10^9$

显然要转化贡献. 这道题也难在转化贡献.

首先有一点很容易想: 我们要求第$i$个位置对所有路径的贡献$cnt_i$, 答案就是$\sum ai \cdot cnt_i$.

接下来, 如果用一条路径上出现的$i$个数求$cnt_i$, 就得用三维dp, 复杂度爆炸. 所以不能这么做.

再转化一次贡献, 求经过了第$i$个位置的合法路径有多少条. 由于一条路径可能不止一个, 所以我们再拆分一下. 设 $A_{i, j}$ 为 第 $j$ 步在 $i$ 的路径条数. 然后求和 $cnt_i = \sum_{j = 0}^k A_{i, j}$.

我从哪里来?

要到哪里去?

我觉得需要记忆的公式

因为一直再用 git 维护博客, 所以就想能不能在服务器上搞一个 git 仓库, 然后本地写博客, 用 git 推到服务器上.

总结一下微分方程的解法

年少轻狂, 伤了不少人.