【niop2016】【luogu2822】组合数问题

二维前缀和：小口诀：上加左减左上加自己

a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]

然后是杨辉三角即C(i,j)=C(i-1,j)+C(i-1,j-1)

for(int i=0;i<=n;i++)
{
    c[i][0]=1;
    for(int j=0;j<=i;j++)
    c[i][j]=c[i-1][j]+c[i-1][j-1];
}

还有一种来自刘汝佳大佬小粉书上的求法求C(n,k) C(n,k)=(n-k+1)/k*C(n,k-1) 然后就可以从C(n,0)=1开始递推

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3     int t,k;
 4     int a[2001][2001];
 5     int ans[2001][2001];
 6     int n[10001],m[10001];
 7 int main()
 8 {
 9     int x=0;
10     scanf("%d%d",&t,&k);
11     for (int i=1;i<=t;i++) 
12     {
13         scanf("%d%d",&n[i],&m[i]);
14         if (n[i]>x) x=n[i];
15     }
16     for (int i=1;i<=x;i++)
17     {
18         a[1][i]=i%k;
19         if (a[1][i]==0) ans[1][i]++;
20     }
21     for (int i=2;i<=x;i++)
22         for (int j=2;j<=i;j++)
23         {
24             a[j][i]=(a[j-1][i-1]+a[j][i-1])%k;
25             if (a[j][i]==0) ans[j][i]++;
26         }
27     for (int i=1;i<=x;i++)
28         for (int j=1;j<=x;j++)
29             ans[j][i]+=ans[j-1][i]+ans[j][i-1]-ans[j-1][i-1];
30     for (int i=1;i<=t;i++) printf("%d
",ans[min(n[i],m[i])][n[i]]);

100昏并不来自我二维前缀和+杨辉三角

还不如测试时美滋滋的不用二维前缀和的90分代码

 1 /*
 2 id:gww
 3 language:C--
 4   
 5 */
 6 #include<bits/stdc++.h>
 7 using namespace std;
 8 const int N=2000+10;
 9 int t,k,n,m;
10 int a[N][N];
11 bool sum[N][N];
12  
13 inline int rd()
14 {
15     int x=0,w=0;char ch=0;
16     while(!isdigit(ch)) w|=ch=='-',ch=getchar();
17     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
18     return w?-x:x;
19 }
20  
21 void build()
22 {
23     a[0][0]=1;
24     for(int i=1;i<=2000;i++)
25     {
26         a[i][0]=1;
27         for(int j=1;j<=i;j++)
28         {
29             a[i][j]=(a[i-1][j-1]+a[i-1][j])%k;
30             if(!a[i][j]) sum[i][j]=1;
31         }
32     }
33 }
34  
35 int main()
36 {
37     t=rd(),k=rd();
38     memset(a,0,sizeof(a));
39     memset(sum,0,sizeof(sum));
40     build();
41     while(t--)
42     {
43         int ans=0;
44         n=rd(),m=rd();
45         if(n<m) m=n;
46         for(int i=0;i<=n;i++)
47         for(int j=0;j<=m;j++)
48         if(sum[i][j])ans++;
49         printf("%d
",ans);
50     }
51     return 0;
52 }

90昏未用二维前缀和

我？我也不知道我错哪了反复错错错各种玄学错误

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=2000+10;
 4 int c[N][N],sum[N][N];
 5 int t,k,n[N],m[N],nn=0;
 6  
 7 inline int rd()
 8 {
 9     int x=0,w=0;char ch=0;
10     while(!isdigit(ch)) w|=ch=='-',ch=getchar();
11     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
12     return w?-x:x;
13 }
14  
15 void build()
16 {
17     for(int i=0;i<=nn;i++)
18     c[i][0]=c[i][i]=1;
19     for(int i=2;i<=nn;i++)
20     for(int j=1;j<=i;j++)
21     c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
22 }
23  
24 int main()
25 {
26     memset(c,0,sizeof(c));
27     memset(sum,0,sizeof(sum));
28     t=rd(),k=rd();
29     for(int i=1;i<=t;i++)
30     {
31         n[i]=rd(),m[i]=rd();
32         if(n[i]<m[i]) m[i]=n[i];
33         nn=max(nn,n[i]);
34     }
35     build();
36     for(int i=2;i<=nn;i++)
37     {
38         for(int j=1;j<=nn;j++)
39         {
40             sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]);//上加左  减左上 加自己
41             if(!c[i][j]) sum[i][j]++;
42         }
43         sum[i][i+1]=sum[i][i];
44     }
45     for(int i=1;i<=t;i++) printf("%d
",sum[n[i]][m[i]]);
46     return 0;
47 }

50昏不知道哪的玄学错误

我是个弟弟