对于这一题，我们有 $\Theta((k\log k+\log m)\log n)$ 的做法。

对于 $i\in[1,n]$，显然当且仅当 $x\in(i-\mathrm{lowbit}(i),i]$ 时，

$v$ 会对 $c_i$ 产生贡献。

设 $\mathrm{cnt}_i=\displaystyle\sum_{j=1}^n[\mathrm{lowbit}(j)=i]$，显然 $\mathrm{cnt}_i=\left\lfloor\dfrac{n-i}{2i}\right\rfloor+1\quad(i\le n)$

因此答案即为

$$\sum_i\dfrac{\mathrm{cnt}_i}{n^m}\sum_{j=0}^m\dbinom{m}{j}i^j(n-i)^{m-j}(S+1)^{-j}\sum_{a_1,a_2,\cdots,a_j\in[0,S]}\left(\sum_{u=1}^ja_u\right)^k$$

• $\dfrac{1}{n^m}\dbinom{m}{j}i^j(n-i)^{m-j}$ 表示 $m$ 次中有 $j$ 次产生了贡献。
• $\displaystyle (S+1)^{-j}\sum_{a_1,a_2,\cdots a_j\in[0,S]}\left(\sum_{u=1}^ja_u\right)^k$ 表示枚举贡献。

右边的 $k$ 次方不好搞，转为牛顿级数：

$$\sum_{a_1,a_2,\cdots,a_j\in[0,S]}\left(\sum_{u=1}^ja_u\right)^k=\sum_{r=0}^k{k\brace r}r!\sum_{a_1,a_2,\cdots,a_j\in[0,S]}\dbinom{a_1+a_2+\cdots+a_j}{r}$$

此时可以范特蒙德卷积

$$\dbinom{a_1+a_2+\cdots+a_j}{r}=\sum_{\sum_{u=1}^jb_u=r}\prod_{u=1}^j\dbinom{a_u}{b_u}$$

调换枚举顺序，发现可以上指标求和

$$\sum_{a_1,a_2,\cdots,a_j\in[0,S]}\dbinom{a_1+a_2+\cdots+a_j}{r}=\sum_{\sum_{u=1}^jb_u=r}\prod_{u=1}^j\sum_{a_u=0}^S\dbinom{a_u}{b_u}$$

$$=\sum_{\sum_{u=1}^jb_u=r}\prod_{u=1}^j\dbinom{S+1}{b_u+1}$$

因此设 $f(x)=\displaystyle\sum_{v=0}^{\infty}\dbinom{S+1}{v+1}x^v$，则

$$\sum_{a_1,a_2,\cdots,a_j\in[0,S]}\dbinom{a_1+a_2+\cdots+a_j}{r}=[x^r]f^j(x)$$

于是最终的答案就是

$$\sum_i\dfrac{\mathrm{cnt}_i}{n^m}\sum_{r=0}^k{k\brace r}r![x^r]\sum_{j=0}^m\dbinom{m}{j}i^j(n-i)^{m-j}(S+1)^{-j}f^j(x)$$

$$=\sum_i\dfrac{\mathrm{cnt}_i}{n^m}\sum_{r=0}^k{k\brace r}r![x^r]\left(\dfrac{if(x)}{S+1}+n-i\right)^m$$

$[x^r]\left(\dfrac{if(x)}{S+1}+n-i\right)^m$ 多项式快速幂即可 $\Theta(k\log k+\log m)$。

因此最终复杂度为 $\Theta((k\log k+\log m)\log n)$。

当然如果不想写任意模数 NTT 的话 $\Theta(k^2\log n\log m)$ 也可以...