\(string\)
- 考试的时候只做了前面的 \(5\) 个 \(subtask\)
(其实都是一个做法),获得 \(53\) 分好成绩.
- 前面 \(5\) 个 \(subtask\) 都可以用 \(O(q\cdot|S|)\) 的做法.这个做法还是比较显然的,每次询问搞出 \(t\) ,那么相同的位置标记为 \(0\) ,不同的位置标记为 \(1\) ,相当于每次翻转一段区间,问变成全 \(0\) 的次数.
- 从两侧开始找,一段 \(0\) 就直接略去,一段 \(1\) 就翻转剩下的整个区间,同时记录一下翻转次数即可.
- 正解:???
\(sea\)
- 考试的时候写了 \(subtask\ 1,2,4,5\) ,获得 \(48\) 分好成绩.(大概?)想出了正确做法,时间原因,没有写.
- 这个题是在考查 必修5-数列 ?显然可以用上错位相减.
- 这里记 \(S(n,k)\) 表示 \(\sum_{i=1}^n i^k\cdot x^i\) , \(x=R\) ,为一常数.
\[
\begin{align*}
S(n,k)&=1^k\cdot x^1+2^k\cdot x^2+3^k\cdot x^3+\dots+n^k\cdot x^n\x\cdot S(n,k)&=0+1^k\cdot x^2+2^k\cdot x^3+3^k\cdot x^4+\dots+n^k\cdot x^{n+1}\S(n+1,k)&=1^k\cdot x^1+2^k\cdot x^2+3^k\cdot x^3+\dots+n^k\cdot x^n+(n+1)^{k}\cdot x^{n+1}\S(n+1,k)-x\cdot S(n,k)&=(1-x)\cdot S(n,k)+(n+1)^{k}\cdot x^{n+1}\&=1^k \cdot x^1+(2^k-1^k)\cdot x^2+\dots +[(n+1)^k-n^k] \cdot x^{n+1}.
\end{align*}
\]
- 得到:
\[
(1-x)\cdot S(n,k)+(n+1)^{k}\cdot x^{n+1}=1^k \cdot x^1+(2^k-1^k)\cdot x^2+\dots +[(n+1)^k-n^k] \cdot x^{n+1}.
\]
- 一时差分一时爽,一直差分一直爽,把右边的式子用插值搞成 \(S(n,k')\) 的组合,递归计算到 \(k=0\) 时用等比数列求和公式返回.
(纯属口胡)
test20190319
原文：https://www.cnblogs.com/jklover/p/10558230.html
