差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:namespace:牛客多校第五场 [2020/07/28 21:18]
great_designer [K]
+++ 2020-2021:teams:namespace:牛客多校第五场 [2020/07/28 22:34] (当前版本)
great_designer [代码]
@@ 行 417: / 行 417: @@
 （好题啊）
+====题目====
+W先生正在写序列。如果他写两个长度为K的正整数序列A和B满足：
+$$\sum_{i=1}^K a_i=N$$
+$$\sum_{i=1}^K b_i=M$$
+他会得到:
+$$P=\prod_{i=1}^K \min(a_i,b_i)$$
+积分。
+你想知道他能写的所有可能的序列的总分之和。
+====输入输出描述====
+输入第一行包含一个整数T（1≤T≤100），表示T个测试用例。
+接下来的T行每行包含三个整数NMK（1≤N,M≤10^6,1≤K≤min(N,M)）。
+输出答案mod 998244353。
+====做法====
+考虑生成函数。我们知道等比数列求和：
+$$\frac{1}{1-x}=\sum_{i=0}^{\infty} x^i$$
+考虑x和y的无限大系数矩阵（类比第一象限附带正坐标轴整点）。那么全1矩阵就是：
+$$\frac{1}{(1-x)(1-y)}$$
+对角矩阵就是：
+$$\frac{1}{1-xy}$$
+乘在一起，再平移一下，就是：
+$$f(x,y)=\frac{xy}{(1-x)(1-y)(1-xy)}=\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} \min(i,j)x^iy^j$$
+二元多项式f的K次幂，各项系数的含义是什么呢？对于f^K中的某一项x^Ny^M，一定由之前的K个f中的各项系数贡献而来。
+首先，在之前的K个f中，x的各个幂次和是N，y的各个幂次和是M。
+其次，每一个项中的系数都是x和y的最小值，共有K个乘在一起。
+最后，还要对全体合法情况求和，不重不漏。
+因此，所求的答案就是多项式：
+$$\frac{x^Ky^K}{{(1-x)}^K{(1-y)}^K}\frac{1}{{(1-xy)}^K}$$
+之中x^Ny^M前的系数。即多项式：
+$$\frac{1}{{(1-x)}^K}\frac{1}{{(1-y)}^K}\frac{1}{{(1-xy)}^K}$$
+之中x^{N-K}y^{M-K}前的系数。
+我们希望，将“对角线”(1/(1-xy))^K的各项系数全部列出来，再乘上两个方向1/(1-x)^K和1/(1-y)^K，补到N-K和M-K。那么这就需要K次方与组合数的知识：
+$$\frac{1}{(1-x)^K}=\sum_{i=0}^{\infty} C_{K-1+i}^{K-1}x^i$$
+$$\frac{1}{{(1-x)}^K}\frac{1}{{(1-y)}^K}\frac{1}{{(1-xy)}^K}=\left(\sum_{i=0}^{\infty} \sum_{j=0}^{\infty} C_{K-1+i}^{K-1}C_{K-1+j}^{K-1}x^iy^j\right)\left(\sum_{s=0}^{\infty} C_{K-1+s}^{K-1}{(xy)}^s\right)$$
+由于在xy项中指数相等，在x^{N-K}y^{M-K}里面的贡献，差值必然由前面来提供。因此多项式中x^{N-K}y^{M-K}项前的系数为：
+$$\sum_{t=0}^{\min(N,M)-K} C_{K-1+t}^{K-1}C_{N-1-t}^{K-1}C_{M-1-t}^{K-1}$$
+为所求答案。
+====代码====
 <hidden>
 <code C>
 #include<stdio.h>
@@ 行 429: / 行 506: @@
 int C(int n,int m)
 {
-	return 1ll*fac[n]*ffac[m]%mod*ffac[n-m]%mod;
+	return ((1ll*fac[n]*ffac[m])%mod*ffac[n-m])%mod;
 }
 int qpow(int n,int k)
 {
-	int ret = 1;
+	int ret=1;
 	while(k)
 	{
 		if(k&1)
 		{
-			ret = 1ll * ret * n % mod;
+			ret=(1ll*ret*n)%mod;
 		}
-		n = 1ll * n * n % mod;
+		n=(1ll*n*n)%mod;
-		k /= 2;
+		k/=2;
 	}
 	return ret;
 }
-int main()
+void init()
 {
-	fac[0] = 1;
+	fac[0]=1;
 	int i;
-	for(i = 1; i <= 2e6; i++)
+	for(i=1;i<=2e6;i++)
 	{
-		fac[i] = 1ll * fac[i-1] * i % mod;
+		fac[i]=(1ll*fac[i-1]*i)%mod;
 	}
-	ffac[2000000] = qpow(fac[2000000], mod - 2);
+	ffac[2000000]=qpow(fac[2000000],mod-2);
-	for(i = 2e6; i >= 1; i--)
+	for(i=2e6;i>=1;i--)
 	{
-		ffac[i - 1] = 1ll * ffac[i] * i % mod;
+		ffac[i-1]=(1ll*ffac[i]*i)%mod;
 	}
+}
+int main()
+{
+	init();
 	int T;
-	scanf("%d", &T);
+	scanf("%d",&T);
 	while(T--)
 	{
-		int N, M, K;
+		int N,M,K;
-		scanf("%d%d%d", &N, &M, &K);
+		scanf("%d%d%d",&N,&M,&K);
-		int ans = 0;
+		int ans=0;
-		for(i = 0; i <=(N<M?N:M) - K; i++)
+		int i;
+		for(i=0;i<=(N<M?N:M)-K;i++)
 		{
-			ans += 1ll * C(i + K - 1, K - 1) * C(N - i - 1, K - 1) % mod * C(M - i - 1, K - 1) % mod;
+			ans+=((1ll*C(i+K-1,K-1)*C(N-i-1,K-1))%mod*C(M-i-1,K-1))%mod;
-			if(ans >= mod)
+			ans-=(ans>=mod)?mod:0;
-			{
-				ans -= mod;
-			}
 		}
 		printf("%d\n",ans);

CVBB ACM Team

用户工具

站点工具

差别

页面工具