菜王的 blog

思路

简单数学。

首先，$a$ 的 $k$ 次前缀和之和肯定还是由若干个 $a_i$ 组成的，可以表示成这样：

$\sum_{i = 1}^n cnt_i a_i$

其中 $cnt_i$ 为 $a_i$ 在 $a$ 的 $k$ 次前缀和之和中出现的次数。

于是我们可以分别计算出每个 $cnt_i$，再与 $a_i$ 乘起来即可。

那 $cnt_i$ 怎么算呢？我们讨论一下 $n = 6$ 的情况。

$k = 1$：$\{6, 5, 4, 3, 2, 1\}$

$k = 2$：$\{21, 15, 10, 6, 3, 1\}$

可以发现一个规律：

$cnt_i = C_{k + n - i}^k$

到这里，我们就可以直接 $O(\log n)$ 求逆元，然后计算。

但是这题 $n \le 10^7$，我们需要一种线性算法来更快的计算逆元。

首先推一下柿子：

$C_n^m = \dfrac{n!}{m!(n - m)!}$

$C_{n + 1}^m = \dfrac{n! \times (n + 1)}{m!(n + 1 - m)!} = \dfrac{n!}{m!(n - m)!} \times \dfrac{n + 1}{n - m + 1}$

于是，我们就可以倒推 $cnt_i$，从 $cnt_i$ 推到 $cnt_{i - 1}$，每一次乘上 $\dfrac{k + n - i + 1}{n - i + 1}$。

线性递推 $[1, n]$ 的逆元，再递推 $cnt_i$，计算后输出即可。

upd：其实递推阶乘逆元也是可以的，想麻烦了

代码

#include <algorithm>
#include <cstdio>
#define mod 1000000007
#define ll long long
#define reg register

using namespace std;

int n, k, S;
ll a[10000001], inv[10000001], mul[10000001], ans;
namespace dataGen{ 
	int seed;
  	inline void init(int S){seed = S;}
  	inline int getNext(){return seed = (1ll * seed * 5 + 13) % mod;}
}
void read(){
  	scanf("%d%d%d", &n, &k, &S);
  	dataGen::init(S);
  	for (int i = 1;i <= n;i ++) a[i] = dataGen::getNext();
}
int main(){
	read();
	inv[1] = mul[1] = 1;
	for (reg int i = 2;i <= n;i ++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	for (reg int i = 2;i <= n;i ++) mul[i] = mul[i - 1] * (k + i - 1) % mod * inv[i - 1] % mod;
	for (reg int i = n;i >= 1;i --) ans = (ans + 1ll * a[i] * mul[n - i + 1]) % mod;
	printf("%d", ans);
}