[AGC035F] Two Histograms

感觉这个题挺神仙的,我可能脑回路比较奇怪,用了一种奇怪的方法过了这道题。
一看这个题感觉无从下手,我就先考虑n=1的情况,可以发现,只需要枚举最后一个2的位置,除了这个2的位置,其它列随便取就可以得到所有答案。
那么我们不妨考虑一行一行取下来,由于列可以影响后面的行,所以我们不妨优先取列,当只取列满足不了时,再延长这行的加值区间,这样就可以不算重了。
这也就是说这一行对行操作的结束位置只有三种情况:
1.这行一个都不加
2.结束位置上的值最终为2
3.这一列的列操作无法使这里变1
对于第三种情况,具体判断方法是这一列之前位置中至少有一个0,也就是上一个位置是0或之前已经被判别为0
枚举完所有行的操作之后可以看有多少种列操作符合条件,可以发现,2情况就是对这一列的终止位置加一个下界,3情况是加上界,最后每一列的操作都是一段区间,直接乘起来即可。
这个$O(3^n m)$的爆搜似乎没法直接优化,我们不妨来枚举每一列。
我们依次枚举每一列,考虑那些行的终止位置在这一列。设这些行分别为$a_1,a_2,a_3,…,a_k$,如果$k\ge 1$,那么贡献为(必定是后面一堆确定下界,前面一堆确定上界,否则贡献为0):
$$(a_1-2-0+1)+(n-a_k+1)+\displaystyle\sum_{i=2}^k (a_i-2-a_{i-1}+1)$$
$$=n+1-k$$
!!!!
我们发现这个竟然和具体位置无关了!
那么答案就是:
$$n! \lbrack x^n \rbrack (\displaystyle\sum_{i\ge 0} (n+1-i)\frac{x^i}{i!})^m e^x$$
$$=n! \lbrack x^n \rbrack ((n+1)e^x-xe^x)^m e^x$$
$$=n! \lbrack x^n \rbrack (n+1-x)^m e^{(m+1)x}$$
$$=n!\displaystyle\sum_{i=0}^n (-1)^i(n+1)^{m-i}\binom{m}{i}\frac{(m+1)^{n-i}}{(n-i)!}$$
时间复杂度$O(n)

Tagged with:

发表评论