【SSLOJ1481】最大前缀和

题目

思路

将每一个 \(1\) 和 \(-1\) 看成向上和向右，那么就转换成从 \((0,0)\) 到 \((n,m)\) 的方案数。
枚举答案 \(i\)，那么显然这条路径不能与 \(y=x+i+1\) 相交。那么答案不超过 \(i\) 的方案数就是从 \((0,0)\) 到 \((n,m)\) 的方案数减去 \((0,0)\) 关于直线对称的点到 \(n,m\) 的方案数。即为

\[C^{n}_{n+m}-C^{m+i+1}_{n+m} \]

注意答案为 \(i\) 的方案数为这个数减去答案不超过 \(i-1\) 的方案数。
预处理阶乘和逆元即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=2000010,MOD=998244853;
ll ans,pre,fac[N],inv[N];
int n,m;

ll fpow(ll x,int k)
{
	ll ans=1;
	for (;k;k>>=1,x=x*x%MOD)
		if (k&1) ans=ans*x%MOD;
	return ans;
}

ll C(int a,int b)
{
	return fac[a]*inv[b]%MOD*inv[a-b]%MOD;
}

int main()
{
	scanf("%d%d",&n,&m);
	fac[0]=1LL;
	for (int i=1;i<N;i++)
		fac[i]=fac[i-1]*i%MOD;
	inv[N-1]=fpow(fac[N-1],MOD-2);
	for (int i=N-2;i>=0;i--)
		inv[i]=inv[i+1]*(i+1)%MOD;
	for (int i=max(n-m,0);i<=n;i++)
	{
		int sum=((C(n+m,n)-C(n+m,m+i+1)-pre)%MOD+MOD)%MOD;
		ans=(ans+1LL*sum*i)%MOD;
		pre=(pre+sum-MOD);
	}
	printf("%lld",(ans+MOD)%MOD);
	return 0;
}