我们先预处理出2000行的杨辉三角（val[i][j]=val[i-1][j]+val[i-1][j-1]）
预处理的时候，我们可以把每个值%k，若为0，即为k的倍数。
然后对于每一行，做一个前缀和，统计这一行的前i个里面是k的倍数的数的个数。
然后对于每个询问，我们 For (i:1->n) ans+=sum[i][min(i,m)] 即可。
附上AC代码
#include#include #include #include #include using namespace std;template inline void read(T &_a){ bool f=0;int _ch=getchar();_a=0; while(_ch<'0' || _ch>'9'){ if(_ch=='-')f=1;_ch=getchar();} while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();} if(f)_a=-_a;}int n,m,k,T,mp[2001][2001],sum[2001][2001];inline void init(){ mp[1][0]=mp[1][1]=1; for (register int i=2;i<=2000;++i) { mp[i][0]=1; for (register int v=1;v<=i;++v) mp[i][v]=(mp[i-1][v]+mp[i-1][v-1])%k; for (register int v=1;v<=i;++v) sum[i][v]=sum[i][v-1]+(mp[i][v]==0?1:0); }}int main(){ read(T); read(k); init(); while(T--) { read(n); read(m); int ans=0; for (register int i=1;i<=n;++i) ans+=sum[i][min(i,m)]; printf("%d\n",ans); } return 0;}