十八个免费的舆情网站,电子商务网站建设用什么软件,p2p网站建设广州,wordpress主题免费吗正题
题目链接:https://www.luogu.com.cn/problem/P5400 题目大意
有一个nmln\times m\times lnml的三维网格#xff0c;要在每个格子处填上一个数#xff0c;要求填的数中1∼nml1\sim n\times m\times l1∼nml都恰好出现了一次。
一个极大值被定义为这个格子比其他与它至…正题
题目链接:https://www.luogu.com.cn/problem/P5400 题目大意
有一个n×m×ln\times m\times ln×m×l的三维网格要在每个格子处填上一个数要求填的数中1∼n×m×l1\sim n\times m\times l1∼n×m×l都恰好出现了一次。
一个极大值被定义为这个格子比其他与它至少有一个坐标相同的格子都大求恰好有kkk个极大值的概率。
1≤n,m,l≤5×106,1≤k≤100,1≤T≤101\leq n,m,l\leq 5\times 10^6,1\leq k\leq 100,1\leq T\leq 101≤n,m,l≤5×106,1≤k≤100,1≤T≤10 解题思路
恰好我们很难进行计数所以我们考虑钦定kkk个极大值然后用二项式反演。
假设n≤m≤ln\leq m\leq ln≤m≤l那么极大值个数不超过nnn个。
考虑怎么求钦定kkk个极大值时的方案首先每个极大值的位置是没有关系的因为三个坐标都肯定各不相同。
那么我们就默认第iii个最大值的位置是(i,i,i)(i,i,i)(i,i,i)且第iii个极大值aiai1a_ia_{i1}aiai1。
这样的话对于每个极大值限制的范围就是一层一层的嵌套。先考虑不在限制范围内的数选一些填上那么方案就是(nml(n−k)(m−k)(l−k))\binom{nml}{(n-k)(m-k)(l-k)}((n−k)(m−k)(l−k)nml)然后还要考虑在外面填的方案那么总方案就是Anml(n−k)(m−k)(l−k)A_{nml}^{(n-k)(m-k)(l-k)}Anml(n−k)(m−k)(l−k)。
然后考虑填被限制的数字的方案从外层开始填那么第一层就是除了(1,1,1)(1,1,1)(1,1,1)以外随便填了。
为了方便我们记Gk(n−k)(m−k)(l−k)G_k(n-k)(m-k)(l-k)Gk(n−k)(m−k)(l−k)那么第一层的方案就是(G0−G1−1)!(G_0-G_{1}-1)!(G0−G1−1)!同样推出第二层的方案(G1−G2−1)!(G_1-G_2-1)!(G1−G2−1)!不过要把第二层的数字穿插在第一层中除了极大值那么就是(G1−G2−1)!×CG0−G2−1G1−G2−1(G_1-G_2-1)!\times C_{G_0-G_2-1}^{G_1-G_2-1}(G1−G2−1)!×CG0−G2−1G1−G2−1。
那么写出总答案就是 1G0!AG0Gk∏i0k−1(Gi−Gi1−1)!CG0−Gi1−1Gi−Gi1−1\frac{1}{G_0!}A_{G_0}^{G_k}\prod_{i0}^{k-1}(G_i-G_{i1}-1)!C_{G_0-G_{i1}-1}^{G_i-G_{i1}-1}G0!1AG0Gki0∏k−1(Gi−Gi1−1)!CG0−Gi1−1Gi−Gi1−1 拆分开来 1Gk!∏i0k−1(Gi−Gi1−1)!(G0−Gi1−1)!(Gi−Gi1−1)!(G0−Gi)!\frac{1}{G_k!}\prod_{i0}^{k-1}(G_i-G_{i1}-1)!\frac{(G_0-G_{i1}-1)!}{(G_i-G_{i1}-1)!(G_0-G_i)!}Gk!1i0∏k−1(Gi−Gi1−1)!(Gi−Gi1−1)!(G0−Gi)!(G0−Gi1−1)! 1Gk!∏i0k−1(G0−Gi1−1)!(G0−Gi)!\frac{1}{G_k!}\prod_{i0}^{k-1}\frac{(G_0-G_{i1}-1)!}{(G_0-G_i)!}Gk!1i0∏k−1(G0−Gi)!(G0−Gi1−1)! 我们会发现我们能用前面的1Gk!\frac{1}{G_k!}Gk!1的某些部分去补足后面G0−GiG_0-G_{i}G0−Gi和G0−Gi1−1G_0-G_{i1}-1G0−Gi1−1的差但是因为会有重复部分我们只提出[G0−Gi1,G0−Gi1][G_0-G_i1,G_0-G_{i1}][G0−Gi1,G0−Gi1]这一部分就有 ∏i1k1G0−Gi∏i0k−1Gi\prod_{i1}^{k}\frac{1}{G_0-G_i}\prod_{i0}^{k-1}G_ii1∏kG0−Gi1i0∏k−1Gi
这样我们用O(n)O(n)O(n)预处理逆元的方法就可以做到O(Tn)O(Tn)O(Tn)了。 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N5e610,P998244353;
ll T,n,m,l,k,fac[N],fnv[N];
ll g[N],G[N],f[N],inv[N],ans;
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
ll C(ll n,ll m)
{return fac[n]*fnv[m]%P*fnv[n-m]%P;}
signed main()
{fnv[0]fnv[1]fac[0]1;for(ll i2;iN;i)fnv[i]P-fnv[P%i]*(P/i)%P;for(ll i1;iN;i)fac[i]fac[i-1]*i%P,fnv[i]fnv[i-1]*fnv[i]%P;scanf(%lld,T);while(T--){scanf(%lld%lld%lld%lld,n,m,l,k);ll Sn*m%P*l%P;g[0]S;ans0;if(mn)swap(n,m);if(ln)swap(n,l);inv[0]1;if(kn){puts(0);continue;}for(ll i1;in;i){G[i](S-(n-i)*(m-i)%P*(l-i)%PP)%P;g[i](n-i)*(m-i)%P*(l-i)%P;inv[i]inv[i-1]*G[i]%P;}inv[n]power(inv[n],P-2);for(ll in;i1;i--)inv[i-1]inv[i]*G[i]%P;f[0]1;for(ll i1;in;i)f[i]f[i-1]*g[i-1]%P;for(ll i0;in;i)f[i]f[i]*inv[i]%P;for(ll ik;in;i)(ansC(i,k)*f[i]%P*(((i-k)1)?(P-1):1)%P)%P;printf(%lld\n,ans);}return 0;
}
