NOIP2016--day2 总结&&题解

T1–组合数问题

.
.
.
一开始看到这题目，哎呀，懵逼数学题。然后…,不管了打个表找个规律先。
然后发现用2000*2000的数组存下所有组合数不是不行，然后突然又想到，这么大的数字，long long 也会爆啊，然后，猛然发现可以对每一个组合数进行取模。
所以我们需要的公式是$ac[i][j]=( c[i-1][j-1] +c[i-1][j] )\%k$ac[i][j]=(c[i−1][j−1]+c[i−1][j])%k
这不就是杨辉三角的公式嘛！！！！

然后…,开开心心一发暴力求每一组询问
好了 90分
emmmmmmmmmm
.
.
.
.
好了说正解，用二维前缀和存下对于每一个n,m对应的答案，然后$O(n)$O(n)查询，好了，AC。
上代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#define LL long long
using namespace std;
int c[2010][2010],s[2010][2010],n,m,k,t;
void first()
{
	c[0][0]=1;
	c[1][1]=1;
	for(int i=1;i<=2000;i++)
	{
		c[i][0]=1;
	}
	for(int i=2;i<=2000;i++)
	{
		for(int j=1;j<=i;j++)
		{
			c[i][j]=( c[i-1][j-1] +c[i-1][j] )%k;
		}
	}
	
	for(int i=2;i<=2000;i++)
	{
		for(int j=1;j<=i;j++)
		{
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
			if(c[i][j]==0) s[i][j]++;
		}
		s[i][i+1]=s[i][i];
	}
}
int main()
{
	//freopen("problem.in","r",stdin);
	//freopen("problem.out","w",stdout);
	memset(s,0,sizeof(s));
	memset(c,0,sizeof(c));
	scanf("%d %d",&t,&k);
	first();
	while(t)
	{
		t--;
		scanf("%d %d",&n,&m);
		if(n<m) m=n;//很重要 
		printf("%d\n",s[n][m]);
	}
	return 0;
}