CF1204E Natasha, Sasha and the Prefix Sums(组合数学)

做法一

\(O(nm)\)

考虑\(f(i,j)\)为i个+1,j个-1的贡献

\(f(i-1,j)\)考虑往序列首添加一个\(1\)，则贡献\(1\times\)为序列的个数：\(C(j+i-1,i-1)\)
\(f(i,j-1)\)考虑首添加一个\(-1\)，则贡献为\(-1\times\)最大前缀和不为\(0\)的个数，考虑序列个数减掉为\(0\)的个数

设\(k(i,j)\)为\(0\)的个数

\(i=0：k(i,j)=1\)

\(j=0或i>j：k(i,j)=0\)

\(i\le：k(i,j)=k(i-1,j)+k(i,j-1)\)，理解：把\(1\)放在最后面，把\(-1\)放在最前面，一定可以构成

做法二

\(O(n+m)\)

考虑\(f(i)\)表示最大子序列为\(i\)的个数，则答案为\(\sum\limits_{i=1}^{n}i\times f(i)\)

考虑\(g(i)\)为最大子序列大于等于\(i\)的个数，显然\(max(n-m,0)\le i\le n\)

抽象到方格：长\(n\)高\(m\)的矩形，往上走相当于\(-1\)，往右走相当于\(+1\)，最大前缀和至少为\(i\)，则路线需要经过\(y=x-i\)

\(0\le i\le n-m：C(n+m,n)\)
\(n-m<i\le n\)：考虑\((0,0)\)对\(y=x-i\)对称，则为\((i,-i)\)到\((n,m)\)的方案数，转换为以下问题，为\(C(n+m,m+k)\)

已知未知数个数，系数均为\(1\)，和为给定值，未知数非负个数解

Code

#include<bits/stdc++.h>

typedef long long LL;

const LL maxn=1e4+9,mod=998244853;

LL n,m,ans;

LL fac[maxn],fav[maxn],g[maxn];

inline LL Pow(LL base,LL b){

	LL ret(1);

	while(b){

		if(b&1) ret=base*ret%mod;

		base=base*base%mod; b>>=1;

	}

	return ret;

}

inline void Pre(LL N){

	fac[0]=1;

	for(LL i=1;i<=N;++i) fac[i]=fac[i-1]*i%mod;

//	puts("133");

	fav[N]=Pow(fac[N],mod-2);

	for(LL i=N;i>=1;--i) fav[i-1]=fav[i]*i%mod;

}

inline LL C(LL N,LL M){

	return fac[N]*fav[M]%mod*fav[N-M]%mod;

}

inline LL Solve(LL k){

	if(k<=n-m) return C(n+m,m);

	return C(n+m,m+k);

}

int main(){

	scanf("%lld%lld",&n,&m);

	Pre(n+m);

//	puts("233");

	for(LL i=1;i<=n;++i) g[i]=Solve(i); g[n+1]=0;

	for(LL i=1;i<=n;++i){

		ans=(ans+i*((g[i]-g[i+1]+mod)%mod)%mod)%mod;

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

CF1204E Natasha, Sasha and the Prefix Sums(组合数学)

做法一

做法二

Code

最新文章

热门文章