题目描述

输入格式

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

输出格式

t行，每行一个整数代表答案。

样例输入

输入样例#1： 1 2 3 3 输入样例#2： 2 5 4 5 6 7

样例输出

输出样例#1： 1 输出样例#2： 0 7

说明

【样例1说明】在所有可能的情况中，只C(2,1)=2是2的倍数。 【子任务】

题目分析

水题，杨辉三角前缀和秒过

源代码

#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } int t,n,m,k,f[2005][2005],sum[2005][2005]; void Get_C() { for(int i=1; i<=2000; i++) { f[i][i]=1; f[i][1]=i%k; for(int j=2; j<i; j++) f[i][j]=(f[i-1][j]%k+f[i-1][j-1]%k)%k; } } int main() { t=Get_Int(); k=Get_Int(); Get_C(); for(int i=1; i<=2000; i++) //杨辉三角前缀和 for(int j=1; j<=i; j++) if(f[i][j]==0)sum[i][j]=sum[i][j-1]+1; else sum[i][j]=sum[i][j-1]; for(int i=1; i<=t; i++) { int ans=0; n=Get_Int(); m=Get_Int(); for(int i=1; i<=n; i++)ans+=sum[i][min(i,m)]; printf("%d\n",ans); } return 0; }