一个极其有意义的问题
  • 板块学术版
  • 楼主StillEmpty
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/5/21 11:01
  • 上次更新2023/10/28 00:59:23
查看原帖
一个极其有意义的问题
150956
StillEmpty楼主2022/5/21 11:01
  1. 0!=0! = 几?
  2. 现在给你无限个 1×21 \times 2 的多米诺骨牌,定义 fn=f_n = 用这种骨牌填满一个 n×2n \times 2 的矩形的方案数。现在请问,f0=f_0 = 几?

这俩问题有点沙雕,但是都是有实际意义的,两个问题的答案应该都等于 11。第二个问题出现在《具体数学》生成函数章节的开头。具体数学原文:

恰有一种方式用多米诺牌覆盖一个 2×02 \times 0 矩形,即不用多米诺牌覆盖,于是 f0=1f_0 = 1

你可能觉得这种说法有点扯淡。我们可以换一个做法:可推导出 fi=fi1+fi2f_i = f_{i-1}+f_{i-2}f1=1f_1 = 1f2=2f_2 = 2,于是我们人为定义 f0=1f_0 = 1

但是对于某些复杂的计数问题的dp转移式,比如我写的cf1666f的:

fi,j=(i(pcntj1i)cntj)fi,j1+((i1)[pcntj1(i1)]cntj1)fi1,j1f_{i, j} = {i-(pcnt_{j-1}-i) \choose cnt_j}f_{i, j-1} + {(i-1)-[pcnt_{j-1}-(i-1)] \choose cnt_j-1}f_{i-1, j-1}

反向推导有点困难。同时在往后做这题时,我发现计算本题答案时需要求出 f0,0f_{0,0} 的值,然后我就意识到 f0,0f_{0,0} 不仅仅是个dp的起始点,是有实际意义的。

再举个知名点的例子:noip2021 数列。由于楼主实在是不能理解 f0,0,0,0f_{0,0,0,0} 是什么鬼。于是自己求了一遍只有一位的答案:

for(int i = 1; i <= n; ++i) {
    dp[0][i][i&1][i>>1] = powv[0][i];
}

但是我前面说了,计数dp的零点似乎是有实际意义的,所以想问一问如何理解dp的零点的值。

2022/5/21 11:01
加载中...