今天HMR大佬给我们讲解了这一道难题。
基本思路是：
可以将问题转化为：求出杨辉三角，用二维数组f[i][j]来表示在杨辉三角中以第i行第j列的点为右下角，第0行第0列处的点为左上角的矩阵中所有元素是k的倍数的个数；
那么这样一来f[i][j]的状态转移方程为：f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-1]
这个方程的意思是以第i行第j-1列的点为右下角的矩阵中的元素是k的倍数的个数+以第i-1行第j列的点为右下角的矩阵中的元素是k的倍数的个数-以第i-1行第j-1列的点为右下角的矩阵中的元素是k的倍数的个数，如果不减去f[i-1][j-1]的话就会多加上那一块重复的。
这是大佬的AC代码：
#include<iostream> #include<cstring> #include<cstdio> #include<cctype> #define ll long long #define gc() getchar() #define maxn 2005 using namespace std; inline ll read(){ //快读 ll a=0;int f=0;char p=gc(); while(!isdigit(p)){f|=p=='-';p=gc();} while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();} return f?-a:a; } void write(ll a){ if(a>9)write(a/10); putchar(a%10+'0'); } int t,k,c[maxn][maxn],f[maxn][maxn]; int main(){ t=read();k=read(); for(int i=0;i<=2000;++i)c[i][0]=1; for(int i=1;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=1;i<=2000;++i){ for(int j=1;j<=i;++j){ f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]; //状态转移方程 if(!c[i][j])f[i][j]++; } f[i][i+1]=f[i][i]; } for(int i=1;i<=t;++i){ int n=read(),m=read(); if(m>n)m=n; write(f[n][m]); putchar(' '); } return 0; }