Day 1
8+100+50，rk13。
打成螳臂了/ll
T1
小 H 有一个长度为 \(n\) 的树状数组 \(a\)，下标为 \(1 \sim n\)，初始时所有元素都为 \(0\)。定义一次更新操作 \(f(i, v)\) 为：
- 将 \(a_i\) 的值加上 \(v\)；
- 将 \(i\) 赋值为 \(i + lowbit(i)\)，如果此时 \(i \le n\) 则回到第一步，否则结束操作。
其中 \(lowbit(x)\) 为 \(x\) 二进制下最低位的 \(1\) 所代表的数，例如 \(lowbit(12) = 4\)。
现在小 H 进行了 \(m\) 次操作，每次操作会在 \([1, n]\) 间随机选择一个整数 \(i\)，在 \([0, S]\) 间随机选择一个整数 \(v\)，然后执行操作 \(f(i, v)\)。
小 H 想知道在进行完所有操作后，\(\sum_{i=1}^{n} a_i^k\) 的期望是多少，答案对 \(10^9 + 7\) 取模。
注意，本题中我们认为 \(0^0 = 1\)。
\(1\le n\le 10^9,0\le S,m\le 10^9,0\le k\le 1000\)。
马修出的题，%%%
对不起但是我声称我的确没时间做了（
这里给出 \(O(k^2+k\log n)\) 做法，不过主要并非我想的。
期望的线性性拆开，枚举一个位置 \(t\in [1,n]\) 的 lowbit 为 \(2^i\)，再枚举其被操作的次数为 \(c\)。令 \(p=\frac{2^i}{n}\)，则 \(Ans=\sum\limits_{i}(\lfloor \frac{n-2^i}{2^{i+1}}\rfloor+1)\sum\limits_{c}\binom{m}{c}p^c(1-p)^{m-c}(f_c\frac{1}{(S+1)^{c}})\)。这里 \(f_c\) 的含义即一个位置被操作 \(c\) 次的总贡献。
更进一步地，\(f_c=\sum\limits_{p\in [0,S]^c}(\sum\limits_{j=1}^{c}p_j)^k\)。将括号拆开，每个括号内选择一个 \(p\) 相乘再求和。所以若这里令 \(g_x\) 为恰好选择了 \(x\) 种 \(p\) 的乘积的和，则 \(f_c=\sum_{x}\binom{c}{x}g_x(S+1)^{c-x}\)。
注意到当 \(x>k\) 时，\(g_x=0\)。所以我们就可以将任意 \(f\) 转为 \(x\le k\) 的 \(g_x\)，即 \(f_c=\sum\limits_{x=1}^{k}\binom{c}{x}g_x(S+1)^{c-x}\)。
如果我们能求出 \(c\le k\) 的 \(f\)，就可以通过递推求出所有 \(g\)。而后将 \(Ans\) 求解式的 \(f\) 代换后的求解复杂度为 \(O(k\log n)\)，不是瓶颈。
接下来是重点。先用斯特林数将 \(x^k\) 拆成下降幂，于是我们相当于要对每一个 \(c,i\in [0,k]\) 求出 \(\sum\limits_{p\in [0,S]^c}\dbinom{\sum\limits_{j=1}^{c}p_j}{i}\)。
等价于 \(\sum\limits_{p\in [0,S]^c}[x^i](1+x)^{\sum\limits_{j=1}^{c}p_j}\)
\(=[x^i](\sum\limits_{j=0}^{S}(1+x)^j)^c\)
\(=[x^{i+c}]((1+x)^{S+1}-1)^c\)
记 \(f_c(x)=[(1+x)^{S+1}-1]^c\)，则我们要对所有 \(c\in [0,k]\) 的 \(f_c(x)\) 求出其前 \(O(k)\) 项系数。
形式并非很复杂，那么就开导吧！
两边提取系数就可以做到 \(O(k^2)\) 递推啦！
T2
根号分治做完了。
T3
提答？不想补。