[AGC039F] Min Product Sum

感觉这个题不是特别难。首先肯定会想到从小到大枚举值,然后依次考虑代价,对于值相同的位置我们貌似无法做到按顺序计数,一种方法是先按任意顺序取然后除个数的阶乘。
由于我们是从小到大枚举,那么取掉一个位置以后,就可以将以其为最小值的位置全部删除(不妨令先取的更小)。
那么当我们取一个位置时,有四种情况:
1.覆盖其所在行和其所在列(其所在行和所在列均没有之前取的元素)
2.覆盖其所在行(其所在行没有之前元素,所在列存在之前取的元素)
3.覆盖其所在列(…)
4.不覆盖任何位置(其所在行列均有之前取的元素)
由于不同行列分别等价,我们不妨将其拉到左上角来考虑,那么这个图大概会成这样:

对于i=1,2,3,编号为i的块表示里面全是情况i的元素
块4中的元素为已被取走的元素和情况4的元素。
那么直接dp就是$O(n^7)$的。
感觉直接做这个dp没有什么优化空间,我们尝试着减掉一维状态。
$f(d,x,y,i)$表示做到元素大小为d,块4大小为$x\times y$,其中已经取了$i$个的代价。(这里我们假设块4位置是固定的而不可以随意选行列)
那么我们容斥一下:
$$f(d,x,y,i)=\displaystyle\sum_{0\le x_1\le x_2 \le x,0\le y_1\le y_2 \le y,0\le j\le i} f(d-1,x_1,y_1,j) \binom{x}{x_2}\binom{x_2}{x_1} \binom{y}{y_2} \binom{y_2}{y_1} \binom{x_2y_2-j}{i-j} (-1)^{x+y-x_2-y_2} d^{(n-x_1)(m-y_1)-(n-x)(m-y)}$$
式子看上去触目惊心,而且我们还成功劣化了算法,将复杂度提升至$\Omega(n^{10})$
这个看上去好像也没有什么优化空间。然后我发现了一件事情,就是我们可以单独考虑之前已经被认定为情况4的元素,当我们认定一个位置为情况4且比$d$大时可以直接随便选一个填进去,不影响其它决策。那么我们可以直接去掉一维,状态变成了三维$f(d,x,y)$表示取到大小为d,块4为$x\times y$的代价。(同样令块4位置固定)
$$f(d,x,y)=\displaystyle\sum_{0\le x_1\le x_2\le x,0\le y_1\le y_2\le y} f(d-1,x_1,y_1)\binom{x}{x_2}\binom{x_2}{x_1}\binom{y}{y_2}\binom{y_2}{y_1}(k-d+1)^{x_2y_2-x_1y_1}(k-d)^{xy-x_2y_2}(-1)^{x+y-x_2-y_2}d^{(n-x_1)(m-y_1)-(n-x)(m-y)}$$
这个感觉非常有优化空间,我们可以先拆成两部分:先用$(x_1,y_1)$搞出$(x_2,y_2)$,然后再搞出$(x,y)$
我们设一个中间函数$g(d,x,y)$
有:
$$g(d,x,y)=\displaystyle\sum_{x_1,y_1} f(d-1,x_1,y_1)\frac{x_2!y_2!(k-d+1)^{x_2y_2}d^{m(x_2-x_1)}d^{n(y_2-y_1)}d^{x_1y_1}}{x_1!(x_2-x_1)!y_1!(y_2-y_1)!(k-d+1)^{x_1y_1}d^{x_2y_2}}$$
我们发现这个行和列是分别独立的,因此可以分别转移。对于每一个d这样做一次是$O(nm(n+m))$的。(可以用FFT优化,但这题模数不太行而且范围比较小,可能用了以后反而会变慢,也可以尝试用$n^{\lg 3}$的那个分治乘法,有兴趣可以试一下,不过这道题暴力已经够用了)
$$f(d,x,y)=\displaystyle\sum_{x_2,y_2} g(x_2,y_2)\frac{x!y!(k-d)^{xy}d^{m(x-x_2)}d^{n(y-y_2)}d^{x_2y_2}}{x_2!(x-x_2)!y_2!(y-y_2)!(k-d)^{x_2y_2}d^{xy}}(-1)^{x-x_2}(-1)^{y-y_2}$$
和上面那个差不多,行列转移分别独立,复杂度$O(nm(n+m))$,但是要注意当$d=k$的时候不能除0,要特判。
所以总复杂度$\Theta(knm(n+m))$可以通过此题,也可以$\Theta(k(mn^{\lg 3}+nm^{\lg 3}))$或$\Theta(knm(\lg n+\lg m))$,但是懒得写了。

Tagged with:

发表评论