题解 P5488 【差分与前缀和】

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

我们将序列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} $$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 ;
}