自动搬运

查看原文

来自洛谷，原作者为

	Social_Zhao 悲しくって 泣いてるわけじゃあない

搬运于2025-08-24 22:08:34，当前版本为作者最后更新于2019-03-02 19:03:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Updated at 2019/3/2/21:56，重新发表

（实际上是发表后几小时，有一位大佬

https://www.luogu.org/space/show?uid=79067

权））

看了诸位大佬的题解，蒟蒻一脸懵逼

难道我写出了本题最短代码？？？

毕竟是自己YY出的野递推式

• 首先来看张表：（没错这就是我用暴力打出来的表的一部分，下标从1开始）

• 请自行脑补行号、列号（逃

• 于是精通找规律的本蒟蒻看出一个递推公式来

• 再说这个公式前，先举几个栗子。

• 对于第2行2列的数：4，它其实是它左上角的数1加上它上方的数1再加上它的行号2
• 对于第2行3列的数：10，它其实是它左上角的数3加上它上方的数4再加上它的行号3
• 对于第5行5列的数：57，它其实是它左上角的数26加上它上方的数26再加上它的行号5
• 特殊情况——对于1行m列的数1，它其实是它左上角的数（初始化为0）加上它上方的数（初始化为0）再加上它的行号1
• 以及——对于n行1列的数1，它其实是它左上角的数（初始化为0）加上它上方的数（初始化为0）再加上它的行号1

• 我想这五个例子应该足以说明问题了吧？下面就是我的递推式：

• $ans[i][j]=ans[i-1][j-1]+ans[i-1][j]+i$

下面是推导过程，看不懂可以自行跳过

为毛是这样的 ？

感谢@dou_bao大佬的解释。（已获得原作者授权）

我们需要三张表

1.帕斯卡三角形（即杨辉三角）（数组$f$）

• 首先，我们需要知道$C(x,y)$等于帕斯卡三角形第$y+1$行第$x+1$个数。不知道的回家洗洗睡吧，我就不证明了

• 所以从$C(1,y)$到$C(i,y)$就是第$y+1$行第$1$到$i+1$个的数之和。

• 所以题中所求的可以表示为

for(int i=1;i<=x;i++)
    for(int j=2;j<=y;j++)
        ans+=f[i][j];

• 不超时个鬼，所以要压缩

• 所以第二张表

2.帕斯卡三角形的前缀和（横着的）（不包括每行第一个数1）（数组$g$）

| 1 | 1 | 1 | 1 | 1 | 1 | | :----: | :----: | :----: | :----: | :----: | :----: | :----: | :----: | | 2 | 3 | 3 | 3 | 3 | 3 | | 3 | 6 | 7 | 7 | 7 | 7 | | 4 | 10 | 14 | 15 | 15 | 15 | | 5 | 15 | 25 | 30 | 31 | 31 | | 6 | 21 | 41 | 56 | 62 | 63 |

• 一个矩阵变成一行了。

• 因为$f[i][j]=f[i-1][j]+f[i-1][j-1];$

• 所以$g[i][j]$就等于$g[i-1][j]+g[i-1][j-1]+1$(把$g[i][j]=sum(f[1]$ to $f[i])$展开就可以得到，实在无法理解可以在表中找规律)

• 俗话说的好，做事要干净，不给别人留后路。

• 所以第三张表

3.帕斯卡三角形横着的前缀和的前缀和（竖着的）（数组$ans$）

| 1 | 1 | 1 | 1 | 1 | 1 | | :----: | :----: | :----: | :----: | :----: | :----: | :----: | :----: | | 3 | 4 | 4 | 4 | 4 | 4 | | 6 | 10 | 11 | 11 | 11 | 11 | | 10 | 20 | 25 | 26 | 26 | 26 | | 15 | 35 | 50 | 56 | 57 | 57 | | 21 | 56 | 91 | 112 | 119 | 120 |

• 是不是和第一张表一模一样？
• 那么很明显 $ans[i][j]=ans[i-1][j]+g[i][j]$
• 又因为之前的$g[i][j]=g[i-1][j]+g[i-1][j-1]+1$
• 所以$ans[i][j]=ans[i-1]+g[i-1][j]+g[i-1][j-1]+1$
• 再不断地拆$g[i-1][j]$
• 就得到了$ans[i][j]=ans[i-1][j]+g[0$ to $i-1][j-1]+i$
• 然后又因为h的定义，所以$ans[i][j]=g[0$ to $i][j]$
• 那么可以变形为：

• $ans[i][j]=ans[i-1][j]+ans[i-1][j-1]+i$

• 就是这样
• 题解写的丑，dalao勿喷。

证毕。

于是......这就是我的只有15行的代码了（未压行）：

#include<iostream>
using namespace std;
int ans[1005][1005],q,n,m;
int main() {
	for(int i=1;i<=1000;i++)
	for(int j=1;j<=1000;j++) {
		ans[i][j]=(ans[i-1][j-1]+ans[i-1][j]+i)%19260817;
	}
	cin>>q;
	while(q--) {
		cin>>n>>m;
		cout<<ans[m][n]<<endl;
	}
	return 0;
}