NOIp2018D2T2的通项公式及一些证明

xenonex · 2018-12-27 20:56:11 · 题解

upd on 2018.12.28 修复了证明Ans(n,m+1)=3 \times Ans(n,m)的bug

当初在考场上看到数据范围以为是个玄学状压+找规律，想了一会感觉不可做的样子，于是就弃掉去淦T3了QAQ。现在我花了一晚上+一上午手玩样例推柿子，并且还口胡了这篇有严格证明的题解造（bao）福（fu）社会。

对于这道NOIplus题目，首先需要yy出两个重要的性质：

性质1、每一条对角线上填的数是单调不增的。

性质2、如果(x-1,y)和(x,y-1)的填的数相同，那么以(x,y)为左上角、以整个矩阵的右下角为右下角的子矩阵内所有对角线内的填数各自相同。

注意本文中的对角线均指从左下到右上的对角线。

有时为了避免混淆，我会画成下面这个样子

总之黑框表示框里的对角线的填数要相等

这两个结论很容易用反证来证明，具体细节请读者自行撕烤

然后还有一个听说很显然的结论：令Ans(n,m)表示宽为m高为n的矩阵填数方案，则Ans(n,m)=Ans(m,n)。

不明白怎么回事的同学可以这样考虑

对于一个合法的m>n的方案，将填入的数全部反转，然后将整个矩阵顺时针转90°，最后把矩阵左右轴对称一下，就能得到一个n>m的方案。

看上去没问题

于是为了方便，后文全部默认n \le m。

到这里就已经能手摸出n=1和n=2的情况了。我们将整个矩阵按照每一条对角线划分为若干个阶段，稍微画下图就能看出Ans(1,m)=2^m以及Ans(2,m)=4 \cdot 3^{m-1}。注意这里是保证了m大于等于n的。

这两个式子应该不用多解释吧

对于n \ge 4，我们再分为4种情况考虑（n=3的情况稍后考虑）：

case1：最上面的两个填数相同

case2：最上面的两个数不同，下面一条对角线的3个填数相同

case3：那3个填数为1，0，0

case4：3个填数为1，1，0

容易发现无论是哪种情况，总是会存在一个点(x,y)使得(x-1,y)和(x,y-1)填数相同，这样就能够限制掉一大片区域，是手玩通项公式的重要保证。

发现这个性质后就能证明出另一结论了：对于n \ge 4且m \ge n+1，有Ans(n,m+1)=3 \times Ans(n,m)

证明其实超简单

可以发现黑框里一定是被性质2限制掉的，所以整条绿色的对角线填数都相同，而且由于绿色方框位于矩阵下边界，它是不受其它填数限制的，换句话说在所有的合法方案中，有1/2的情况它等于0，剩下1/2的情况等于1

然后考虑在原矩阵右边再添一列

灰色粗♂条划掉的方格由于受到性质2的影响，它们必须要与各自左下方的格子中填数相同，因此这一部分不会对答案产生新的贡献；但蓝色位于右下角，它的填数是自由的。

受到性质1的限制，若绿色格子内填数为1，则右上方的方格能填0或1，会产生2\times2=4倍的贡献；否则只能填0，只有2\times1=2倍的贡献。综合起来，总的贡献就是原来的\frac{1}{2}\times4+\frac{1}{2}\times2=3倍。

简单吧，没骗你

upd：第二天晚上发现自己zz了……

因为第二排的确有可能没有被覆盖到，就像这样

于是上面的证明就愉快地GG了

紧急修一波锅

跟之后推式子的操作一样，枚举第一次出现相同数的位置，我们发现当这个位置比较靠前使得红色方块被覆盖到时是无需考虑的，因为此时与上方的情形等价= =

于是把精力集中在这两种情况

考虑第一张图，原先绿色部分有3种填法，添一列后运用类似的方法分析出产生的新贡献，它是原来的\frac{2}{3}+\frac{2}{3}+\frac{4}{3}=\frac{8}{3}倍

同理算出第二张图是原来的4倍

接着同时考虑这两种情况，算出倍数\frac{(2^{n-2}\times3\times3\times2)\times\frac{8}{3}+(2^{n-2}\times3\times2)\times4}{2^{n-2}\times3\times3\times2+2^{n-2}\times3\times2}=\frac{2^{n+2}\times3+2^{n+1}\times3}{2^{n-1}\times9+2^{n-1}\times3}=\frac{8\times3+4\times3}{9+3}=3

这才完成了Ans(n,m+1)=3 \times Ans(n,m)的证明

好的下面继续原来的内容

接下来考虑m=n的情况来摸柿子。请各位务必要看懂以下的推倒过程，其它更一般的推倒与这里大同小异。

首先看case1。

联系两条限制条件，不难得出每条对角线上填数的方案数，我用蓝色在图上标注了一些边界情况。容易看出case_1=2\times2\times4^{n-2}\times2^{n-1}=8^{n-1}

这样case1就搞定了。

然后是case2

得到case_2=2\times2\times5\times4^{n-4}\times2^{n-1}=5\times2^{3n-7}

于是case2也搞定了

到现在为止一切都很美好

接下来才是真正辣手的事情

下面是case3

这下不好办了，因为左边两列貌似都没有什么特别的限制。不过没关系，我们可以继续分类讨论下去

我们大力讨论左边两列的对角线上从上往下第一次出现两数相同的位置，所以这之上应该都填1,0。而此时出现了一个新的限制区域，将此区域与原来的区域取并集就成了下图黑框的样子

然后就可以写出每条线上的方案了

注意当x=0时右上方的对角线只能填0，而x=1时三种情况都能填，所以x那里的线是4

于是我们找出一些边界情况后就能算出整个case3了

在第一个出现

在倒数第二个出现

在最后一个出现

别忘了没有的情况

于是我们可以枚举x下方4的个数，得到case_3=2\times4\times5\times\sum\limits_{i=0}^{n-5}4^i\times2^{n-1}+2\times4\times3\times2^{n-2}+2\times3\times2^{n-2}

于是case3也搞定了

好像也不怎么复杂

最后是case4

稍微yy一下case4的推倒发现其实与case3是完全对称的，不明白这里的同学可以手动画一下，我这里就不画了...因此case_4=case_3

综合以上4种cases，我们就能算出Ans(n,n)了。因为这4种情况完全包含了所有的可能且互不重叠，所以Ans(n,n)=case_1+case_2+case_3+case_4。把case带进式子再使劲蹂躏一下得到最终答案：

累死了