题解 CF1204E 【Natasha, Sasha and the Prefix Sums】

ljc20020730 · 2019-08-23 13:27:18 · 题解

这里补一个O(n+m)的作法，对于该题，我们直接可以用组合数来求解。

设f_i为最大前缀和为i的不同序列的个数。

那么最后的答案就是\sum\limits_{i=1}^{n}i \times f_i

为了求出f_i，我们可以先求出一个g_i数组，

其中g_i表示最大前缀和大于等于i的不同序列个数。

那么对于任意1 \leq i \leq n ，都有f_i = g_i - g_{i-1}

那么，如何求g_i，设当前放了i个+1，放了j个-1,对应在平面直角坐标系的点(i,j)，将一个序列看做从初始位空的(0,0)点走到最终状态的(n,m)点的一条路径。

对于最大前缀和至少为i的限制，就是强制这条路径必须经过直线y = x-k

那么，从(0,0)经过直线y = x - k再到达(n,m)的路径条数就是g_k的值。

我们可以将(0,0)点按照直线对称，变成(k,-k)，那么从(k,-k)走到(n,m)的路径条数就是所求。

这个值可以直接组合数来求，答案是\binom{n-k+m+k}{n-k} = \binom{n+m}{n-k}

即g_k = \binom{n+m}{n-k}.

请注意一个g_i的先决条件，就是如果无论如何当前序列如何构造，都能够使得最大前缀和大于等于i的情况下(即k \leq n-m时)，g_i = \binom{n+m}{n}。

吐槽一下模数我一直以为是998244353来着的....