2020-08-06 14:49 已编辑武汉大学 C++

关注

浅谈下降幂

公式:

$x^{\underline k}=\frac{x!}{(x-k)!}$

$x^k=\sum_{i=0}^{k} \begin{Bmatrix}k\\i\end{Bmatrix} x^{\underline i}$

$\binom{n}{k} \times k^{\underline i}=\binom{n-i}{k-i} \times n^{\underline i}$

题目

P6620 [省选联考 2020 A 卷] 组合数问题

$\left(\sum_{k=0}^{n} f(k) \times x^{k} \times\left(\begin{array}{l}n \\ k\end{array}\right)\right) \bmod p$

题解

$=\sum_{k=0}^{n} \sum_{i=0}^{m} a_{i} k^{i} \times x^{k} \times\left(\begin{array}{l}n \\ k\end{array}\right)$

$=\sum_{k=0}^{n} \sum_{i=0}^{m} a_{i} \sum_{j=0}^{i} \begin{Bmatrix}i\\j\end{Bmatrix} k^{\underline j} \times x^{k} \times\left(\begin{array}{l}n \\ k\end{array}\right)$

$=\sum_{k=0}^{n} \sum_{i=0}^{m} \sum_{j=i}^{m} a_{j}\begin{Bmatrix}j\\i\end{Bmatrix} k^{\underline i} \times x^{k} \times\left(\begin{array}{l}n \\ k\end{array}\right)$

$令b_i=\sum_{j=i}^{m} a_{j}\begin{Bmatrix}j\\i\end{Bmatrix} k^{\underline i}$

$=\sum_{k=0}^{n} \sum_{i=0}^{m} b_{i} \times k^{\underline i} \times x^{k} \times\left(\begin{array}{l}n \\ k\end{array}\right)$

$=\sum_{i=0}^{m} b_{i} \times n^{i} \sum_{k=0}^{n}\left(\begin{array}{l}n-i \\ k-i\end{array}\right) x^{k}$

$不枚举k，改枚举k-i$

$=\sum_{i=0}^{m} b_{i} \times n^{\underline i} \sum_{k=0}^{n-i}\left(\begin{array}{c}n-i \\ k\end{array}\right) x^{k+i}$

$=\sum_{i=0}^{m} b_{i} \times n^{i} \times x^{i} \sum_{k=0}^{n-i}\left(\begin{array}{c}n-i \\ k\end{array}\right) x^{k}$

$=\sum_{i=0}^{m} b_{i} \times n^{i} \times x^{i} \sum_{k=0}^{n-i}\left(\begin{array}{c}n-i \\ k\end{array}\right) x^{k} \times 1^{n-i-k}$

$=\sum_{i=0}^{m} b_{i} \times n^{i} \times x^{i}\times (x+1)^{n-i}$

代码

#include<bits/stdc++.h>
using namespace std;
#define next Nxt
#define last Lst
#define gc getchar
#define int long long
const int N=1005;
int n,m,mod,ans,x,a[N],b[N],c[N],d[N],e[N],s[N][N];
//char buf[1<<21],*p1=buf,*p2=buf;
//inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
int kuai(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b=b/2;
    }
    return res;
}
int work(int x)
{
    int res=1;
    for(int i=n-x+1;i<=n;i++)res=res*i%mod;
    return res;
}
int work2(int x)
{
    int res=0;
    for(int i=x;i<=m;i++)res=(res+a[i]*s[i][x])%mod;
    return res;
}
signed main()
{
    n=read();x=read();mod=read();m=read();
    for(int i=0;i<=m;i++)a[i]=read();
    for(int i=0;i<=m;i++)e[i]=work(i);
    s[0][0]=1;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++)
            s[i][j]=(s[i-1][j-1]+s[i-1][j]*j)%mod;
    for(int i=0;i<=m;i++)b[i]=work2(i);
    c[0]=1;
    for(int i=1;i<=m;i++)c[i]=c[i-1]*x%mod;
    for(int i=0;i<=m;i++)d[i]=kuai((x+1)%mod,n-i);
    for(int i=0;i<=m;i++)
        ans=(ans+e[i]*b[i]%mod*c[i]%mod*d[i]%mod)%mod;
    cout<<ans;
    return 0;
}

题目

P6667 [清华集训2016] 如何优雅地求和

$Q(f, n, x)=\sum_{k=0}^{n} f(k)\left(\begin{array}{l}n \\ k\end{array}\right) x^{k}(1-x)^{n-k}$

题解

$=\sum_{k=0}^{n} \sum_{i=0}^{m} a_{i} k^{i} \times x^{k} \times\left(\begin{array}{l}n \\ k\end{array}\right) \times (1-x)^{n-k}$

$=\sum_{k=0}^{n} \sum_{i=0}^{m} a_{i} \sum_{j=0}^{i} \begin{Bmatrix}i\\j\end{Bmatrix} k^{\underline j} \times x^{k} \times\left(\begin{array}{l}n \\ k\end{array}\right)\times (1-x)^{n-k}$

