Codeforces 295D Greg and Caves

题意

你有一个n*m大小的棋盘,n行,m列,行号列号都从1开始,行从上到下数到n,列从左到右数到m,棋盘的每一个格子可以是黑色或者白色。

当满足全部下述条件的时候,认为棋盘上出现了一个”Cave“:

  • 存在一个线段[l,r] (1 <= l <= r <= n),使得l,l+1,l+2,...,r这些行都有且仅有两个黑色格子,其他行不存在黑色格子。
  • 存在一个行号t (l <= t <= r),使得:
    • 对于任意存在黑色格子的行r,把这行的黑色格子对应的列号和黑色格子之间的列号加入一个集合, 称之为S(r)
    • 任取t及t之上的两个有黑色格子的行,令上方的行为u,下方的行d,则S(u)S(d)的子集。
    • 任取tt之下的两个有黑色格子的行,令上方的行为u,下方的行为d,则S(d)S(u)的子集。

你要输出有多少染色的方案,使得棋盘出现一个“Cave”,答案模1000000007

思路

翻译一下题意,就是让我们找一种染色方案,让棋盘上出现下面这样的图案(下图中n = m = 5 ,l = 3, r = 15, t = 8)。

295D

可以发现,这个图案可以以t行为界分拆为上下两个部分,不妨令hf[h][w]表示得到高度为h的,底部两个黑块宽度必须为w的,每一行都有黑块的,半个图案的染色方案数。

我们可以很容易发现如下的递推关系:

hf[h][w] = {hf[h-1][w] + 2\times hf[h-1][w-1] + 3\times hf[h-1][w-2] +4\times hf[h-1][w-3] + ... + w\times hf[h-1][1]}

即:

hf[h][w] = \sum_{k=1}^{w} k\cdot  hf[h-1][w+1-k]

考虑同一高度的相邻两项之差:

hf[h][w] - hf[h][w-1] = \sum_{k=1}^{w} hf[h-1][k]

这样,我们一行行地计算hf的值,一边维护每一行的前缀和,一边算下一项,这样可以用O(n^2)的时间完成预处理。

