题解 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$来着的....
$AC$代码：
```cpp
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N=2e5+10,mo=998244853;
int s[N],inv[N],n,m;
int Pow(int x,int n)
{
int ans = 1;
while (n) {
if (n&1) ans=ans*x%mo;
x=x*x%mo;
n>>=1;
}
return ans%mo;
}
int C(int n,int m) {
if (m<0) return 0;
return s[n]*inv[m]%mo*inv[n-m]%mo;
}
int g(int k) {
if (k<=n-m) return C(n+m,n);
else return C(n+m,n-k);
}
signed main()
{
scanf("%lld%lld",&n,&m);
s[0]=1; for (int i=1;i<=n+m;i++) s[i]=s[i-1]*i%mo;
inv[0]=1; for (int i=1;i<=n+m;i++) inv[i]=Pow(s[i],mo-2);
int ret = 0;
for (int i=1;i<=n;i++)
ret=(ret+i*(((g(i)-g(i+1)%mo+mo)%mo)%mo))%mo;
printf("%lld\n",ret);
return 0;
}
```