@[shenwentao](/user/790898) 你需要在处理 $c$ 数组的时候预处理出来 $ans$ 数组啊,不能每一次询问都去做一次前缀和,时间复杂度是 $O(nmT)$的
by keep_of_silence @ 2024-02-07 10:34:35
@[keep_of_silence](/user/567247) 额···本人不太理解,可以具体讲解一下吗
by shenwentao @ 2024-02-07 10:44:26
@[shenwentao](/user/790898) 给你改一下吧,等一下
by keep_of_silence @ 2024-02-07 10:46:19
@[shenwentao](/user/790898)
```
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
#define int long long
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
using namespace std;
int t,k;
int n,m,ans[2010][2010];
int c[2010][2010];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
//freopen("P2822_13.in","r",stdin);
//freopen("xxx.out","w",stdout);
cin>>t>>k;
c[1][1]=1;
c[0][0]=c[1][0]=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]+c[i-1][j-1])%k;//处理c
}
}
for(int i=2;i<=2000;i++)
{
for(int j=1;j<=i;j++)
{
ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
ans[i][j]+=(c[i][j]==0);
}
ans[i][i+1]=ans[i][i];
}//对于每一个n,m处理出相应的答案,存下来,询问的时候直接查询
while(t--)
{
cin>>n>>m;
cout<<ans[n][min(n,m)]<<endl;
}
return 0;
}
```
by keep_of_silence @ 2024-02-07 10:53:52
@[keep_of_silence](/user/567247) 好像有点明白,感谢大佬帮助
by shenwentao @ 2024-02-07 10:56:57