[HDU 3483] A Very Simple Problem 题解

标签：HDU limits Very 题解 sum binom

题目描述

快速求出下面式子的值：

\[\left(\sum\limits_{k=1}^{N}k^{x}x^{k}\right)\bmod M \]

其中 \(1 ≤ N, M ≤ 2\times 10^9\), 并且 \(1 ≤ x ≤ 50\)。

题解 (solution)

对于该类题目，\(N\) 很大，而 \(x\) 很小，考虑矩阵快速幂优化。
对于每一个 \(N\) 的答案，我们用 \(f(N)\) 来表示，于是有（忽略取模运算）：

\[f(n+1)=f(n)+(n+1)^{x}x^{n+1} \]

因为 \(x\) 很小，而我们所希望的递推式是不包含项数的，所以把 \((n+1)^{x}\) 用二项式定理暴力拆开，于是有：

\[f(n+1)=f(n)+x\sum\limits_{i=0}^{x}\binom{x}{i}n^{i}x^{n} \]

所以最后答案为：

\[\begin{align} f(n)&=x\sum\limits_{i=1}^{n}{\sum\limits_{j=0}^{x}\binom{x}{j}(i-1)^{j}x^{i-1}}\\ &=x\sum\limits_{i=0}^{n-1}{\sum\limits_{j=0}^{x}\binom{x}{j}i^{j}x^{i}}\\ &=x\sum\limits_{i=0}^{x}{\binom{x}{i}\sum\limits_{j=0}^{n-1}j^{i}x^{j}} \end{align} \]

观察到式子后面一坨与原式相似，于是定义 \(g(n,y)\) 表示 \(\sum\limits_{i=1}^{n}i^{y}x^{i}\)，则递推式为

\[g(n,y)=x\sum\limits_{i=0}^{y}\binom{y}{i}(g(n-1,i)+[i=0]) \]

直接矩阵快速幂求出 \(g(n,x)\) 即可，时间复杂度 \(\mathcal O(x^3\log n)\)。

标签：HDU,limits,Very,题解,sum,binom
From： https://www.cnblogs.com/cqbzljh/p/17790230.html