一般二维前缀和的递推公式为
```
flag[i][j]=flag[i-1][j]+flag[i][j-1]-flag[i-1][j-1]+a[i][j];
```
但是这个题遍历是三角形求前缀和,不是矩形。
而前缀和公式中 当前位置的数 需要正上方一个数来参加计算推导,但是三角形的最外围的数也就是flag[i][i]的上面一个数不会遍历到,且始终为0, 由前缀和知识可以知道此题的flag[i][i+1]一定等于flag[i][i]
故加一行代码flag[i][i+1]=flag[i][i];来保证后续递推前缀和不会出错
by xinglili @ 2023-10-09 18:32:03
```
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#define int long long
using namespace std;
int c[2010][2010],flag[2010][2010];
signed main()
{
int t,k,n,m;
cin>>t>>k;
//递推求组合数(杨辉三角)
for(int i=0;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;
//递推求前缀和
if(c[i][j]==0)flag[i][j]=flag[i-1][j]+flag[i][j-1]-flag[i-1][j-1]+1;
else flag[i][j]=flag[i-1][j]+flag[i][j-1]-flag[i-1][j-1]+0;
}
flag[i][i+1]=flag[i][i];//保证后续前缀和的递推正常
}
int ans;
while(t--)
{
cin>>n>>m;
if(m>n)cout<<flag[n][n]<<endl;
else cout<<flag[n][m]<<endl;
}
return 0;
}
```
by xinglili @ 2023-10-09 18:33:06
ฏ้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้
by Touris2ts @ 2024-01-04 14:06:48