Hundred Thousand Volts 01 题解

2018-04-15 14:07:15 By eeeeeericKKK

棋赢

是不是很像个多项式题呢?

令果子总数为sum,最终答案显然是 $\binom{sum-1}{n-1}$ 。由于n很小,前者可以暴力展开成一个关于sum的n-1次多项式。这意味着如果我们算出向量 $V=(\sum sum^0 ,\sum sum^1 , \sum sum^2 ,\dots ,\sum sum^{n-1})$ ,就可以求得答案。

定义 $f(V,x)$ 表示对V所代表的的当前答案中所有需要统计的sum值变成sum+x会怎么样。利用二项式定理可以把 $(sum+x)^k$ 展开,最终写成一个下三角矩阵 $M_{ij}=\binom i j\cdot x^{i-j}$ 。容易得到 $f(V,x)= M\cdot V$ 。

接下来考虑一只动物的影响,相当于把x=1到x=b所对应的的矩阵相加,也就是 $M'_{ij}=\binom i j\sum_{x=1}^bx^{i-j}$ 。得到这个之后,可以使用矩阵快速幂得到最终的答案。不考虑计算M的时间,总的复杂度是 $O(mn^3\log S_a)$ 。

至于转移矩阵显然是一个自然数幂和的形式,有多种方法优化。

某黑红出题人要求我把这题出成一个彻头彻尾的多项式题,数据范围变成$10^5$,然而本出题人非常良心没有同意。这部分就当做bonus啦!

std(上面blog没有描述,用了第二类斯特林数和下降幂的性质)在这里


或负

甩锅啦!原题戳这里,题解戳这里

std在这里


必去之

为了方便,把p改变,使得最优答案一定包含第一个和最后一个数,详见std。

定义f(i)表示考虑前i个数,且必须选择第i个时的LIS。那么有下面的公式,可以证明这样一定不会丢失最优解。 $$f(i)=\max\{f(j)+1+\min\{j到i之间的空格个数,p_j到p_i之间未出现在原排列的数的个数\}\mid j< i,p_j>0,p_j< p_i\}$$

可以发现min里面的两项都是部分和的形式,可以用前缀和改写。公式自行脑补然后把min操作分成两部分加到max的条件里面去,这样所求的max值为一个三维的RMQ。首先按i从小到大可以去掉一维,剩下的随便写个二维数据结构即可,复杂度2个log。

std(cdq分治)在这里


后记

实际上我写了一个很详细的题解,包括多种算法和部分分。然后在最后写好保存的时候网络模糊,最终保存到oj上的变成了一堆乱码...

不过出题人还是很良心艰难地把正解做法告诉了你们!至于具体公式和细节就留给你们脑补啦!

杨主力:写题解还带std的都是sb出题人!

评论

avatar
fizzydavid
你们别听陈主力瞎说 他在最后一行加的那些话我一句都没说过 ![pic8.jpg](//acm.nflsoj.com/pictures/problem/110/pic8.jpg)
avatar
diamond_duke
![pic8.jpg](http://acm.nflsoj.com/pictures/problem/110/pic8.jpg)
avatar
czrwinwinwin
czrwin!
avatar
spfa
Orz
avatar
duyi
考古

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。