Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$，执行 $q$ 次操作分两种：

• = l r x：对每个 $l\le i\le r$ 执行 $a_i\leftarrow x$.
• ? l r k：求 $(\sum _{i=l}^r{a}_i\times (i-l+1{)}^k)\mathrm{mod}(10^9+7)$.

Limitations

$1\le n,q\le 10^5$
$1\le l\le r\le n$
$0\le a_i,x\le 10^9$
$0\le k\le 5$
$5\text{s},256\text{MB}$

Solution

直接维护答案式子是不大现实的.

考虑拆开，由二项式定理得：
$$\begin{array}{rl}\text{原式}& =\sum _{i=l}^r{a}_i\times (\sum _{j=0}^k(\genfrac{}{}{0ex}{}{k}{j})\times (i+1{)}^j\times (-l{)}^{k-j})\\ & =\sum _{j=0}^k\left(\genfrac{}{}{0ex}{}{k}{j}\right)\times (-l{)}^{k-j}\times (\sum _{i=l}^r{a}_i\times (i+1{)}^j)\end{array}$$

预处理 $\left(\genfrac{}{}{0ex}{}{k}{j}\right)$，线段树维护 $S=\sum _{i=l}^r{a}_i\times (i+1{)}^j$ 即可，剩下的查询时暴算.
时间复杂度 $O(kq\log n)$.

Submisson