自动搬运

查看原文

来自洛谷，原作者为

	Soulist 再见了

搬运于2025-08-24 22:11:17，当前版本为作者最后更新于2019-12-01 10:46:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这篇题解对于许多题解打表/一言概括得到的结论进行了充分的证明

我们将序列$a$看作一个$OGF$

$$F(x)=\sum_{i=0}^{\infty} a_i x^i$$

考虑计算前缀和，众所周知，只需要拿它乘以$G(x)=1+x^1+...+x^{\infty}$

根据一些等比数列求和的芝士我们知道$G(x)=\dfrac{1}{1-x}$

置于求它的差分，则拿$F$和$1-x$卷起来即可

好了那么$k$维前缀和呢？

$$F\times\dfrac{1}{(1-x)^k}$$

$k$维差分呢？

$$F\times (1-x)^k$$

好了然后求个$\ln$，乘个$k$，取个$\exp$这道题就做完了

但是非常不幸的是这样会非常难写而且我已经不会求$\ln$和$\exp$了（不要问我怎么清$0$，我也不会清$0$）

于是我们还是用点生成函数的技巧吧

首先是差分，它非常好做：

$$(1-x)^k$$

二项式定理强行打开使我们可以知道：

$$(1-x)^k=\sum_{i=0}^{\infty}(-1)^i\dbinom{k}{i}x^i$$

好的这道题真是见了鬼了$k$这么大搞什么。。。

不过这道题要用连续的组合数然而它可以递推

$\dbinom{k}{0}=1,\dbinom{k}{i}=\dbinom{k}{i-1}\times\dfrac{k-i+1}{i}$

然后大概$k$是可以直接取模的。。。

好了接下来是：

$$\dfrac{1}{(1-x)^k}$$

这个有点麻烦，需要借助广义二项式定理：

我们把它看作$(1-x)^{-k}$

根据广义二项式定理它等价于：

$$(1-x)^a=\sum_{i=0}^{\infty}\dbinom{a}{i}x^i$$

这个式子看上去挺对的。。。毕竟当$i>a$的时候$\dbinom{a}{i}=0..$不过现在我们不能用阶乘来定义组合数了，于是我们需要把它改成下降幂的形式：

$$\dbinom{a}{i}=\dfrac{a^{\underline{i}}}{i!}$$

注：$a^{\underline{i}}=a(a-1)(a-2)...(a-i+1)$

好的我们来看下$-k$代入进去是什么样的：

$$(1-x)^{-k}=\sum_{i=0}^{\infty}(-1)^i\dfrac{(-k)^{\underline{i}}}{i!}x^i $$$$(1-x)^{-k}=\sum_{i=0}^{\infty}(-1)^{2i}\dfrac{(k+i-1)^{\underline{i}}}{i!}x^i $$

所以我们知道：

$$(1-x)^{-k}=\sum_{i=0}^{\infty}\dbinom{k+i-1}{i}x^i $$

好了于是对于差分我们只需要拿$F$和$\sum_{i=0}^{\infty}(-1)^i\dbinom{k}{i}x^i$卷起来即可

对于前缀和我们只需要拿$F$和$\sum_{i=0}^{\infty}\dbinom{k+i-1}{i}x^i$卷起来即可

当然这个什么$\dbinom{k+i-1}{i}$也可以递推，因为它是$\dfrac{(k+i-1)^{\underline{i}}}{i!}$，要递推的话也很简单，每次乘一个$(k+i-1)/i$即可

然后模数还是$\text{NTT}$模数。。。

实际上这篇题解是在做一些特别蠢的证明。。。

$Code:$

#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
const int P = 1004535809 ;
const int Gi = 334845270 ; 
const int G = 3 ;
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = ( cn * 10 + cc - '0' ) % P, cc = getchar() ;
	return cn * flus ;
}
const int N = 1e5 + 5 ; 
int n, m, A[N << 2], B[N << 2], limit, L, Inv, R[N << 2] ; 
int fpow( int x, int k ) {
	int ans = 1, base = x ; 
	while( k ) {
		if( k & 1 ) ans = ( ans * base ) % P ; 
		base = ( base * base ) % P, k >>= 1 ; 
	} return ans ; 
}
void init( int x ) {
	limit = 1, L = 0 ; 
	while( limit <= x ) limit <<= 1, ++ L ; 
	rep( i, 0, limit ) R[i] = ( R[i >> 1] >> 1 ) | ( ( i & 1 ) << ( L - 1 ) ) ;
	Inv = fpow( limit, P - 2 ) ;
}
void NTT( int *a, int type ) {
	for( re int i = 0; i < limit; ++ i ) if( R[i] > i ) swap( a[i], a[R[i]] ) ;
	for( re int k = 1; k < limit; k <<= 1 ) {
		int d = fpow( ( type == 1 ) ? G : Gi, ( P - 1 ) / ( k << 1 ) ) ; 
		for( re int i = 0; i < limit; i += ( k << 1 ) ) 
		for( re int j = i, g = 1 ; j < i + k; ++ j, g = ( g * d ) % P ) {
			int Nx = a[j], Ny = ( a[j + k] * g ) % P ;
			a[j] = ( Nx + Ny ) % P, a[j + k] = ( Nx - Ny + P ) % P ; 
		} 
	}
	if( type != 1 ) rep( i, 0, limit ) a[i] = a[i] * Inv % P ; 
}
signed main()
{
	n = gi(), m = gi() ; int type = gi() ; 
	rep( i, 1, n ) A[i - 1] = gi() ; B[0] = 1 ; 
	if( type == 0 ) rep( i, 1, n ) B[i] = B[i - 1] * ( m + i - 1 ) % P * fpow( i, P - 2 ) % P ; 
	if( type == 1 ) rep( i, 1, n ) B[i] = ( -B[i - 1] * ( m - i + 1 + P ) % P * fpow( i, P - 2 ) % P + P ) % P ; 
	init( n + n ), NTT( A, 1 ), NTT( B, 1 ) ;
	rep( i, 0, limit ) A[i] = A[i] * B[i] % P ;
	NTT( A, -1 ) ; rep( i, 1, n ) printf("%lld ", A[i - 1] ) ;  
	return 0 ;
}