第一行有两个整数 t,kt,k，其中 tt 代表该测试点总共有多少组测试数据，kk 的意义见问题描述。

接下来 tt 行每行两个整数 n,mn,m，其中 n,mn,m 的意义见问题描述。

说明/提示

我们知道，在二项式定理中，每一项的二项式系数都相应的对应着杨辉三角的某一行

如图：

本题的测试点只在2000的范围内，所以可以打表，将2000以内的排列数全部求出来。

之后如果用二次遍历来排查能不能整除，复杂度会比较大，会有可能爆时间（事实上也爆时间了），只能得90分，

但是，可以用求前缀和来简化，

 本题的前缀和公式也相应地是：s[x][y]=b[x-1][y]+b[x][y-1]-b[x-1][y-1] ；

代码如下：

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<math.h>usingnamespacestd; int k,a[5000][5000]; int s[5000][5000]; void st(int k) { a[1][1]=1; for(int i=1;i<=2000;i++) { a[i][0]=1; } for(int i=2;i<=2000;i++) { for(int j=1;j<=i;j++) { a[i][j]=(a[i-1][j-1]%k+a[i-1][j]%k)%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(a[i][j]==0) { s[i][j]++; } } s[i][i+1]=s[i][i]; } } int main(void) { int t,k; cin>>t>>k; st(k); while(t--) { int n,m; cin>>n>>m; if(m>n) cout<<s[n][n]<<endl; elsecout<<s[n][m]<<endl; } return0; }

这里相应的，只要输出s[n][m]，即输出前缀和，即可得到正确答案。

这里的优化，最关键的就是这里的前缀和求值，重在理解！！！

可以理解为：

用局部面积之和，再加上自己，减去重复的地方，即得前缀和。