差别

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

--- 2020-2021:teams:namespace:牛客多校第五场 [2020/07/28 17:50]
great_designer [J]
+++ 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);
@@ 行 812: / 行 892: @@
 这又是一个大作业题目了。没想到竟然可以简单地用C语言完成。
-<hidden>
+[[小型代码管理系统的实现方式]]
-<code C>
-#include<stdio.h>
-#include<string.h>
-const char op1[]="<<<<<<< branch1";
-const char op2[]="=======";
-const char op3[]=">>>>>>> branch2";
-struct pp
-{
-	int first;
-	int second;
-};
-struct pp makepp(int a,int b)
-{
-	struct pp temp;
-	temp.first=a;
-	temp.second=b;
-	return temp;
-}
-struct pp op1hash,op2hash,op3hash;
-char s1[4007][267],s2[4007][267];
-int len1[4007],len2[4007];
-char s[267];
-int n1=0,n2=0;
-struct pp hash1[4007],hash2[4007];
-short f[4007][4007][3],g[4007][4007][3];
-struct qq
-{
-	struct pp first;
-	int second;
-};
-struct qq makeqq(struct pp a,int b)
-{
-	struct qq temp;
-	temp.first=a;
-	temp.second=b;
-	return temp;
-}
-struct qq que[4007];
-int cnt=0;
-int main()
-{
-    op1hash=makepp(0,0);
-    int i;
-    for(i=0;i<strlen(op1);i++)
-    {
-        op1hash.first=(1LL*307*op1hash.first+op1[i]+1)%998244353;
-        op1hash.second=(1LL*307*op1hash.second+op1[i]+1)%100000007;
-    }
-    op2hash=makepp(0,0);
-    for(i=0;i<strlen(op2);i++)
-    {
-        op2hash.first=(1LL*307*op2hash.first+op2[i]+1)%998244353;
-        op2hash.second=(1LL*307*op2hash.second+op2[i]+1)%100000007;
-    }
-    op3hash=makepp(0,0);
-    for(i=0;i<strlen(op3);i++)
-    {
-        op3hash.first=(1LL*307*op3hash.first+op3[i]+1)%998244353;
-        op3hash.second=(1LL*307*op3hash.second+op3[i]+1)%100000007;
-    }
-    int curstatus=0;
-    char ch=getchar();
-    while(ch!=EOF)
-    {
-        int len=0;
-        while(ch!='\n'&&ch!=EOF)
-        {
-            s[len++]=ch;
-            ch=getchar();
-        }
-        struct pp h=makepp(0,0);
-        for(i=0;i<len;i++)
-        {
-            h.first=(1LL*307*h.first+s[i]+1)%998244353;
-            h.second=(1LL*307*h.second+s[i]+1)%100000007;
-        }
-        if(h.first==op1hash.first&&h.second==op1hash.second)
-		{
-			curstatus=1;
-		}
-        else if(h.first==op2hash.first&&h.second==op2hash.second)
-		{
-			curstatus=2;
-		}
-        else if(h.first==op3hash.first&&h.second==op3hash.second)
-		{
-			curstatus=0;
-		}
-        else
-        {
-            if(curstatus!=1)
-            {
-                len2[++n2]=len;
-                hash2[n2]=h;
-                for(i=0;i<len;i++)
-                {
-                	s2[n2][i]=s[i];
-				}
-            }
-            if(curstatus!=2)
-            {
-                len1[++n1]=len;
-                hash1[n1]=h;
-                for(i=0;i<len;i++)
-                {
-                	s1[n1][i]=s[i];
-				}
-            }
-        }
-        if(ch!=EOF)
-		{
-			ch=getchar();
-		}
-	}
-    for(i=0;i<=n1;i++)
-    {
-    	int j;
-    	for(j=0;j<=n2;j++)
-    	{
-    		int k;
-    		for(k=0;k<3;k++)
-    		{
-    			f[i][j][k]=10007;
-				g[i][j][k]=0;
-			}
-		}
-	}
-    f[0][0][0]=0;
-    f[0][0][1]=1;
-    g[0][0][1]=0;
-    f[0][0][2]=1;
-    g[0][0][2]=0;
-    for(i=0;i<=n1;i++)
-    {
-    	int j;
-    	for(j=0;j<=n2;j++)
-        {
-            if(i==0&&j==0)
-			{
-				continue;
-			}
-            if(i>0)
-            {
-                if(f[i][j][1]>f[i-1][j][1]+1)
-                {
-                    f[i][j][1]=f[i-1][j][1]+1;
-                    g[i][j][1]=-1;
-                }
-            }
-            if(j>0)
-            {
-                if(f[i][j][2]>f[i][j-1][2]+1)
-                {
-                    f[i][j][2]=f[i][j-1][2]+1;
-                    g[i][j][2]=-1;
-                }
-            }
-            if(i>0&&j>0&&hash1[i].first==hash2[j].first&&hash1[i].second==hash2[j].second)
-            {
-                if(f[i][j][0]>f[i-1][j-1][0]+1)
-                {
-                    f[i][j][0]=f[i-1][j-1][0]+1;
-                    g[i][j][0]=-1;
-                }
-            }
-            int k1;
-            for(k1=0;k1<3;k1++)
-            {
-            	int k2;
-            	for(k2=0;k2<3;k2++)
-            	{
-            		if(f[i][j][k1]>f[i][j][k2]+1)
-                    {
-                        f[i][j][k1]=f[i][j][k2]+1;
-                        g[i][j][k1]=k2;
-                    }
-				}
-			}
-        }
-	}
-    que[++cnt]=makeqq(makepp(n1,n2),0);
-    while(que[cnt].first.first!=0||que[cnt].first.second!=0||que[cnt].second!=0)
-    {
-        int x=que[cnt].first.first;
-        int y=que[cnt].first.second;
-        int k=que[cnt].second;
-        if(g[x][y][k]!=-1)
-		{
-			k=g[x][y][k];
-		}
-        else if(k==0)
-		{
-			--x,--y;
-		}
-        else if(k==1)
-		{
-			--x;
-		}
-        else
-		{
-			--y;
-		}
-        que[++cnt]=makeqq(makepp(x,y),k);
-    }
-    for(i=cnt-1;i;i--)
-    {
-        int x=que[i].first.first;
-        int y=que[i].first.second;
-        int k=que[i].second;
-        if(g[x][y][k]!=-1)
-        {
-            if(g[x][y][k]==0)
-            {
-                if(k==1)
-				{
-					printf("#ifdef branch1\n");
-				}
-                else if(k==2)
-				{
-					printf("#ifdef branch2\n");
-				}
-            }
-			else
-            {
-                if(k==0)
-				{
-					printf("#endif\n");
-				}
-                else
-				{
-					printf("#else\n");
-				}
-            }
-        }
-		else
-        {
-            if(k==1)
-            {
-            	int ii;
-                for(ii=0;ii<len1[x];ii++)
-                {
-                	printf("%c",s1[x][ii]);
-				}
-                printf("\n");
-            }
-			else
-            {
-				int ii;
-                for(ii=0;ii<len2[y];ii++)
-                {
-                	printf("%c",s2[y][ii]);
-				}
-                printf("\n");
-            }
-        }
-    }
-    return 0;
-}
-</code>
-</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具