• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

[CF1278F] Cards 加强版

2周前 (04-29) 6次浏览

(text{Problem}:)CF1278F Cards 加强版

(text{Solution}:)

(p=frac{1}{m})，要求的是：

[sumlimits_{i=0}^{n}binom{n}{i}p^{i}(1-p)^{n-i}i^{k}
]

(i^{k}) 利用第二类斯特林数展开，有：

[begin{aligned}
ans&=sumlimits_{i=0}^{n}binom{n}{i}p^{i}(1-p)^{n-i}sumlimits_{j=0}^{k}{kbrace j}i^{underline{j}}\
&=sumlimits_{j=0}^{k}{kbrace j}sumlimits_{i=j}^{n}i^{underline{j}}binom{n}{i}p^{i}(1-p)^{n-i}\
&=sumlimits_{j=0}^{k}{kbrace j}sumlimits_{i=j}^{n}binom{n-j}{i-j}n^{underline{j}}p^{i}(1-p)^{n-i}\
&=sumlimits_{j=0}^{k}{kbrace j}n^{underline{j}}p^{j}sumlimits_{i=0}^{n-j}binom{n-j}{i}p^{i}(1-p)^{n-i-j}\
&=sumlimits_{j=0}^{k}{kbrace j}n^{underline{j}}p^{j}
end{aligned}
]

[begin{aligned}
ans&=sumlimits_{j=0}^{k}p^{j}binom{n}{j}j!sumlimits_{i=0}^{j}frac{(-1)^{j-i}i^{k}}{i!(j-i)!}\
&=sumlimits_{j=0}^{k}p^{j}binom{n}{j}sumlimits_{i=0}^{j}binom{j}{i}(-1)^{j-i}i^{k}\
&=sumlimits_{i=0}^{k}i^{k}sumlimits_{j=i}^{k}p^{j}binom{n}{j}(-1)^{j-i}binom{j}{i}\
&=sumlimits_{i=0}^{k}i^{k}(-1)^{-i}sumlimits_{j=i}^{k}(-p)^{j}binom{n}{j}binom{j}{i}\
&=sumlimits_{i=0}^{k}i^{k}(-1)^{i}sumlimits_{j=i}^{k}(-p)^{j}binom{n-i}{j-i}binom{n}{i}\
&=sumlimits_{i=0}^{k}i^{k}(-1)^{i}(-p)^{i}binom{n}{i}sumlimits_{j=0}^{k-i}(-p)^{j}binom{n-i}{j}\
end{aligned}
]

(g_{i}=sumlimits_{j=0}^{k-i}(-p)^{j}binom{n-i}{j})，有：

[begin{aligned}
g_{i}&=sumlimits_{j=0}^{k-i}(-p)^{j}binom{n-i}{j}\
&=sumlimits_{j=0}^{k-i}(-p)^{j}left(binom{n-i-1}{j}+binom{n-i-1}{j-1}right)\
&=(-p+1)g_{i+1}+(-p)^{k-i}binom{n-i-1}{k-i}
end{aligned}
]

(g_{i}) 带回原式，有：

[ans=sumlimits_{i=0}^{k}i^{k}p^{i}binom{n}{i}g_{i}
]

(text{Code}:)

``````#include <bits/stdc++.h>
#pragma GCC optimize(3)
//#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
#define vi vector<int>
#define vpi vector<pair<int,int>>
using namespace std; const int N=10000010, Mod=998244353;
{
int s=0, w=1; ri char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
return s*w;
}
int n,P,K,up,iiv[N],pw[N],pw2[N],g[N],ans;
int pri[N/10],cnt,w[N]; bool book[N];
inline int ksc(int x,int p) { int res=1; for(;p;p>>=1, x=1ll*x*x%Mod) if(p&1) res=1ll*res*x%Mod; return res; }
inline void Init()
{
iiv[1]=1;
for(ri int i=2;i<=up;i++) iiv[i]=1ll*(Mod-Mod/i)*iiv[Mod%i]%Mod;
pw[0]=1;
P=ksc(P,Mod-2);
for(ri int i=1;i<=up;i++) pw[i]=1ll*pw[i-1]*P%Mod;
w[1]=1;
for(ri int i=2;i<=up;i++)
{
if(!book[i]) pri[++cnt]=i, w[i]=ksc(i,K);
for(ri int j=1;j<=cnt&&i*pri[j]<=up;j++)
{
book[i*pri[j]]=1;
w[i*pri[j]]=1ll*w[i]*w[pri[j]]%Mod;
if(i%pri[j]==0) break;
}
}
}
signed main()
{
up=min(n,K);
Init();
int Q=(Mod+1-P)%Mod;
if(n<=K)
{
pw2[0]=1;
if(Q) for(ri int i=1;i<=n;i++) pw2[i]=1ll*pw2[i-1]*Q%Mod;
for(ri int i=0,now=1,inv=1;i<=n;i++)
{
ans=(ans+1ll*w[i]*pw[i]%Mod*now%Mod*inv%Mod*pw2[n-i]%Mod)%Mod;
now=1ll*now*(n-i)%Mod;
inv=1ll*inv*iiv[i+1]%Mod;
}
printf("%dn",ans);
return 0;
}
g[K]=1;
int now=1;
for(ri int i=K-1;~i;i--)
{
now=1ll*now*(n-i-1)%Mod*iiv[K-i]%Mod;
g[i]=1ll*now*pw[K-i]%Mod;
if((K-i)&1) g[i]=Mod-g[i];
g[i]=(g[i]+1ll*g[i+1]*Q%Mod)%Mod;
}
for(ri int i=0,now=1,inv=1;i<=K;i++)
{
ans=(ans+1ll*w[i]*pw[i]%Mod*now%Mod*inv%Mod*g[i]%Mod)%Mod;
now=1ll*now*(n-i)%Mod;
inv=1ll*inv*iiv[i+1]%Mod;
}
printf("%dn",ans);
return 0;
}
``````