2559. [NOIP2016]组合数问题
【题目描述】
【输入格式】
从文件中读入数据。
第一行有两个整数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输出】
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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-05-24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录