CF1278F Cards

利用组合意义 DP。或者利用斯特林数推式子可以做到更优。

注意到 $x^k$ 不好处理，我们容易想到进行转化。

组合意义DP

换一种思考方式，考虑 $x^k$ 的组合意义，即从第 $i$ 次王牌翻出王牌的方案所构成的集合中选 $k$ 次的方案数。 这只与不同的 $i$ 相关。我们可以通过 DP 求出 $s(x,y)$ 表示选了 $x$ 个，有 $y$ 种不同的 $i$ 的方案数，最后乘上 $\frac{1}{m^y}$ 的系数统计答案即可。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=5e3+10,mod=998244353;
int n,m,k;
int s[N][N];
inline int adj(int x){return x>=mod?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
    int res=1;
    while(k)
    {
        if(k&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    s[0][0]=1;
    for(int i=1;i<=k;i++)
        for(int j=1;j<=i;j++)
            s[i][j]=adj(1ll*j*s[i-1][j]%mod+1ll*s[i-1][j-1]*(n-j+1)%mod);
    m=qpow(m);
    int ans=0;
    for(int i=1,res=m;i<=k;i++,res=1ll*res*m%mod)
        ans=adj(ans+1ll*res*s[k][i]%mod);
    printf("%d\n",ans);
    return 0;
}

斯特林数

注意到 $x^k$ 的形式，利用经典套路，即斯特林数数转下降幂的技巧进行处理。设 $p=\frac{1}{m},q=1-p$，将朴素的式子列出来，并进行推导：

$$\begin{align} &\sum_{i=0}^n \binom{n}{i}p^i q^{n-i}i^k\\ =&\sum_{i=0}^n \binom{n}{i}p^i q^{n-i}\sum_{j=0}^k {k \brace j}i^{\underline j}\notag\\ =&\sum_{j=0}^k {k \brace j}\sum_{i=0}^n \binom{n}{i}p^i q^{n-i}i^{\underline j}\notag\\ =&\sum_{j=0}^k{k \brace j} \cdot j!\sum_{i=0}^n \binom{i}{j}\binom{n}{i}p^i q^{n-i}\notag\\ =&\sum_{j=0}^k{k \brace j} \cdot n^{\underline j}\sum_{i=j}^n \binom{n-j}{i-j}p^i q^{n-i}\notag\\ =&\sum_{j=0}^k{k \brace j} \cdot n^{\underline j}\sum_{i=0}^{n-j} \binom{n-j}{i}p^{i+j} q^{n-j-i}\notag\\ =&\sum_{j=0}^k{k \brace j} \cdot n^{\underline j} p^j\sum_{i=0}^{n-j}\binom{n-j}{i}p^{i} q^{n-j-i}\notag\\ =&\sum_{j=0}^k{k \brace j} \cdot n^{\underline j} p^j\notag\\ \end{align}$$

暴力做是 $\mathcal O(k^2)$ 的。同一行斯特林数可以通过其通项公式 $\displaystyle {n \brace k}=\sum_{i=0}^n \frac{i^n}{i!}\frac{(-1)^{k-i}}{(k-i)!}$ 卷积计算，时间复杂度 $\mathcal O(k\log k)$。

考虑更优的做法，我们直接将通项公式带入其中， 再推一下：

$$\begin{align} &\sum_{j=0}^k{k \brace j} \cdot n^{\underline j} p^j\notag\\ =&\sum_{j=0}^k n^{\underline j} p^j\sum_{i=0}^k (-1)^{j-i} \frac{i^k}{i!(j-i)!}\notag\\ =&\sum_{j=0}^k j!\binom{n}{j} p^j\sum_{i=0}^k (-1)^{j-i}i^k \frac{1}{j!}\binom{j}{i}\notag\\ =&\sum_{j=0}^k p^j\sum_{i=0}^k (-1)^{j-i}i^k\binom{n}{j} \binom{j}{i}\notag\\ =&\sum_{j=0}^k p^j\sum_{i=0}^k (-1)^{j-i}i^k\binom{n-i}{j-i} \binom{n}{i}\notag\\ =&\sum_{i=0}^k i^k \binom{n}{i} \sum_{j=i}^k p^j(-1)^{j-i}\binom{n-i}{j-i}\notag\\ =&\sum_{i=0}^k i^k p^i \binom{n}{i} \sum_{j=0}^{k-i} (-p)^j \binom{n-i}{j}\notag\\ \end{align}$$

考虑求出 $\displaystyle \sum_{j=0}^{k-i} (-p)^j \binom{n-i}{j}$ 只与 $i$ 有关，考虑求出其通项公式。。设 $\displaystyle f(i)=\displaystyle \sum_{j=0}^{k-i} (-p)^j \binom{n-i}{j}$。暴力拆开组合数也可以，这里是构造出组合数递推的形式，即 $\displaystyle \binom{n-i}{j}=\binom{n-i-1}{j-1}+\binom{n-i-1}{j-1}$。那么 $\displaystyle f(i+1)=\sum_{j=0}^{k-i-1} (-p)^j \binom{n-i-1}{j}$，对其进行一些推导：

$$\begin{align} -p\cdot f(i+1)&=-p\cdot \sum_{j=0}^{k-i-1} (-p)^j\binom{n-i-1}{j}\notag\\ &=\sum_{j=1}^{k-i} (-p)^{j}\binom{n-i-1}{j-1}\notag\\ &=\sum_{j=1}^{k-i-1} (-p)^{j}\binom{n-i-1}{j-1}+(-p)^{k-i}\binom{n-i-1}{k-i-1} \\ f(i+1)&=\sum_{j=0}^{k-i-1} (-p)^j\binom{n-i-1}{j} \end{align}$$

$(2)$ 式与 $(3)$ 式相加得到：

$$\begin{align} (1-p)\cdot f(i+1) &=\sum_{j=1}^{k-i-1} (-p)^j(\binom{n-i-1}{j-1}+\binom{n-i-1}{j})+1+(-p)^{k-i}\binom{n-i-1}{k-i-1} \notag\\ &=\sum_{j=0}^{k-i-1} (-p)^j\binom{n-i}{j}+(-p)^{k-i}\binom{n-i-1}{k-i-1} \notag\\ &=\sum_{j=0}^{k-i} (-p)^j\binom{n-i}{j}-(-p)^{k-i}\binom{n-i}{k-i}+(-p)^{k-i}\binom{n-i-1}{k-i-1} \notag\\ &=f(i)-(-p)^{k-i}(\binom{n-i}{k-i}-\binom{n-i-1}{k-i-1}) \notag\\ &=f(i)-(-p)^{k-i}\binom{n-i-1}{k-i} \notag\\ \end{align}$$

所以得到最终的递推式：

$$f(i)=(1-p)\cdot f(i+1)+(-p)^{k-i}\binom{n-i-1}{k-i}$$

其边界为 $f(k)=1$。对于 $n\le k$ 的情况直接用 $(1)$ 式暴力计算即可。 总的时间复杂度可以做到 $\mathcal O(k)$。

注意需要特判 $m=1$ 的情况下，此时 $q=0$ 不存在逆元。

Code

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e7+10,mod=998244353;
int n,k;
int cnt,prime[N];
bool vis[N];
int p,q,invp,invq;
int inv[N],pw[N];
int f[N];

inline int adj(int x){return x>=mod?x-mod:x;}
inline int qpow(int x,int k=mod-2)
{
    int res=1;
    while(k)
    {
        if(k&1)res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        k>>=1;
    }
    return res;
}
inline void sieve(int n)
{
    pw[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            prime[++cnt]=i;
            pw[i]=qpow(i,k);
        }
        for(int j=1;j<=cnt&&1ll*i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=1;
            pw[i*prime[j]]=1ll*pw[i]*pw[prime[j]]%mod;
            if(!(i%prime[j]))break;
        }
    }
}
void solve1()
{
    int res=qpow(q,n),ans=0;
    for(int i=1;i<=n;i++)
    {
        res=1ll*res*(n-i+1)%mod*inv[i]%mod*p%mod*invq%mod;
        ans=adj(ans+1ll*res*pw[i]%mod);
    }
    printf("%d\n",ans);
}
void solve2()
{
    int res=1,ans=0;
    f[k]=1;
    for(int i=k-1;i;i--)
    {
        res=1ll*res*(n-i-1)%mod*inv[k-i]%mod*(mod-p)%mod;
        f[i]=adj(1ll*(mod+1-p)*f[i+1]%mod+res);
    }
    res=1;
    for(int i=1;i<=k;i++)
    {
        res=1ll*res*(n-i+1)%mod*inv[i]%mod*p%mod;
        ans=adj(ans+1ll*res*pw[i]%mod*f[i]%mod);
    }
    printf("%d\n",ans);
}
void prework(int n)
{
    p=qpow(invp);
    q=mod+1-p;
    invq=qpow(q);
    inv[1]=1;
    for(int i=2;i<=n;i++)inv[i]=1ll*(mod-(mod/i))*inv[mod%i]%mod;
    sieve(n);
}
int main()
{
    scanf("%d%d%d",&n,&invp,&k);
    if(invp==1)return printf("%d\n",qpow(n,k)),0;
    prework(k);
    if(n<=k)solve1();
    else solve2();
    return 0;
}