接下来我们考虑如何把两个一半的图案合成一个,我们令al[h][w]表示得到高度为h,最宽处宽度为w,每一行都有黑块的图案的染色方案数,我们有:

 al[h][w] =\sum \left\{\begin{matrix} {hf[1][w] \cdot (2\times hf[h-1][w-1] + 3\times hf[h-1][w-2] + 4\times hf[h-1][w-3] + ... + w\times hf[h-1][1])} \\ {hf[2][w] \cdot (2\times hf[h-2][w-1] + 3\times hf[h-2][w-2] + 4\times hf[h-2][w-3] + ... + w\times hf[h-2][1])} \\ {hf[3][w] \cdot (2\times hf[h-3][w-1] + 3\times hf[h-3][w-2] + 4\times hf[h-3][w-3] + ... + w\times hf[h-3][1])} \\ ... \\ {hf[h][w] \cdot (2\times hf[0][w-1] + 3\times hf[0][w-2] + 4\times hf[0][w-3] + ... + w\times hf[0][1])} \end{matrix}\right.

即:

 al[h][w] = \sum \left\{\begin{matrix} hf[1][w]\times \sum_{k=1}^{w-1} (k+1)\cdot hf[h-1][w-k] \\ hf[2][w]\times \sum_{k=1}^{w-1} (k+1)\cdot hf[h-2][w-k] \\ hf[3][w]\times \sum_{k=1}^{w-1} (k+1)\cdot hf[h-3][w-k] \\ ... \\ hf[h][w]\times \sum_{k=1}^{w-1} (k+1)\cdot hf[0][w-k] \end{matrix}\right.

为了让式子更简洁,我们令rc[h][w] = \sum_{k=1}^{w-1} (k+1)\cdot hf[h][w-k],这样的话,我们就有:

al[h][w] = \sum_{k=1}^{h} hf[k][w]\cdot rc[h-k][w]

很明显这个式子是一个卷积,如果我们可以预处理出rc的值,就可以使用FFT进行快速运算。我们发现rc的递推关系和hf的递推关系非常相似,我们依然考虑同行相邻两项的差值:

rc[h][w] - rc[h][w-1] = hf[h][w-1] + \sum_{k=1}^{w-1} hf[h][w-k]

这样我们依然采用一边计算一边维护前缀和的方法,可以在O(n^2)的时间完成rc的预处理。

预处理好rc之后,就是计算卷积了,因为题目要求模1000000007,我们需要采用NTT+CRT的方式实现任意模空间下的卷积(具体实现原理不是我们的讨论范围),这样的话,在最恶劣情况,我们需要做18000次4096点NTT,单次NTT耗时几毫秒,超时无法避免,我们只能考虑进一步优化。

我们继续考虑,令dw[w]表示最宽处宽度为w,高度范围在1 \sim N的图案,有多少方案可以作成,那么我们有:

 dw[w] = \sum \left\{\begin{matrix} N\cdot al[1][w] \\ (N-1)\cdot al[2][w] \\ (N-2)\cdot al[3][w] \\ ... \\ 1 \cdot al[N][w]  \end{matrix}\right.

al打开,就有:

 dw[w] = \sum \left\{\begin{matrix} N\times hf[1][w]\cdot rc[0][w] \\ (N-1)\times (hf[1][w]\cdot rc[1][w] + hf[2][w]\cdot rc[0][w]) \\ (N-2)\times (hf[1][w]\cdot rc[2][w] + hf[2][w]\cdot rc[1][w] + hf[3][w]\cdot rc[0][w]) \\ ... \\ 1\times (hf[1][w]\cdot rc[N-1][w] + hf[2][w]\cdot rc[N-2][w] + ... + hf[N][w]\cdot rc[0][w]) \end{matrix}\right.

我们把dw[w]重新整理一下:

 dw[w] = \sum \left\{\begin{matrix} hf[1][w]\times (N\cdot rc[0][w] + (N-1)\cdot rc[1][w] + (N-2)\cdot rc[2][w] + ... + 1\cdot rc[N-1][w]) \\ hf[2][w]\times ((N-1)\cdot rc[0][w] + (N-2)\cdot rc[1][w] + (N-3)\cdot rc[2][w] + ... + 1\cdot rc[N-2][w]) \\ hf[3][w]\times ((N-2)\cdot rc[0][w] + (N-3)\cdot rc[1][w] + (N-4)\cdot rc[2][w] + ... + 1\cdot rc[N-3][w]) \\ ... \\ hf[N][w] \times 1 \cdot rc[0][w] \end{matrix}\right.

如果比较敏感的话应该已经发现突破口了,我们再整理一下:

dw[w] = \sum_{i=1}^{N}hf[i][w]\sum_{j=0}^{N-i}((N-i-j+1)\cdot rc[j][w])

还没看出来?再令tr[i][w] = \sum_{j=0}^{N-i}((N-i-j+1)\cdot rc[j][w]),这样:

dw[w] = \sum_{i=1}^{N}hf[i][w]\cdot tr[i][w]

而且我们还可以发现hf, rc, tr它们的递推关系都是差不多的,也就是说对于tr我们继续采用考虑相邻两项差的策略:

tr[i][w] - tr[i-1][w] = \sum_{k=0}^{N-i} rc[k][w]

这样我们可以用O(n^2)的时间把tr搞定,这样的话,计算全部的dw的值也是O(n^2)时间了。

计算好表示定宽度不定高度的图案数的dw之后,接下来我们放宽到不定宽度不定高度的图案数,也就是答案,我们有:

ans = \sum_{w=2}^{M}(M-w+1)\cdot dw[w]

这样我们绕了一大圈终于把答案算出来了,总复杂度O(n^2),本题至此解决。

实现

NTT+CRT做法

注意这份代码因为常数过大无法通过,但是答案是正确的。

正解

参考

  1. kmjpさん(日本語注意):
    http://kmjp.hatenablog.jp/entry/2014/09/22/0900
  2. Zeyu_king:
    http://blog.csdn.net/zeyu_king/article/details/44040749

 

Leave a Reply

Scroll to top