BZOJ 5093[Lydsy1711月赛]图的价值线性做法

博主曾更过一篇复杂度为$O( k· \log k)$的多项式做法在这里

惊闻本题有$ O(k)$的神仙做法，说起神仙我就想起了于是就去学习了一波

幂与第二类斯特林数

推导看这里

$$ x^k=\sum_{j=0}^kj!\binom{x}{j}\begin{Bmatrix}k\\j\end{Bmatrix}$$

$$ \begin{Bmatrix}k\\j\end{Bmatrix}=\frac{1}{j!}\sum_{i=0}^ji^k\binom{j}{i}(-1)^{j-i}$$

以上是两个非常实用的公式

推式子

现在开始推式子

原博文已经推出了我们真正需要求的是$ f(n,k)=\sum\limits_{i=0}^n\binom{n}{i}i^k$

根据上面的公式可以推得

$$
\begin{aligned}
f(n,k) & =\sum_{i=0}^n\binom{n}{i}i^k=\sum_{j=0}\begin{Bmatrix}k\\j\end{Bmatrix}\frac{n!}{(n-j)!}2^{n-j}\\
& =\sum_{j=0}^k\frac{n!}{(n-j)!}2^{n-j}\frac{1}{j!}\sum_{i=0}^j(-1)^{j-i}\binom{j}{i}i^k\\
&=\sum_{j=0}^k\binom{n}{j}2^{n-j}\sum_{i=0}^j(-1)^{j-i}\binom{j}{i}i^k\\
&=\sum_{i=0}^k\binom{n}{i}i^k\sum_{j=i}^k2^{n-j}(-1)^{j-i}\binom{n-i}{j-i}\\
&=\sum_{i=0}^k\binom{n}{i}i^k2^{n-i}\sum_{j=0}^{k-i}\binom{n-i}{j}(-\frac{1}{2})^j
\end{aligned}
$$

我们需要快速递推出$A(i)=\displaystyle\sum_{j=0}^{k-i}\binom{n-i}{j}(-\frac{1}{2})^j$

再推波式子得

$$
\begin{aligned}
\sum_{j=0}^{k-i}\binom{n-i}{j}(-\frac{1}{2})^j&=\sum_{j=0}^{k-i}\left(\binom{n-i-1}{j}+\binom{n-i-1}{j-1}\right)(-\frac{1}{2})^j\\
&=\sum_{j=1}^{k-i}(-\frac{1}{2})^j\binom{n-i-1}{j-1}+\sum_{j=0}^{k-i}(-\frac{1}{2})^j\binom{n-i-1}{j}\\
&=-\frac{1}{2}\sum_{j=0}^{k-i-1}(-\frac{1}{2})^j\binom{n-i-1}{j}+\sum_{j=0}^{k-i}(-\frac{1}{2})^j\binom{n-i-1}{j}\\
&=\frac{1}{2}\sum_{j=0}^{k-i-1}(-\frac{1}{2})^j\binom{n-i-1}{j}+(-\frac{1}{2})^{k-i}\binom{n-i-1}{k-i}
\end{aligned}
$$

因此$A(i)=\frac{1}{2}A(i+1)+(-\frac{1}{2})^{k-i}\binom{n-i-1}{k-i}$

就假装推完了

大常数代码

#include<ctime>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<queue>

#define p 998244353

#define inv2 499122177

#define rt register int

#define ll long long

using namespace std;

inline ll read(){

    ll x = ; char zf = ; char ch = getchar();

    while (ch != '-' && !isdigit(ch)) ch = getchar();

    if (ch == '-') zf = -, ch = getchar();

    while (isdigit(ch)) x = x *  + ch - '', ch = getchar(); return x * zf;

}

void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}

void writeln(const ll y){write(y);putchar('\n');}

int i,j,k,m,n,x,y,z,cnt;

int ksm(int x,int y=p-){

    int ans=;

    for(rt i=y;i;i>>=,x=1ll*x*x%p)if(i&)ans=1ll*ans*x%p;

    return ans;

}

int inv[],A[];

int v[],ss[];bool b[];

int main(){

    n=read()-;k=read();

    inv[]=inv[]=;

    v[]=;v[]=(k==);

    for(rt i=;i<=k;i++){

        if(!b[i])ss[++cnt]=i,v[i]=ksm(i,k);

        for(rt j=;i*ss[j]<=k&&j<=cnt;j++){

            b[i*ss[j]]=;v[i*ss[j]]=1ll*v[i]*v[ss[j]]%p;

            if(i%ss[j]==)break;

        }

    }

    for(rt i=;i<=k;i++)inv[i]=1ll*inv[p%i]*(p-p/i)%p;

    int ans=;

    if(n<=k){

        for(rt i=,c=;i<=n;c=1ll*(n-i)*inv[i+]%p,i++)

        ans+=1ll*c*v[i]%p;

        cout<<(1ll*ans*(n+)%p*ksm(,(ll)n*(n-)/%(p-))%p+p)%p;

        return ;

    }

    A[k]=;

    for(rt i=k-,y=-inv2,c=n-i-;i>=;i--,y=1ll*y*-inv2%p){

        A[i]=(1ll*A[i+]*inv2%p+1ll*c*y%p)%p;

        c=1ll*c*(n-i)%p*inv[k-i+]%p;

    }

    for(rt i=,d=ksm(,n),c=;i<=k&&i<=n;c=1ll*c*(n-i)%p*inv[i+]%p,i++,d=1ll*d*inv2%p)

    (ans+=1ll*c*v[i]%p*d%p*A[i]%p)%=p;

    cout<<(1ll*ans*(n+)%p*ksm(,(ll)n*(n-)/%(p-))%p+p)%p;

    return ;

}

巴特西

BZOJ 5093[Lydsy1711月赛]图的价值线性做法

幂与第二类斯特林数

推式子

大常数代码

最新文章

热门文章

巴特西

BZOJ 5093[Lydsy1711月赛]图的价值 线性做法

幂与第二类斯特林数

推式子

大常数代码

最新文章

热门文章

BZOJ 5093[Lydsy1711月赛]图的价值线性做法