not ez problem 6
luogu_gza
·
·
学习·文化课
原题 AT_ajo2024_final_c。
AtCoder 君参加了一场由 n 道题目组成的测试。在这场测试中，题目会依次被出题，每一题的难度会根据当前的答题情况发生变化，具体规则如下：
- 如果当前的正确数大于等于错误数，那么 AtCoder 君以概率 1/3 正确回答下一题。
- 如果当前的正确数小于错误数，那么 AtCoder 君以概率 2/3 正确回答下一题。
- 此外，假定每题答对或答错的概率都是独立的。也就是说，每次解题时，都以概率 1/3 或 2/3 掷一次硬币，若正面朝上则答对。
只要答对超过一半的题目，就算合格。
那么，把 AtCoder 先生合格的概率乘以 3^n 后得到的值 f(n) 是整数。
给定一个整数 N，请计算 \sum_{n=1}^N \left\lfloor \frac{10^{18}}{n} \right\rfloor \times f(n) 模 10^9 + 7 的结果，并输出。
::::info[题解]
credits to GPT.
我们把题意改成平面上走路。$h\ge 0$ 时，向上走一步的权值为 $1$，向下走一步的权值为 $2$，$h<0$ 时，向上走一步的权值为 $2$，向下走一步的权值为 $1$。一条路径的权值为各步权值之积，$f(n)$ 就是走 $n$ 步后，高度严格为正的所有路径的权值和。
令 $a_{n,h}$ 表示走 $n$ 步到达高度 $h$ 的权值和，我们定义 $Z(z)=\sum_{n\ge 0}a_{n,0}z^n,A(z,u)=\sum_{n\ge 0}\sum_{h\ge 1}a_{n,h}z^nu^h,B(z,u)=\sum_{n\ge 0}\sum_{h\ge 1}a_{n,-h}z^nu^h$。
记 $p(z)=[u^1]A(z,u)$、$q(z)=[u^1]B(z,u)$，我们想要的是 $F(z)=\sum_{n\ge0}f(n)z^n=A(z,1)$，规定 $f(0)=0$。
依题意有 $A=zu(Z+A)+\frac{2z}{u}(A-up),B=zu(2Z+B)+\frac{2z}{u}(B-uq)$。根据 $Z$ 的定义有 $Z=1+2z(p+q)$。
将前两个方程稍作变形有 $(u-zu^2-2z)A=zu^2Z-2zup,(u-zu^2-2z)B=2zu^2Z-2zuq$。
取 $S(z)=\sqrt{1-8z^2},U(z)=\frac{1-\sqrt{1-8z^2}}{2z}=\frac{1-S(z)}{2z}$ 带入变形后的方程有 $p=\frac{UZ}{2},q=UZ$，再带入 $Z=1+2z(p+q)$ 有 $Z=\frac{2}{3S-1}$。
我们回到 $A$，令 $u=1$ 有 $F(z)=A(z,1)=\frac{1+4z-\sqrt{1-8z^2}}{4(1-9z^2)}$。
分母提示我们要分奇偶讨论，$n$ 为奇的情况平凡，考虑 $n$ 为偶。
我们令 $H(t)=\frac{1-\sqrt{1-8t}}{4t} =\sum_{m\ge0}b_mt^m$，容易发现 $f(2m)=9f(2m-2)+b_{m-1}$，因此我们只需要计算 $b$。
不妨施广义二项式定理，有 $b_m=-\frac14[t^{m+1}](1-8t)^{1/2}=-\frac14\binom{1/2}{m+1}(-8)^{m+1}=\frac{2^m}{m+1}\binom{2m}{m}$，容易设计其递推式：$b_0=1,b_m=\frac{4(2m-1)}{m+1}b_{m-1}$。
::::