【题解】P2822 组合数问题

仅以此题,纪念我的智障

先把注意点说了:C(0,0)=1;C(1,0)=1;C(1,1)=1;C(2,0)=1;C(2,1)=2;C(2,2)=1
列成数组就是

n\m012345
01~~~~~
111~~~~
2121~~~
31331~~
414641~
515101051

解题思路

1.看到 $C_{n}^m$ 不难想到可以用杨辉三角做这道题。

2.由于是超多次询问,又不难想到这道题用前缀和。

3.由于询问是二维的,不难想到用二维的前缀和。

然后一般人就能做出来了。。。

但是我并不是一般人。看了dalao的题解后想了一个多小时。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

才发现原来C(1,2)原来是2,并不是1 这是什么清奇的思路

于是就过了

对了,二维前缀和好像还没讲

二位前缀和

先来一幅图自己体会一下

二位前缀和 (2)_LI.jpg

白色部分=整个长方形-两个灰色长方形+黑色部分(黑色部分是两个灰色长方形的重叠部分)

这道题是上述结论的变形
整个长方形=两个灰色长方形-黑色部分+白色部分

代码

#include<bits/stdc++.h>
using namespace std;
int c[2005][2005];
int ans[2005][2005];
int main(){
    int t,k;
    cin>>t>>k;
    int n,m;
    c[1][3]=1;
    for(int i=0;i<2005;i++){
        c[i][0]=1;  //栽在这个循环。。。
    }
    for(int i=2;i<2005;i++){
        for(int j=1;j<=i;j++){
            c[i][j]=c[i-1][j]+c[i-1][j-1];
            c[i][j]%=k;
        }
    }
    for(int i=2;i<2005;i++){
        for(int j=1;j<=i;j++){
            ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
            if(c[i][j]==0){
                ans[i][j]++;
            }
        }
        ans[i][i+1]=ans[i][i];
    }
    for(int i=0;i<t;i++){
        cin>>n>>m;
        m=min(m,n);
        cout<<ans[n][m]<<endl;
    }
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/538/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者