~~这么晚了还不睡啊~~【滑稽】
by XMK_萌新 @ 2019-03-07 00:03:42
@[sunzhen](/space/show?uid=179811)
用杨辉三角递推,不要用定义,除法在取模条件下不能用。
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Mod=19260817;
const int MAX_N=1005;
int C[MAX_N][MAX_N];
int sum[MAX_N][MAX_N];
signed main()
{
for(int i=1;i<MAX_N;i++)
{
C[i][0]=C[i][i]=1;
}
for(int i=1;i<MAX_N;i++)
{
for(int j=1;j<i;j++)
{
C[i][j]=C[i-1][j-1]+C[i-1][j];
C[i][j]%=Mod;
}
}
for(int i=1;i<MAX_N;i++)
{
for(int j=1;j<MAX_N;j++)
{
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+C[i][j];
sum[i][j]%=Mod;
if(sum[i][j]<0)sum[i][j]+=Mod;
}
}
int Q;
cin>>Q;
while(Q--)
{
int n,m;
cin>>n>>m;
cout<<sum[m][n]<<endl;
}
return 0;
}
```
by Smile_Cindy @ 2019-03-07 08:51:07
```cpp
void yang()
{
//构造杨辉三角
int x=1;
for(int i=1;i<=max_n;i++,x++)
{
for(int j=x;j<=max_n;j++)
{
if(i==1)yanghui[i][j]=j;
else if(i==j)yanghui[i][j]=1;
else yanghui[i][j]=(yanghui[i][j-1]+yanghui[i-1][j-1])%19260817;
}
}
}
```
```cpp
for(int n=1;n<=1000;n++)
{
for(int m=1;m<=1000;m++)
{
yh[n][m]=(yh[n][m-1]+yh[n-1][m]-yh[n-1][m-1]+19260817+yanghui[n][m])%19260817;
}
}
```
by sunzhen @ 2019-03-07 14:50:35
```cpp
/*for(int i=1;i<=max_n;i++)
{
for(int j=1;j<=max_n;j++)
{
cout<<data[i][j]<<' ';
}
cout<<'\n';
}
for(int i=1;i<=max_n;i++)
{
for(int j=1;j<=max_n;j++)
{
cout<<sum[i][j]<<' ';
}
cout<<'\n';
}*/
```
by sunzhen @ 2019-03-07 18:29:37
```cpp
#include<bits/stdC++.h>
using namespace std;
typedef long long ll;
const int max_n=1000,p=19260817;
ll data[max_n][max_n],sum[max_n][max_n];
inline void fun()
{
for(int i=1;i<=max_n;i++)
{
for(int j=i;j<=max_n;j++)
{
if(i==1)data[i][j]=j;
else if(i==j)data[i][j]=1;
else data[i][j]=(data[i][j-1]+data[i-1][j-1])%p;
}
}
}
inline void f()
{
for(int i=1;i<=max_n;i++)
{
for(int j=1;j<=max_n;j++)
{
sum[i][j]=(sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+p+data[i][j])%p;
}
}
}
int main()
{
fun();
f();
int x,y,n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
cout<<sum[x][y]<<'\n';
}
return 0;
}
```
by sunzhen @ 2019-03-07 18:30:17
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=1000,p=19260817;
ll data[1005][1005];
ll end1[1005][1005];
void fun()
{
for(int i=1;i<=max_n;i++)
{
for(int j=i;j<=max_n;j++)
{
if(i==1)data[i][j]=j;
else if(i==j)data[i][j]=1;
else data[i][j]=(data[i][j-1]+data[i-1][j-1])%p;
}
}
}
int main()
{
fun();
memset(end1,0,sizeof(end1));
end1[1][1]=1;
for(int n=1;n<=max_n;n++)
{
for(int m=1;m<=max_n;m++)
{
if(n>1&&m>1)end1[n][m]=(end1[n-1][m]+end1[n][m-1]-end1[n-1][m-1]+p+data[n][m])%p;
else if(n>1&&m==1)end1[n][m]=(end1[n-1][m]+data[n][m])%p;
else if(n==1&&m>1)end1[n][m]=(end1[n][m-1]+data[n][m])%p;
}
}
int x,y,n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
cout<<end1[x][y]<<'\n';
}
return 0;
}
```
by sunzhen @ 2019-03-07 19:44:27
终于ac了,感谢各位大佬
还想问个问题
```cpp
if(n>1&&m>1)end1[n][m]=(end1[n-1][m]+end1[n][m-1]-end1[n-1][m-1]+p+data[n][m])%p;
else if(n>1&&m==1)end1[n][m]=(end1[n-1][m]+data[n][m])%p;
else if(n==1&&m>1)end1[n][m]=(end1[n][m-1]+data[n][m])%p;
```
在二维前缀和计算的时候是不是应该这样防止越界?
我先把整个数组初始化为0,但是不这样防越界的话在第0行和第0列出现了奇怪的值,我初始化过了应该是0啊?
by sunzhen @ 2019-03-07 19:47:37
@[Alpha](/space/show?uid=87058)
by sunzhen @ 2019-03-07 19:48:01
@[sunzhen](/space/show?uid=179811)
如果不防越界就会出现负数下标,负数下标对应的地址不在数组范围内,是一个随机值。
by Smile_Cindy @ 2019-03-07 19:57:27