### [Link](https://www.luogu.com.cn/problem/P5400) ### 前置知识 #### 二项式反演（反向） 若 $$ g_i=\sum_{j=i}^n \binom{j}{i} f_j $$ 则 $$ f_i=\sum_{j=i}^n(-1)^{j-i}\binom{j}{i}g_j $$ 若 $f(i)$ 表示恰好 $i$ 个满足条件的方案数，则 $g(i)$ 可表示存在 $i$ 个满足的方案数 我们发现 $f(i)$ 不是很好求，可以先求出 $g(i)$ 再反演出 $f(i)$ #### 树的拓扑序个数 我们先算概率，发现一个树满足条件首先要根节点一定是第一个被选出了的，所以第一位是根节点的概率为 $\frac{1}{n}$ 我们发现其他的子树是互不影响的，所以总方案数为 $\frac{n!}{\prod_{1}^{n} sz[i]}$ #### 线性求序列中任意一个数的逆元（本题卡时间） 预处理整个序列的逆元和前缀积和后缀积 $inv(a_i)=\frac{a_1\cdot a_2\cdots a_{i-1}\times a_{i+1}\cdot a_{i+2}\cdots a_{n}}{a_1\cdot a_2\cdots a_n}\mod p$ --- --- --- --- --- 本题中先把“恰好”去掉，变成先求存在 $k$ 个极大的数的方案数，在通过上面第二个式子反演回去。 选取 $k$ 个的方案数为 $n^{\underline{k}}m^{\underline{k}}l^{\underline{k}}$ 从小到大考虑每一个数，假设前 $i-1$ 小的极大值已经放置在前 $i-1$ 个位置，考虑第 $i$ 个位置是第 $i$ 小的极大值的概率。 注意到一个极大值是第 $i$ 小，意味着它是前 $i$ 个位置所占的截面的并上的最大值 这就是树的拓扑序模型，因此此情况概率为 $\prod_{i=1}^{k} \frac{1}{n m l-(n-i)(m-i)(l-i)}$ 线性预处理逆元最后反演即可。 ### CODE ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e6+10, P=998244353; int fac[N], inv[N], sl[N], sr[N], f[N]; int power(int x, int y) { int r=1; while (y) { if (y&1) r=r*x%P; x=x*x%P; y>>=1; } return r; } void init(int n) { fac[0]=1; for (int i=1; i<=n; i++) fac[i]=fac[i-1]*i%P; inv[n]=power(fac[n], P-2); for (int i=n-1; ~i; i--) inv[i]=inv[i+1]*(i+1)%P; } signed main() { int T=read(); init(N-10); while (T--) { int n=read(), m=read(), l=read(), k=read(), s=n*m%P*l%P; if (n>m) n^=m^=n^=m; if (n>l) n^=l^=n^=l; sl[0]=sr[n+1]=1; for (int i=1; i<=n; i++) sl[i]=sl[i-1]*(s-(n-i)*(m-i)%P*(l-i)%P+P)%P; for (int i=n; i>=1; i--) sr[i]=sr[i+1]*(s-(n-i)*(m-i)%P*(l-i)%P+P)%P; int INV=power(sl[n], P-2); f[0]=1; for (int i=1; i<=n; i++) f[i]=f[i-1]*(n-i+1)%P*(m-i+1)%P*(l-i+1)%P*sl[i-1]%P*sr[i+1]%P*INV%P; int ans=0; for (int i=k; i<=n; i++) ans=(ans+fac[i]*inv[k]%P*inv[i-k]%P*(((i-k)&1)?(P-1):1)%P*f[i]%P)%P; printf("%lld\n", ans); } return 0; } ```` Loading... ### [Link](https://www.luogu.com.cn/problem/P5400) ### 前置知识 #### 二项式反演（反向） 若 $$ g_i=\sum_{j=i}^n \binom{j}{i} f_j $$ 则 $$ f_i=\sum_{j=i}^n(-1)^{j-i}\binom{j}{i}g_j $$ 若 $f(i)$ 表示恰好 $i$ 个满足条件的方案数，则 $g(i)$ 可表示存在 $i$ 个满足的方案数 我们发现 $f(i)$ 不是很好求，可以先求出 $g(i)$ 再反演出 $f(i)$ #### 树的拓扑序个数 我们先算概率，发现一个树满足条件首先要根节点一定是第一个被选出了的，所以第一位是根节点的概率为 $\frac{1}{n}$ 我们发现其他的子树是互不影响的，所以总方案数为 $\frac{n!}{\prod_{1}^{n} sz[i]}$ #### 线性求序列中任意一个数的逆元（本题卡时间） 预处理整个序列的逆元和前缀积和后缀积 $inv(a_i)=\frac{a_1\cdot a_2\cdots a_{i-1}\times a_{i+1}\cdot a_{i+2}\cdots a_{n}}{a_1\cdot a_2\cdots a_n}\mod p$ --- --- --- --- --- 本题中先把“恰好”去掉，变成先求存在 $k$ 个极大的数的方案数，在通过上面第二个式子反演回去。 选取 $k$ 个的方案数为 $n^{\underline{k}}m^{\underline{k}}l^{\underline{k}}$ 从小到大考虑每一个数，假设前 $i-1$ 小的极大值已经放置在前 $i-1$ 个位置，考虑第 $i$ 个位置是第 $i$ 小的极大值的概率。 注意到一个极大值是第 $i$ 小，意味着它是前 $i$ 个位置所占的截面的并上的最大值 这就是树的拓扑序模型，因此此情况概率为 $\prod_{i=1}^{k} \frac{1}{n m l-(n-i)(m-i)(l-i)}$ 线性预处理逆元最后反演即可。 ### CODE ```cpp #include <bits/stdc++.h> #define int long long using namespace std; int read() { int x=0, f=0; char c=getchar(); while (!isdigit(c)) f|=c=='-', c=getchar(); while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar(); return f ? -x : x; } const int N=5e6+10, P=998244353; int fac[N], inv[N], sl[N], sr[N], f[N]; int power(int x, int y) { int r=1; while (y) { if (y&1) r=r*x%P; x=x*x%P; y>>=1; } return r; } void init(int n) { fac[0]=1; for (int i=1; i<=n; i++) fac[i]=fac[i-1]*i%P; inv[n]=power(fac[n], P-2); for (int i=n-1; ~i; i--) inv[i]=inv[i+1]*(i+1)%P; } signed main() { int T=read(); init(N-10); while (T--) { int n=read(), m=read(), l=read(), k=read(), s=n*m%P*l%P; if (n>m) n^=m^=n^=m; if (n>l) n^=l^=n^=l; sl[0]=sr[n+1]=1; for (int i=1; i<=n; i++) sl[i]=sl[i-1]*(s-(n-i)*(m-i)%P*(l-i)%P+P)%P; for (int i=n; i>=1; i--) sr[i]=sr[i+1]*(s-(n-i)*(m-i)%P*(l-i)%P+P)%P; int INV=power(sl[n], P-2); f[0]=1; for (int i=1; i<=n; i++) f[i]=f[i-1]*(n-i+1)%P*(m-i+1)%P*(l-i+1)%P*sl[i-1]%P*sr[i+1]%P*INV%P; int ans=0; for (int i=k; i<=n; i++) ans=(ans+fac[i]*inv[k]%P*inv[i-k]%P*(((i-k)&1)?(P-1):1)%P*f[i]%P)%P; printf("%lld\n", ans); } return 0; } ```` 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