|
题目描述 Description |
|
|
|
输入描述 Input Description |
|
从标准输入读入数据。 第一行有两个整数 t,k，其中 t 代表该测试点总共有多少组测试数据，k 的意义见问题描述。 接下来 t 行每行两个整数 n,m，其中 n,m的意义见问题描述。 |
|
输出描述 Output Description |
|
输出到标准输出。 tt 行，每行一个整数代表所有的 0≤i≤n,0≤j≤min(i,m) 中有多少对 (i,j)(满足 Cji 是 k 的倍数。 |
|
样例输入 Sample Input |
1 2 3 3 |
|
样例输出 Sample Output |
|
1 |
|
数据范围及提示 Data Size & Hint |
|
|
之前的一些废话：还有两周运动会，争取收获两块奖牌。后天要搞大事情。
题解：NOIP2016D2T1智障题，不要问我为什么去年只得了30分（无比悲惨的回忆）。组合数递推C(n,m)=C(n-1,m)+C(n-1,m-1)，然后取模，维护一个二维前缀和即可。
代码：
#include<iostream> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long LL; typedef pair<int,int> PII; #define mem(a,b) memset(a,b,sizeof(a)) inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c==‘-‘)f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-‘0‘;c=getchar();} return x*f; } const int maxn=2010; int T,K,c[maxn][maxn],sum[maxn][maxn],cnt[maxn][maxn]; int main() { T=read();K=read(); mem(c,-1); c[0][0]=1; for(int i=1;i<=2000;i++)c[i][0]=1,c[i][i]=1; for(int i=1;i<=2000;i++)for(int j=1;j<i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%K; for(int i=1;i<=2000;i++)for(int j=1;j<=2000;j++)sum[i][j]=sum[i][j-1]+(c[i][j]==0); for(int i=1;i<=2000;i++)cnt[1][i]=sum[1][i]; for(int i=1;i<=2000;i++)for(int j=1;j<=2000;j++)cnt[i][j]=cnt[i-1][j]+sum[i][j]; while(T--)printf("%d\n",cnt[read()][read()]); return 0; }
总结：去年的我是一个白痴。
原文：http://www.cnblogs.com/FYH-SSGSS/p/7538492.html
