[LibreOJ 3119]【CTS2019】随机立方体【计数】【容斥】

素颜马尾好姑娘i 2021-12-23 12:39 184阅读 0赞

## Description ##

![在这里插入图片描述][20190521165544680.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h6ajEwNTQ2ODk2OTk_size_16_color_FFFFFF_t_70]

## Solution ##

记\\(N=min(n,m,l)\\)  
首先考虑容斥，记\\(f(i)\\)为至少有i个位置是极大的，显然极大的位置数上界是N。  
那么显然\\(Ans=\\sum\\limits\_\{i=k\}^\{N\}(-1)^\{i-k\}f(i)\{i \\choose k\}\\)

现在来计算\\(f\\)  
我们考虑立方体中哪些**位置**是极大的，显然这些极大的位置三维坐标都互不相同，然后剩下的怎么选概率都是一样的。

将这i个位置按值从小到大排起来，那么有序的选出\\(i\\)个位置的方案数就是\\(n^\{i\\downarrow\}m^\{i\\downarrow\}l^\{i\\downarrow\}\\)，下降箭头表示下降幂。

然后这些位置都必须是这些坐标中最大的。记\\(S\_j\\)为与第j个位置有坐标相同的点集。

如果直接对于每一个位置j计算它是\\(S\_j\\)中最大的点的概率，然后再全部乘在一起，这是不正确的，因为\\(S\\)之间可能有交，即使排除了交的部分，概率仍然是不独立的。

但是我们注意到位置已经按照小到大排了，因此\\(a\_2>a\_1\\geq S\_1,a\_2\\geq S\_2\\)，因此一定满足\\(a\_2\\geq S\_1\\cup S\_2,a\_3\\geq S\_1\\cup S\_2 \\cup S\_3......\\)  
可以发现，这样每个位置是极大的概率就独立了。

因此\\(f(k)=n^\{k\\downarrow\}m^\{k\\downarrow\}l^\{k\\downarrow\}\\sum\\limits\_\{j=1\}^\{k\}\{1\\over nml-(n-j)(m-j)(l-j)\}\\)

预处理n个数的逆元可以用前缀积做到\\(O(n+\\log)\\)，因此总的时间复杂度就是\\(O(tN)\\)的

## Code ##

#include <bits/stdc++.h> #define fo(i,a,b) for(int i=a;i<=b;++i) #define fod(i,a,b) for(int i=a;i>=b;--i) #define N 5000005 #define LL long long #define mo 998244353 using namespace std; LL js[N],ny[N],d[N],nd[N],ds[N]; LL ksm(LL k,LL n) { LL s=1; for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo; return s; } LL C(int n,int m) { if(n<m) return 0; return js[n]*ny[m]%mo*ny[n-m]%mo; } LL n,m,l,r,n1; int main() { int t; cin>>t; js[0]=1; fo(i,1,N-5) js[i]=js[i-1]*(LL)i%mo; ny[N-5]=ksm(js[N-5],mo-2); fod(i,N-6,0) ny[i]=ny[i+1]*(LL)(i+1)%mo; while(t--) { cin>>n>>m>>l>>r; n1=min(n,min(m,l)); LL v=1,ans=0,s=1,np=n*m%mo*l%mo; ds[0]=1; fo(i,1,n1) { d[i]=(np-(n-i)*(m-i)%mo*(l-i)%mo+mo)%mo; ds[i]=ds[i-1]*d[i]%mo; } nd[n1]=ksm(ds[n1],mo-2); fod(i,n1-1,0) nd[i]=nd[i+1]*d[i+1]%mo; fo(i,1,n1) { s=s*(n-i+1)%mo*(m-i+1)%mo*(l-i+1)%mo; s=s*nd[i]%mo*ds[i-1]%mo; if(i>=r) { ans=(ans+s*v%mo*C(i,r)%mo)%mo; v=mo-v; } } printf("%lld\n",ans); } }

转载于:https://www.cnblogs.com/BAJimH/p/10902111.html

[20190521165544680.png]: /images/20211223/2db0d6b6efe14851865fe99fa870c4d1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h6ajEwNTQ2ODk2OTk_size_16_color_FFFFFF_t_70]: /images/20211223/fc798415a8b2474aaa14b771c8bbe74c.png