2 条题解

  • 3
    @ 2023-4-27 23:24:09

    距离上一次写题解已经过了十个甚至九个月了,中间的课是都不会啊!!!(恼)

    免责声明

    本篇题解所写内容均为个人想法,并不代表且可能完全与代老师的标准思路、答案无关。若遇到此种情况,以英明神武帅气的代老师的代码为准。本人代码仅供参考。

    组合数问题

    一:组合数处理

    如题目所说,组合数求解是有最基本的公式的。但是这个公式上下都是阶乘,一次次算肯定十分的浪费时间。因此需要考虑到一定的优化。

    观察题目数据范围可以发现,n只有2000!!!多么的小啊!!!!因此我们肯定可以把全部的组合数算出来,然后每次求解的时候再考虑求和问题。直接上二维数组记录一下C[i][j]。

    ps:我一开始以为开longlong空间不够,故补上计算结果:

    2000 * 2000 * 8 / 1024 / 1024 = 30.517MB

    显而易见的,可以利用数论中的杨辉三角的递推式来求解。每次都利用之前求过的C来求解本次的。由于公式的markdown对于本蒟蒻十分的难写,故给出wiki传送门:

    组合数学 | 33Wiki (33dai.cn)

    线性求出后,每次用n2的复杂度统计,整体复杂度是O(n2t),1010级别,肯定过不了。因此我们需要考虑再次优化求和时候的平方级复杂度。

    当然,如果不优化,也有70pts,加个取模操作90pts。

    二:前缀和优化

    考虑每次求和做的事情,其实就是在杨辉三角中找出当前这个点左上角那一部分的 C[i][j]%k==0 的数字数量只和。我们可以在脑子里构建一个新的二维bool数组,如果是当前位置是1表示这个地方的C可以被整除,为最终的结果提供1的贡献。所以最终就是将这样的一个表进行二维前缀和(求和)操作。将每次询问复杂度优化为O(1),故最终复杂度是O(n2)。

    当然,这个表其实并不需要真的建出来。它的功能可以和前缀和的数组相结合。假设前缀和数组是d,则可以得到以下的公式:

    d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+(c[i][j]==0);

    如图所示,相信可以给忘记了二维前缀和的同学们(包括我)提供一些想法。轻轻敲醒沉睡的心灵

    image

    左图为取模k(假设k=5)时的杨辉三角。右图为根据贡献画出来的树。如果我们要求白框位置为右下角的一整个图形面积,就是 上方红框+左侧红框-左上方篮框 的1的总数量,加上自己这个位置是否是1,因此就是上方的公式。

    三:上代码!

    部分小细节在代码中注释给出,最终就可以得到如下代码:

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int MAXN=2005;
    int t,k,n,m;
    int c[MAXN][MAXN],d[MAXN][MAXN];
    void C_init(int x,int y)
    {
    	c[0][0]=1; //最上方的数字初始化为0 
    	for(int i=1;i<=x;i++)
    	{
    		c[i][0]=1;
    		for(int j=1;j<=min(i,y);j++)
    			c[i][j]=(c[i-1][j]%k+c[i-1][j-1]%k)%k;//公式 
    		//每次求的时候就取模,更加方便 
    	}
    	return;
    }
    void qzh(int x,int y)
    {
    	for(int i=0;i<=x;i++)
    	{
    		for(int j=0;j<min(i,y);j++)
    		{
    			if(i==0&&j==0)//如果是左上角的位置,只需要加自己 
    				d[i][j]=(c[i][j]==0);
    			else if(i==0)//如果是第0行,i轴不变 
    				d[i][j]=d[i][j-1]+(c[i][j]==0);
    			else if(j==0)//如果是第0列,j轴不变,只加i轴 
    				d[i][j]=d[i-1][j]+(c[i][j]==0);
    			else//正常的前缀和公式 
    				d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+(c[i][j]==0);
    		}
    		d[i][min(i,y)]=d[i][min(i,y)-1]+(c[i][min(i,y)]==0);
    		//特殊判断,将最右侧的值赋为左侧的值加上自己
    		//因为最右侧的实际上就等于左侧的矩形,但是它上方矩形的数值为0
    		//所以直接加的答案会错误,需要特殊处理 
    	}
    	return;
    }
    signed main()
    {
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cin>>t>>k;
    	C_init(2000,2000); //线性求组合数函数 
    	qzh(2000,2000); //二维前缀和 
    	while(t--)
    	{
    		cin>>n>>m;
    		cout<<d[n][min(n,m)]<<'\n';
    		//注意,上方只做出了三角形形状的前缀和图形,但是题目中并没有保证m<n
    		//因此,第二维应该是min(n,m),比如在6个数里选10个,答案数等同于6个里选6个 
    	}
    	return 0;	
    }
    
    • 0
      @ 2023-4-27 21:59:42

      前缀和

      #include<bits/stdc++.h>
      using namespace std;
      int T,k,n,m;
      int c[2005][2005];
      int sum[2005][2005];
      int main()
      {
      	ios::sync_with_stdio(false);
      	cin.tie(0);
      	cin>>T>>k;
      //组合数求解
      	for(int i=0;i<=2001;i++)
      		for(int j=0;j<=i;j++)
      			if(i==0||i==j)
      				c[i][j]=1;
      			else
      				c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
      //二维前缀和求解
      	for(int i=1;i<=2001;i++)
      		for(int j=1;j<=2001;j++)
      			if(c[i][j]==0&&j<=i)//注意算组合数时满足j<=i
      				sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+1;
      			else
      				sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];
      	while(T--)
      	{
      		cin>>n>>m;
      		cout<<sum[n][m]<<"\n";
      	}
      	return 0;
      }
      
      • @ 2023-4-28 17:27:29

        可以在```后面加个cpp,这样字体就有C++的格式的颜色了

      • @ 2023-4-28 17:34:12

        原来如此,太巨了!!!谢谢陈巨大佬的浇浇!!!@

    • 1

    信息

    ID
    150
    时间
    1000ms
    内存
    512MiB
    难度
    7
    标签
    递交数
    48
    已通过
    12
    上传者