【P5488 差分与前缀和】—Monkey can‘t understands this solution

· · 题解

P5488 差分与前缀和 题解

标签： 多项式

前言

一个牛顿二项式定理的应用，掌握好这个题目对组合数学有一定的帮助。

自认为是特别详细了。

前置知识

1、牛顿二项式定理(加个正号防止有歧义)。

(1+x)^{\alpha}=\sum_{i=0}^{\infty}\binom{\alpha}{i}(+x)^i \binom{n}{m}=\frac{n^{\underline{m}}}{m!}=\frac{\frac{n!}{(n-m)!}}{m!}

2、NTT。

3、生成函数（会封闭形式）。

4、n 阶前缀和以及 n 阶差分。

举个例子： 1 阶前缀和是我们所熟知的一维前缀和， 2 阶前缀和就是 1 阶前缀和的前缀和，依次类推，n 阶前缀和是 n-1 阶前缀和的前缀和，差分同理可得。

思路

首先，众所周知的是，将要求前缀和的序列的值依次代到 F(x) 的系数中去，通过与 G(x)=\sum_{i=0}^{\infty}x^i 相乘，可以得到序列的前缀和（我一般习惯从 1 开始代入）。

先从前缀和开始讲起：

设 F(x) 为当前已经代入了系数的多项式，与 G(x) （意义同上） 相乘得到：

F(x)\times G(x)=F(x)\times\sum_{i=0}^{\infty}x^i =F(x)\times \frac{1}{1-x}

那么每一项的系数就是序列从 1 …i 的 1 阶前缀和啦。

至于 k 阶前缀和，即要对初始的多项式做 k 次同样的操作，也就是下面的式子。

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

通过牛顿二项式定理把这个式子给拆开。

F(x)\times (\frac{1}{1-x})^k=F(x)\times (1-x)^{-k} =F(x)\times \sum_{i=0}^{\infty}\binom{-k}{i}(-x)^i =F(x)\times \sum_{i=0}^{\infty}(-1)^i\frac{\frac{(-k)!}{(-k-i)!}}{i!}x^i =F(x)\times \sum_{i=0}^{\infty}(-1)^i\frac{(-k-i+1)(-k-i+2)(-k-i+3)…(-k)}{i!}x^i

在这里需要说一下的是,上面坟墓上，当枚举到 i 的时候，上面一共有 i 个数，也就是奇数时有奇数个，偶数时有偶数个，分两种情况讨论一下:

1、当为奇数个的时候，上面的式子一看每一项一定是负数 (k>0) 的，奇数的时候提出奇数个负号来，所以上面还带着一个负号没有消去，而此时，(-1)^i=-1 负号全部消掉，变为正的。

2、当为偶数个的时候，上面可以提出偶数个负号来，全部消掉，而此时 (-1)^i=1 忽略不管。

通过上面的讨论可以得到的是：

=F(x) \times \sum_{i=0}^{\infty}\frac{(k+i-1)(k+i-2)…[k+i-(i-1)]k}{i!}x^i =F(x) \times \sum_{i=0}^{\infty}\frac{\frac{(k+i-1)!}{(k+i-1-i)!}}{i!}x^i =F(x) \times \sum_{i=0}^{\infty}\binom{k+i-1}{i}x^{i}

由此可以得到最终式子，由于 k 过大，肯定不可以直接算出来，所以要考虑递推求解啦，顺便把递推式扔在下面：

\binom{k-1}{0}=1 \binom{k}{1}=\frac{k!}{(k-1)!}=k \binom{k+1}{2}=\frac{(k+1)!}{2!(k-1)!}=\frac{k(k+1)}{2} \binom{k+2}{3}=\frac{(k+2)!}{3!(k-1)!}=\frac{k(k+1)(k+2)}{2\times 3}

由此可以得到：

\binom{k+i-1}{i}=\binom{k+i-2}{i-2}\times \frac{k+i-1}{i}

式子和递推式都推出来了，猴子应该也会做了，一边裸的 \text{NTT} 就可以了。

接下来看差分，既然前缀和是 \dfrac{1}{1-x}，那么差分就是 (1-x) 啦。

差分其实和前缀和差不多，不过还是来详细推导一下公式吧。

F(x)\times (1-x)^k=F(x)\times \sum_{i=0}^{\infty} \binom{k}{i}(-x)^i =F(x)\times \sum_{i=0}^{\infty}(-1)^i \binom{k}{i}\ x^i

已经化为最简形式了，所以最后再扔一个递推式验算过程：

\binom{k}{0}=1 \binom{k}{1}=\frac{k!}{(k-1)!}=k \binom{k}{2}=\frac{k!}{2!(k-2)!}=\frac{k(k-1)}{2} \binom{k}{3}=\frac{k!}{3!(k-3)!}=\frac{k(k-1)(k-2)}{2\times 3} \binom{k}{i}=\binom{k}{i-1}\times \frac{(k-i+1)}{i}

最后，这个题就圆满结束啦！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#define int long long 
using namespace std;
const int N=4e5+9;
const int mod=1004535809;
const int g[]={3,334845270};
int a[N],b[N];
int r[N];
int term=1,l;
int n,k,t;
int inv[N];
int read()//快读要经过模处理
{
    int f=1,x=0;
    char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=((x<<1)+(x<<3)+(s^'0'))%mod;s=getchar();}
    return f*x%mod;
}
int quick(int x,int p)
{
    int ret=1;
    while(p)
    {
        if(p&1) ret=ret*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return ret%mod;
}
void NTT(int *A,int type)
{
    for(int i=0;i<term;i++)
        if(i<r[i])
            swap(A[i],A[r[i]]);
    for(int mid=1;mid<term;mid<<=1)
    {
        int R=mid<<1;
        int Wn=quick(g[type],(mod-1)/R);
        for(int j=0;j<term;j+=R)
        {
            int w=1;
            for(int k=0;k<mid;k++,w=w*Wn%mod)
            {
                int x=A[j+k]%mod;
                int y=w*A[j+k+mid]%mod;
                A[j+k]=(x+y)%mod;
                A[j+k+mid]=(x-y+mod)%mod;
            }
        }   
    }
    if(type==1)
    {
        int inv=quick(term,mod-2);
        for(int i=0;i<term;i++)
            A[i]=A[i]*inv%mod; 
    }
    return;
}
void less_than_break()()//差分
{
    b[0]=1;
    inv[1]=1;
    for(int i=2;i<=n;i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=n;i++)
        b[i]=-b[i-1]*(k-i+1+mod)%mod*inv[i]%mod;
    NTT(a,0);
    NTT(b,0);
    for(int i=0;i<term;i++)
        a[i]=a[i]*b[i]%mod;
    NTT(a,1);
    for(int i=1;i<=n;i++)
        printf("%lld ",a[i-1]);
}
void frontsum()//前缀和
{
    b[0]=1;
    inv[1]=1;
    for(int i=2;i<=n;i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=n;i++)
        b[i]=b[i-1]*(k+i-1)%mod*inv[i]%mod;
    NTT(a,0);
    NTT(b,0);
    for(int i=0;i<term;i++)
        a[i]=a[i]*b[i]%mod;
    NTT(a,1);
    for(int i=1;i<=n;i++)
        printf("%lld ",a[i-1]);
}
signed main()
{
    n=read();
    k=read();
    t=read();
    for(int i=1;i<=n;i++)
        a[i-1]=read();
    while(term<=2*n)
    {
        term<<=1;
        l++;
    }
    for(int i=0;i<term;i++)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    if(t==1) less_than_break();
    else frontsum();
    return 0;
}