[LGP2791] 幼儿园篮球题
2024-10-07 01:12:59
你猜猜题怎么出出来的?
显然第\(i\)场的答案为
\[\frac{1}{\binom{n_i}{m_i}\binom{n_i}{k_i}}\sum_{x=0}^{k_i}\binom{n_i}{m_i}\binom{m_i}{x}\binom{n_i-m_i}{k_i-x}x^L
=\frac{1}{\binom{n_i}{k_i}}\sum_{x=0}^{k_i}\binom{m_i}{x}\binom{n_i-m_i}{k_i-x}x^L\\
\]
=\frac{1}{\binom{n_i}{k_i}}\sum_{x=0}^{k_i}\binom{m_i}{x}\binom{n_i-m_i}{k_i-x}x^L\\
\]
利用斯特林数进行变换
\[\sum_{x=0}^{k_i}\binom{m_i}{x}\binom{n_i-m_i}{k_i-x}x^L
=\sum_{x=0}^{k_i}\binom{m_i}{x}\binom{n_i-m_i}{k_i-x}\sum_{y=0}^{x}y!\binom{x}{y}\left\{\begin{matrix}L\\y\end{matrix}\right\}\\
=\sum_{y=0}^{k_i}y!\left\{\begin{matrix}L\\y\end{matrix}\right\}
\sum_{x=y}^{k_i}\binom{x}{y}\binom{m_i}{x}\binom{n_i-m_i}{k_i-x}\\
=\sum_{y=0}^{k_i}y!\left\{\begin{matrix}L\\y\end{matrix}\right\}
\sum_{x=y}^{k_i}\binom{m_i}{y}\binom{m_i-y}{x-y}\binom{n_i-m_i}{k_i-x}\\
=\sum_{y=0}^{k_i}y!\binom{m_i}{y}\left\{\begin{matrix}L\\y\end{matrix}\right\}
\sum_{x=0}^{k_i-y}\binom{m_i-y}{x}\binom{n_i-m_i}{k_i-y-x}\\
=\sum_{y=0}^{k_i}y!\binom{m_i}{y}\left\{\begin{matrix}L\\y\end{matrix}\right\}
\binom{n_i-y}{k_i-y}
\]
=\sum_{x=0}^{k_i}\binom{m_i}{x}\binom{n_i-m_i}{k_i-x}\sum_{y=0}^{x}y!\binom{x}{y}\left\{\begin{matrix}L\\y\end{matrix}\right\}\\
=\sum_{y=0}^{k_i}y!\left\{\begin{matrix}L\\y\end{matrix}\right\}
\sum_{x=y}^{k_i}\binom{x}{y}\binom{m_i}{x}\binom{n_i-m_i}{k_i-x}\\
=\sum_{y=0}^{k_i}y!\left\{\begin{matrix}L\\y\end{matrix}\right\}
\sum_{x=y}^{k_i}\binom{m_i}{y}\binom{m_i-y}{x-y}\binom{n_i-m_i}{k_i-x}\\
=\sum_{y=0}^{k_i}y!\binom{m_i}{y}\left\{\begin{matrix}L\\y\end{matrix}\right\}
\sum_{x=0}^{k_i-y}\binom{m_i-y}{x}\binom{n_i-m_i}{k_i-y-x}\\
=\sum_{y=0}^{k_i}y!\binom{m_i}{y}\left\{\begin{matrix}L\\y\end{matrix}\right\}
\binom{n_i-y}{k_i-y}
\]
发现\(y\)的实际上界为\(\min(k_i,m_i,L)\)不过\(1e5\),而询问仅\(2e2\),预处理第\(L\)行斯特林数,询问复杂度\(O(L)\)可以接受。
斯特林数的预处理参见。
最终答案为
\[\sum_{i=1}^S\frac{k_i!(n_i-k_i)!}{n_i!}\sum_{y=0}^{k_i}y!\frac{m_i!(n_i-y)!}{y!(m_i-y)!(k_i-y)!(n_i-k_i)!}S(L,y)\\
=\sum_{i=1}^S\frac{k_i!m_i!}{n_i!}\sum_{y=0}^{k_i}\frac{(n_i-y)!}{(m_i-y)!(k_i-y)!}S(L,y)
\]
=\sum_{i=1}^S\frac{k_i!m_i!}{n_i!}\sum_{y=0}^{k_i}\frac{(n_i-y)!}{(m_i-y)!(k_i-y)!}S(L,y)
\]
显得十分的和谐。
此题卡常
#include <bits/stdc++.h>
#define IL inline
#define ll long long
using namespace std;
const int N=8e5+10;
const int M=2e7+10;
const int mod=998244353;
IL ll gi(){
ll x=0,f=1;
char ch=getchar();
while(!isdigit(ch))f^=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f?x:-x;
}
int lmt,w[N],rev[N];
IL int fpw(int x,int y) {
int c=1;
for(; y; y>>=1,x=(ll)x*x%mod) if(y&1) c=(ll)c*x%mod;
return c;
}
IL void init(int n) {
int l=0; lmt=1;
while(lmt<=n) lmt<<=1, l++;
for(int i=0; i<lmt; ++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
int tmp=lmt>>1, wlmt=fpw(3,(mod-1)>>l); w[tmp]=1;
for(int i=tmp+1; i<lmt; ++i) w[i]=(ll)w[i-1]*wlmt%mod;
for(int i=tmp-1; i; --i) w[i]=w[i<<1];
lmt=l;
}
IL void DFT(int*a,int len) {
static unsigned ll tmp[N];
int u=lmt-__builtin_ctz(len),T;
for(int i=0; i<len; ++i) tmp[rev[i]>>u]=a[i];
for(int m=1; m<len; m<<=1)
for(int i=0,s=m<<1; i<len; i+=s)
for(int j=0; j<m; ++j)
T=tmp[i+j+m]*w[j+m]%mod,tmp[i+j+m]=tmp[i+j]+mod-T,tmp[i+j]+=T;
for(int i=0; i<len; ++i) a[i]=tmp[i]%mod;
}
IL void IDFT(int*a,int len) {
reverse(a+1,a+len); DFT(a,len);
ll T=mod-(mod-1)/len;
for(int i=0; i<len; ++i) a[i]=T*a[i]%mod;
}
IL int getLen(int n) {return 1<<(32-__builtin_clz(n));}
int n,m,s,l,k,fiv[M],fac[M],f[N],g[N];
IL void getFac(int n) {
fac[0]=1;
for(int i=1; i<=n; ++i) fac[i]=(ll)fac[i-1]*i%mod;
fiv[n]=fpw(fac[n],mod-2);
for(int i=n-1; ~i; --i) fiv[i]=(ll)fiv[i+1]*(i+1)%mod;
}
int cnt,pri[N];
bool vis[N];
IL void getSti(int n) {
ll fup=mod-1;
for(int i=0; i<=n; ++i) {
fup=mod-fup;
f[i]=fup*fiv[i]%mod;
}
g[1]=1;
for(int i=2; i<=n; ++i) {
if(!vis[i]) pri[++cnt]=i,g[i]=fpw(i,n);
for(int j=1; j<=cnt&&pri[j]*i<=n; ++j) {
vis[pri[j]*i]=1;
g[pri[j]*i]=(ll)g[pri[j]]*g[i]%mod;
if(i%pri[j]==0) break;
}
}
for(int i=1; i<=n; ++i) g[i]=(ll)g[i]*fiv[i]%mod;
int len=getLen(n<<1);
DFT(f,len); DFT(g,len);
for(int i=0; i<len; ++i) f[i]=(ll)f[i]*g[i]%mod;
IDFT(f,len);
for(int i=n+1; i<len; ++i) f[i]=0;
}
int main() {
scanf("%d%d%d%d",&n,&m,&s,&l);
init(l<<1);
getFac(max(n,l));
getSti(l);
while(s--) {
scanf("%d%d%d",&n,&m,&k);
int T=min(min(m,k),l),sum=0;
for(int i=0; i<=T; ++i) sum=(sum+(ll)fac[n-i]*fiv[m-i]%mod*fiv[k-i]%mod*f[i]%mod)%mod;
sum=(ll)sum*fac[k]%mod*fac[m]%mod*fiv[n]%mod;
printf("%d\n",sum);
}
return 0;
}
最新文章
- DOM性能瓶颈与Javascript性能优化
- spring mvc 请求转发和重定向(转)
- libCEF总结02字符串
- The 5th Zhejiang Provincial Collegiate Programming Contest---ProblemF:Faster, Higher, Stronger
- Android 中 更新视图的函数ondraw() 和dispatchdraw()的区别
- web前端开发浏览器兼容性 - 持续更新
- C语言指针类型 强制转换
- poj 1850 1019 (简单位数dp)
- MySQL show binglog event in &#39;log_name&#39;
- perl 第十四章 Perl5的包和模块
- openstack镜像如何在vmware 环境中运行
- PLSQL Developer oracle导入导出表及数据
- C和C++运行库
- day 23 二十三、对象方法,类方法,封装,绑定方法
- [Swift]在Swift项目中创建桥接头文件,Swift文件和Objective-C文件相互调用
- apach ab 安装时的错误
- 浅谈C#依赖注入
- python selenium 模拟登陆百度账号
- IdentityServer4 And AspNetCore.Identity Get AccessToken 问题
- java HttpServletRequest和HttpServletResponse詳解
热门文章
- echarts的渲染问题
- oracle报错:The Network Adapter could not establish the connection的解决
- oracle 中使用 pl/sql代码块
- Win10环境:使用VLC搭建RTSP服务器
- VS Code 调试 Golang 出现 Failed to continue: Check the debug console for details
- Haskell 安装
- java tfserving grpc 通信调用代码解析 【重点参考】
- tensorflow二进制文件读取与tfrecords文件读取
- 七十七:flask.Restful之flask-Restful参数验证
- java读取blob,clob转换为字符串