洛谷 p2822

访问了数组的边界而卡了快一个小时
谨记

我们要求(n,m)内的(inom{j}{i})为k的倍数即为在模k的意义下为0

利用公式

[inom{n}{m}=inom{n-1}{m-1}+inom{n}{m-1} ]

就可以在(O(n^2))算出所有的(inom{i}{j})(模k意义下)

再利用二维前缀和来求的n,m以内的满足为0的(inom{i}{j})最后面对问题进行(O(1))的查询

#include<bits/stdc++.h> 

#define ll  long long 
using namespace std;

const int maxn = 2010;

int c[maxn][maxn];
int s[maxn][maxn];


int main()
{
	int t,k;
	cin >> t >>k;
	for(int i=0;i<maxn;++i)	c[i][0] = 1,c[i][i]=1;
	for(int i=2;i<maxn;++i)
	{
		for(int j=1;j<=i;++j)
		{
			c[i][j] = (c[i-1][j]+c[i-1][j-1])%k;
		}
	}
	for(int i=2;i<maxn;++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]+=1;
		}
		s[i][i+1] = s[i][i]; 
	}
	for(int i=0;i<t;++i)
	{
	
		int n,m;
		scanf("%d%d",&n,&m);
		printf("%d
",s[n][m>n?n:m]);
		
	}

	return 0;
} 

再写一下二维前缀和公式

[sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] ]