1 条题解
-
0
自动搬运
来自洛谷，原作者为
NaCly_Fish
北海虽赊，扶摇可接。搬运于
2025-08-24 22:39:29，当前版本为作者最后更新于2022-08-20 22:53:14，作者可能在搬运后再次修改，您可在原文处查看最新版自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多
以下是正文
场上就一个人 AC，怎么回事呢？
样例给的做法提示很明显，就是 有 个选手过线概率 乘以 给 个选手分配的期望价值 再求和。
有 个人过线的概率很简单，就是 ，分治乘即可。
然后需要计算给 个选手分配的价值总和。对于这种经典模型，对每种奖品建立 EGF，然后都乘起来，也就是：
$$k![x^k]\prod_{i=1}^A(1+a_i(\cosh x-1))\times \prod_{i=1}^B(b_i \sinh x) $$后一部分很简单，前一部分有个暴力做法：做换元 ，然后直接分治乘，最后就是求 的系数。
$$=[x^k]\sum_{k=0}^\infty x^k\sum_{i=-A}^Af_i i^k =[x^k]\sum_{i=-A}^A\frac{f_i}{1-ix} $$可以直接维护分子和分母分治求和。
最后把总和变为期望就是除一个方案数，令 都为 就是答案。
参考代码（没太注意实现细节，跑得比较慢）：
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> #define N 1048579 #define p 998244353 #define ll long long using namespace std; inline void read(int &x){ x = 0; char c = getchar(); while(c<'0'||c>'9') c = getchar(); while(c>='0'&&c<='9'){ x = (x<<3)+(x<<1)+(c^48); c = getchar(); } } void print(int x){ if(x>9) print(x/10); putchar(x%10+'0'); } inline int power(int a,int t){ int res = 1; while(t){ if(t&1) res = (ll)res*a%p; a = (ll)a*a%p; t >>= 1; } return res; } inline int add(const int& x,const int& y){ return x+y>=p?x+y-p:x+y; } inline int dec(const int& x,const int& y){ return x<y?x-y+p:x-y; } int rt[N],rev[N],fac[N],ifac[N],inv[N]; int siz; void init(int n){ int w,lim = 1; while(lim<=n) lim <<= 1,++siz; for(int i=1;i!=lim;++i) rev[i] = (rev[i>>1]>>1)|((i&1)<<(siz-1)); w = power(3,(p-1)>>siz); inv[1] = fac[0] = fac[1] = ifac[0] = ifac[1] = rt[lim>>1] = 1; for(int i=(lim>>1)+1;i!=lim;++i) rt[i] = (ll)rt[i-1]*w%p; for(int i=(lim>>1)-1;i;--i) rt[i] = rt[i<<1]; for(int i=2;i<=n;++i) fac[i] = (ll)fac[i-1]*i%p; ifac[n] = power(fac[n],p-2); for(int i=n-1;i;--i) ifac[i] = (ll)ifac[i+1]*(i+1)%p; for(int i=2;i<=n;++i) inv[i] = (ll)fac[i-1]*ifac[i]%p; } inline void dft(int *f,int n){ static unsigned long long a[N]; int x,shift = siz-__builtin_ctz(n); for(int i=0;i!=n;++i) a[rev[i]>>shift] = f[i]; for(int mid=1;mid!=n;mid<<=1) for(int j=0;j!=n;j+=(mid<<1)) for(int k=0;k!=mid;++k){ x = a[j|k|mid]*rt[mid|k]%p; a[j|k|mid] = a[j|k]+p-x; a[j|k] += x; } for(int i=0;i!=n;++i) f[i] = a[i]%p; } inline void idft(int *f,int n){ reverse(f+1,f+n); dft(f,n); int x = p-((p-1)>>__builtin_ctz(n)); for(int i=0;i!=n;++i) f[i] = (ll)f[i]*x%p; } inline int getlen(int n){ return 1<<(32-__builtin_clz(n)); } inline void inverse(const int *f,int n,int *r){ static int g[N],h[N],st[30]; memset(g,0,getlen(n<<1)<<2); int lim = 1,top = 0; while(n){ st[++top] = n; n >>= 1; } g[0] = 1; while(top--){ n = st[top+1]; while(lim<=(n<<1)) lim <<= 1; memcpy(h,f,(n+1)<<2); memset(h+n+1,0,(lim-n)<<2); dft(g,lim),dft(h,lim); for(int i=0;i!=lim;++i) g[i] = g[i]*(2-(ll)g[i]*h[i]%p+p)%p; idft(g,lim); memset(g+n+1,0,(lim-n)<<2); } memcpy(r,g,(n+1)<<2); } int n,A,B; int pr[N],a[N],C[N]; void product(int l,int r,int *R){ if(l==r){ R[0] = p+1-pr[l],R[1] = pr[l]; return; } int lim = getlen(r-l+1),mid = (l+r)>>1; int fl = mid-l+1,gl = r-mid; int f[lim+2],g[lim+2]; product(l,mid,f),product(mid+1,r,g); memset(f+fl+1,0,(lim-fl)<<2); memset(g+gl+1,0,(lim-gl)<<2); dft(f,lim),dft(g,lim); for(int i=0;i!=lim;++i) R[i] = (ll)f[i]*g[i]%p; idft(R,lim); } void prod2(int l,int r,int *R){ if(l==r){ R[0] = R[2] = a[l],R[1] = ((p+1-a[l])<<1)%p; return; } int lim = getlen((r-l+1)<<1),mid = (l+r)>>1; int fl = (mid-l+1)<<1,gl = (r-mid)<<1; int f[lim+2],g[lim+2]; prod2(l,mid,f),prod2(mid+1,r,g); memset(f+fl+1,0,(lim-fl)<<2); memset(g+gl+1,0,(lim-gl)<<2); dft(f,lim),dft(g,lim); for(int i=0;i!=lim;++i) R[i] = (ll)f[i]*g[i]%p; idft(R,lim); } void solve(int l,int r,const int *sc,int *fz,int *fm){ // 多项式复合 F(e^x) if(l==r){ fz[0] = sc[l+A],fm[0] = 1,fm[1] = (p-l)%p; return; } int lim = getlen(r-l+1),mid = (l+r)>>1; int fl = mid-l+1,gl = r-mid; int lfz[lim+2],lfm[lim+2],rfz[lim+2],rfm[lim+2]; solve(l,mid,sc,lfz,lfm),solve(mid+1,r,sc,rfz,rfm); memset(lfz+fl,0,(lim-fl+1)<<2),memset(lfm+fl+1,0,(lim-fl)<<2); memset(rfz+gl,0,(lim-gl+1)<<2),memset(rfm+gl+1,0,(lim-gl)<<2); dft(lfz,lim),dft(lfm,lim),dft(rfz,lim),dft(rfm,lim); for(int i=0;i!=lim;++i){ fz[i] = ((ll)lfz[i]*rfm[i]+(ll)lfm[i]*rfz[i])%p; fm[i] = (ll)lfm[i]*rfm[i]%p; } idft(fz,lim),idft(fm,lim); } inline void deriv(const int *f,int n,int *R){ for(int i=1;i!=n;++i) R[i-1] = (ll)i*f[i]%p; R[n-1] = 0; } inline void integ(const int *f,int n,int *R){ for(int i=n-1;i;--i) R[i] = (ll)f[i-1]*inv[i]%p; R[0] = 0; } inline void log(const int *f,int n,int *r){ static int g[N],h[N]; inverse(f,n,g); deriv(f,n+1,h); int lim = getlen(n<<1); memset(g+n+1,0,(lim-n)<<2); memset(h+n+1,0,(lim-n)<<2); dft(g,lim),dft(h,lim); for(int i=0;i!=lim;++i) g[i] = (ll)g[i]*h[i]%p; idft(g,lim); integ(g,n+1,r); } inline void exp(const int *a,int n,int *R){ int m = n+1; n = 1; while(n<m) n <<= 1; static int der[N],b[N],c[N],dfta[N],dftb[N],dftb2[N],dftc[N]; for(int i=0;i!=n;++i) b[i] = c[i] = dfta[i] = dftb[i] = dftb2[i] = dftc[i] = 0; dftb2[0] = b[0] = c[0] = 1; dft(dftb2,2); deriv(a,n,der); for(int d=1;d!=n;d<<=1){ memcpy(dftc,c,d<<2); dft(dftc,d<<1); for(int i=0;i!=d;++i) dftb[i] = (ll)dftb2[i<<1]*dftc[i<<1]%p; idft(dftb,d); dftb[0] = dec(dftb[0],1); for(int i=0;i!=d;++i) dftb[d+i] = dftb[i]; memset(dftb,0,d<<2); dft(dftb,d<<1); memcpy(dfta,der,(d-1)<<2); dfta[d-1] = 0; dft(dfta,d<<1); for(int i=0;i!=(d<<1);++i) dfta[i] = (ll)dfta[i]*dftb[i]%p; idft(dfta,d<<1); deriv(b,d,dftb); dft(dftb,d); for(int i=0;i!=d;++i) dftb[i] = (ll)dftb[i]*dftc[i<<1]%p; idft(dftb,d); for(int i=0;i!=d-1;++i) dftb[d+i] = dec(dftb[i],der[i]); memset(dftb,0,(d-1)<<2); for(int i=d-1;i!=(d<<1);++i) dftb[i] = dec(dftb[i],add(der[i],dfta[i])); integ(dftb,d<<1,dftb); dft(dftb,d<<1); for(int i=0;i!=(d<<1);++i) dftb[i] = (ll)dftb[i]*dftb2[i]%p; idft(dftb,d<<1); for(int i=d;i!=(d<<1);++i) b[i] = p-dftb[i]; if((d<<1)==n) continue; memcpy(dftb2,b,d<<3); dft(dftb2,d<<2); for(int i=0;i!=(d<<1);++i) dftb[i] = (ll)dftb2[i<<1]*dftc[i]%p; idft(dftb,d<<1); memset(dftb,0,d<<2); dft(dftb,d<<1); for(int i=0;i!=(d<<1);++i) dftb[i] = (ll)dftb[i]*dftc[i]%p; idft(dftb,d<<1); for(int i=d;i!=(d<<1);++i) c[i] = p-dftb[i]; } memcpy(R,b,m<<2); } int f[N],g[N],fz[N],fm[N],suf[N]; int pw,ans; int main(){ read(n),read(A),read(B); if(n<B){ puts("0"); return 0; } init(800000); for(int i=1;i<=n;++i) read(pr[i]); for(int i=1;i<=A;++i) read(a[i]); product(1,n,C),prod2(1,A,f); solve(-A,A,f,fz,fm); for(int i=n+1;i<=(A<<1);++i) fz[i] = fm[i] = 0; inverse(fm,n,fm); int lim = getlen(n<<1); dft(fz,lim),dft(fm,lim); for(int i=0;i!=lim;++i) fz[i] = (ll)fz[i]*fm[i]%p; idft(fz,lim); memset(fz+n+1,0,(lim-n)<<2),memset(f,0,lim<<2); for(int i=0;i<=n;++i) fz[i] = (ll)fz[i]*ifac[i]%p; int tn = max((n-B)>>1,4); for(int i=0;i<=tn;++i) f[i] = ifac[i<<1|1]; log(f,tn,f); for(int i=0;i<=tn;++i) f[i] = (ll)f[i]*B%p; exp(f,tn,f); for(int i=tn;i;--i) f[i<<1] = f[i],f[i] = 0; for(int i=n;i>=B;--i) f[i] = f[i-B]; memset(f,0,B<<2),memset(f+n+1,0,(lim-n)<<2); for(int i=0;(i<<1)<=n;++i) g[i] = ifac[i<<1]; log(g,n>>1,g); for(int i=0;(i<<1)<=n;++i) g[i] = (ll)g[i]*A%p; exp(g,n>>1,g); for(int i=(n>>1);i;--i) g[i<<1] = g[i],g[i] = 0; dft(fz,lim),dft(f,lim),dft(g,lim); for(int i=0;i!=lim;++i){ fz[i] = (ll)fz[i]*f[i]%p; g[i] = (ll)g[i]*f[i]%p; } idft(fz,lim),idft(g,lim); suf[n+1] = 1; for(int i=n;i;--i) suf[i] = (ll)suf[i+1]*(g[i]==0?1:g[i])%p; int pre = power(suf[1],p-2); for(int i=1;i<=n;++i){ ans = (ans+(ll)fz[i]*C[i]%p*pre%p*suf[i+1])%p; pre = (ll)pre*(g[i]==0?1:g[i])%p; } for(int i=1;i<=B;++i){ read(pw); ans = (ll)ans*pw%p; } ans = (ll)ans*power(2,p-A-1)%p; print(ans); return 0; }
15011418730
LV 7
@ 2025-8-24 22:39:29
- 1
