https://www.luogu.org/problem/show?pid=2822 天哪,我水题都不会做了; 太可怕了; 一道dp题披上了数论的的大衣; 就是先搞个杨辉三角+取模; 然后直接矩形前缀和; 我他妈想了半天的数论。。。。。。 Fop_zz说他当年10直接做好了; …………
#include<map> #include<cmath> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> using namespace std; int f[2005][2005],d[2005][2005]; int n,m,t,k,ans; void make(){ memset(f,-1,sizeof f); for(int i=1;i<=2000;i++) for(int j=0;j<=i;j++) if(j==0||j==i)f[i][j]=1%k;else f[i][j]=(f[i-1][j]+f[i-1][j-1])%k; for(int i=1;i<=2000;i++) for(int j=1;j<=2000;j++) d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+(int)(f[i][j]==0); } int main() { scanf("%d%d",&t,&k); make(); while(t--){ scanf("%d%d",&n,&m); printf("%d\n",d[n][m]); } }