我们先考虑暴力，暴力枚举每一个\(i,j\)暴力算\(\binom{i}{j}\)
时间复杂度为\(O(T*N^3)\)，显然超时
然后我们发现\(N,M \le2000\)
我们考虑使用组合数的递推公式预处理\(\binom{0}{0}\)到\(\binom{2000}{2000}\)。
这里说一下组合数递推公式\(\binom{i}{j}=\binom{i-1}{j-1}+\binom{i-1}{j}\)
可以从组合意义上来理解 我们从\(i\)个数中选\(j\)个数，对于每一个数可以分为选与不选两种情况，选的时候即\(\binom{i-1}{j-1}\),在剩下的\(i-1\)个数里选\(j-1\)个数，不选的时候即\(\binom{i-1}{j}\)，在剩下的\(i-1\)个数里选出\(j\)个数.
但是这样复杂度为\(O(T*N^2+N^2)\)，依旧无法通过，事实上我们需要一种不需要枚举\(i,j\)的方法才能通过。
我们发现对于多个询问，\(k\)始终为定值，于是考虑前缀和优化，设\(ans_{i,j}\)，在预处理时，若\(k|\binom{i}{j}\),则将\(ans_{i,j}+1\)。然后套用二维前缀和。但是我们发现，二维前缀和递推时 \(ans_{i,j}=ans_{i-1,j}+ans_{i,j-1},-ans_{i-1,j-1}+[k|\binom{i}{j}]\)，在处理到边界时，我们会用未处理的值(因为此时\(i<j\))来更新。
但是我们又发现
对于所有的 \(0\leq i\leq n,0\leq j\leq \min \left ( i, m \right )\) 有多少对 \((i,j)\) 满足 \(k|\binom{i}{j}\)
于是我们直接将未处理的值设为同一行上一个值
由此即可AC这道题了!
点我展开看代码
```cpp#include <bits/stdc++.h>using namespace std;#define int long longint t,n,m,k,c[2008][2008],ans[2008][2008];void init(){c[0][0]=1;c[1][0]=c[1][1]=1;for(int i=2;i<=2000;i++){c[i][0]=1; for(int j=1;j<=i;j++){c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];if(c[i][j]==0){ans[i][j]++;} }ans[i][i+1]=ans[i][i]; }}signed main(){cin>>t>>k;init(); while(t--){cin>>n>>m;if(n<m){cout<<ans[n][n]<<"\n";} else{cout<<ans[n][m]<<"\n"; }}return 0;}
```