题解 P5239 【回忆京都】

Social_Zhao · 2019-03-02 19:03:21 · 题解

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

（实际上是发表后几小时，有一位大佬@dou_bao想出了递推式的推导方法（已获得他的授权））

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

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

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

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

  1	1	1	1	1	······
  3	4	4	4	4	······
  6	10	11	11	11	······
  10	20	25	26	26	······
  15	35	50	56	57	······
  ······	······	······	······	······	······

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

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

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

• 对于第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）

• 一个矩阵变成一行了。

• 因为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）

• 是不是和第一张表一模一样？
• 那么很明显 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;
}