$=\sum_{k=0}^{n} \sum_{i=0}^{m} \sum_{j=i}^{m} a_{j}\begin{Bmatrix}j\\i\end{Bmatrix} k^{\underline i} \times x^{k} \times\left(\begin{array}{l}n \\ k\end{array}\right)\times (1-x)^{n-k}$

$令b_i=\sum_{j=i}^{m} a_{j}\begin{Bmatrix}j\\i\end{Bmatrix} k^{\underline i}$

$=\sum_{k=0}^{n} \sum_{i=0}^{m} b_{i} \times k^{\underline i} \times x^{k} \times\left(\begin{array}{l}n \\ k\end{array}\right)\times (1-x)^{n-k}$

$=\sum_{i=0}^{m} b_{i} \times n^{i} \sum_{k=0}^{n}\left(\begin{array}{l}n-i \\ k-i\end{array}\right) x^{k}\times (1-x)^{n-k}$

$不枚举k，改枚举k-i$

$=\sum_{i=0}^{m} b_{i} \times n^{\underline i} \sum_{k=0}^{n-i}\left(\begin{array}{c}n-i \\ k\end{array}\right) x^{k+i}\times (1-x)^{n-k-i}$

$=\sum_{i=0}^{m} b_{i} \times n^{i} \times x^{i} \sum_{k=0}^{n-i}\left(\begin{array}{c}n-i \\ k\end{array}\right) x^{k}\times (1-x)^{n-k-i}$

$=\sum_{i=0}^{m} b_{i} \times n^{i} \times x^{i}\times (x+(1-x))^{n-i}$

$=\sum_{i=0}^{m} b_{i} \times n^{i} \times x^{i}\times 1^{n-i}$

出题人毒瘤， $f(k)$ 是以点值的形式给出，我们要转化为 $f(k)=\sum_{i=0}^{m} a_i\times k^i$ 的形式。

这就是多项式插值，我们可以用 $n^2$ 的拉格朗日插值来解决，具体就是

对于 $f(k)=\sum_{i=0}^{n} y_{i} \prod_{i \neq j} \frac{k-x[j]}{x[i]-x[j]}$ ，把 $k$ 当成未知数，求出这个多项式每一项的系数。

代码

#include<bits/stdc++.h>
using namespace std;
#define next Nxt
#define last Lst
//#define gc getchar
//#define int long long
const int N=20005;
const int mod=998244353;
int n,m,ans,len,x,y[N],inv[N],f[N],a[N],b[N],c[N],d[N],e[N],s[2][N];
char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
int kuai(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b=b/2;
    }
    return res;
}
int work(int x)
{
    int res=1;
    for(int i=n-x+1;i<=n;i++)res=1ll*res*i%mod;
    return res;
}
void solve(int x)
{
    for(int i=0;i<=len;i++)c[i]=a[i];
    for(int i=len;i;i--)
    {
        b[i-1]=c[i];
        c[i-1]=(c[i-1]+1ll*c[i]*x%mod+mod)%mod;
    }
}
signed main()
{
    n=read();m=read();x=read();
    for(int i=0;i<=m;i++)y[i]=read();
    a[1]=1;
    len=1;
    for(int i=1;i<=m;i++)
    {
        b[0]=0;
        for(int j=0;j<=len;j++)
            b[j+1]=a[j];
        for(int j=0;j<=len;j++)
            b[j]=(b[j]-1ll*a[j]*i%mod+mod)%mod;
        len++;
        for(int j=0;j<=len;j++)a[j]=b[j];
    }
    for(int i=0;i<=m;i++)
    {
        inv[i]=1;
        for(int j=0;j<=m;j++)
            if(i!=j)inv[i]=1ll*inv[i]*(i-j)%mod;
        inv[i]=(inv[i]+mod)%mod;
        inv[i]=kuai(inv[i],mod-2);
    }
    for(int i=0;i<=m;i++)
    {
        solve(i);
        for(int j=0;j<len;j++)
            f[j]=(f[j]+1ll*b[j]*y[i]%mod*inv[i]%mod)%mod;
    }
    for(int i=0;i<=m;i++)a[i]=f[i];
    for(int i=0;i<=m;i++)e[i]=work(i);
    for(int i=0;i<=m;i++)b[i]=0;
    s[0][0]=1;
    b[0]=a[0];
    for(int i=1;i<=m;i++)
    {
        int u=i&1,v=(i-1)&1;
        if(i>1)s[0][0]=0;
        for(int j=1;j<=m;j++)
            s[u][j]=(s[v][j-1]+1ll*s[v][j]*j)%mod;
        for(int j=0;j<=i;j++)b[j]=(b[j]+1ll*a[i]*s[u][j])%mod;
    }
    c[0]=1;
    for(int i=1;i<=m;i++)c[i]=1ll*c[i-1]*x%mod;
    for(int i=0;i<=m;i++)
        ans=(ans+1ll*b[i]*c[i]%mod*e[i]%mod)%mod;
    cout<<ans;
    return 0;
}

题目

#1305. 数

$\begin{aligned} f_{0} &=1 \\ f_{i} &=\left(\left(b_{i} \times\left(\sum_{j=0}^{i-1} f_{j} \times F(i-j)\right)\right) \bmod P\right) \text { xor } c_{i} \end{aligned}$