首页 > > 程序设计 > C/C++ >

2559. [NOIP2016]组合数问题

2018-06-17 22:30:15来源：未知阅读 ()

【题目描述】

【输入格式】

从文件中读入数据。

第一行有两个整数t, k，其中t代表该测试点总共有多少组测试数据，k的意义见【问题描述】。

接下来t行每行两个整数n, m，其中n, m的意义见【问题描述】。

【输出格式】

输出到文件中。

t行，每行一个整数代表所有的0<=i<=n,0<=j<=min(i,m)中有多少对(i, j)满足C(j,i)是k的倍数。

【样例1输入】

1 2
3 3

【样例1输出】

【提示】

在所有可能的情况中，只有C(1,2)是2的倍数。

【样例2输入】

2 5
4 5
6 7

【样例2输出】

0
7

【来源】

NOIP2016 官方数据、

这道题几天之前在我眼里还是懵逼的

不过今天我们学习了一个公式

C下n+1上m=C下n上m-1+C下n上m、

本来只想推推看看，后来一推就是55

然后加了个%k是90

后来实在做不出来了看了看大神的题解原来可以用前缀和

如此看来noip2016的题也不是很难啊，

 1     #include<iostream>
 2     #include<cstdio>
 3     #include<cstring>
 4     #include<cmath>
 5     using namespace std;
 6     const int MAXN=2001;
 7     int T,k,n,m;
 8     int dp[MAXN][MAXN];
 9     int read(int & n)
10     {
11         int flag=0,x=0;char c='/';
12         while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
13         while(c>='0'&&c<='9')x=x*10+(c-48),c=getchar();
14         if(flag)n=-x;else n=x;
15     }
16     int main()
17     {
18         freopen("problem.in","r",stdin);
19         freopen("problem.out","w",stdout);
20         read(T);read(k);
21         for(int i=0;i<=2001;i++)
22         dp[i][0]=1,dp[i][i]=1;
23         for(int i=0;i<=2001;i++)
24             for(int j=0;j<=2001;j++)
25                 if(dp[i+1][j]==0)
26                 dp[i+1][j]=(dp[i][j]+dp[i][j-1]);
27         
28         while(T--)
29         {
30             read(n);read(m);
31             int ans=0;
32             for(int i=1;i<=n;i++)
33                 for(int j=1;j<=min(i,m);j++)
34                     if(dp[i][j]%k==0)
35                         ans++;
36             printf("%d\n",ans);
37         }
38         return 0;
39     }

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define LL long long 
 6 using namespace std;
 7 const int MAXN=2003;
 8 int T,k,n,m;
 9 LL dp[MAXN][MAXN];
10 LL sum[MAXN][MAXN];
11 int read(int & n)
12 {
13     int flag=0,x=0;char c='/';
14     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
15     while(c>='0'&&c<='9')x=x*10+(c-48),c=getchar();
16     if(flag)n=-x;else n=x;
17 }
18 int main()
19 {
20     freopen("problem.in","r",stdin);
21     freopen("problem.out","w",stdout);
22     
23     read(T);read(k);
24     for(int i=1;i<=2002;i++)
25     dp[i][i]=1,dp[i][1]=i%k;
26     for(int i=0;i<=2002;i++)
27         for(int j=2;j<i;j++)
28             dp[i][j]=(dp[i-1][j]%k+dp[i-1][j-1]%k)%k;
29     
30     /*for(int l=0;l<=50;l++)
31         for(int j=0;j<=l;j++)
32             cout<<dp[l][j];
33         cout<<endl;*/
34         //cout<<dp[1][2];
35     
36     for(int i=1;i<=2002;i++)
37         for(int j=1;j<=i;j++)
38         {
39             if(dp[i][j]==0)sum[i][j]=sum[i][j-1]+1;// 满足条件 
40             else sum[i][j]=sum[i][j-1]; 
41         }
42     
43     while(T--)
44     {
45         read(n);read(m);
46         LL ans=0;
47         for(int i=1;i<=n;i++)
48             ans+=sum[i][min(i,m)];
49         cout<<ans<<endl;
50         //printf("%d\n",sum[n][min(n,m)]);
51     }
52     return 0;
53 }