CF 1204 E Natasha,Sasha and the Prefix Sums(組合せ数学)

作り方1
(O(nm))は(f(i,j))がi個+1,j個−1に寄与することを考慮した.

(f(i-1,j))シーケンスに最初に1つの(1)を追加することを考慮すると、寄与(1times)はシーケンスの個数:(C(j+i-1,i-1))

(f(i,j-1))最初に1つの(-1)を追加することを考慮すると、貢献は(-1times)最大接頭辞と(0)でない個数であり、シーケンス個数が(0)に減少する個数を考慮すると

である.
(k(i,j))を(0)とする個数
(i=0:k(i,j)=1)(j=0またはi>j:k(i,j)=0)(ile:k(i,j)=k(i-1,j)+k(i,j-1))は、(1)を一番後ろに、(-1)を一番前に、必ず構成できる
作り方2
(O(n+m))考慮(f(i))は、最も大きなサブシーケンスが(i)である個数を表し、答えは(sumlimits_{i=1}^{n}itimes f(i))である
(g(i))が最も大きいサブシーケンスが(i)より大きい個数であることを考慮すると、明らかに(max(n-m,0)le ile n)は、長(n)高(m)の矩形、上へ行くと(-1)、右へ行くと(+1)、最大接頭辞および少なくとも(i)に抽象化され、ルートは(y=x-i)を通過する必要がある.

\(0\le i\le n-m:C(n+m,n)\)

(n-m:((0,0))対(y=x-i)対称を考慮すると((i,-i))から((n,m))へのシナリオ数は、(C(n+m,m+k))に変換される.
既知の未知数の数、係数はすべて(1)、および与えられた値であり、未知数は負の数解ではない

Code

#include
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
",ans);
    return 0;
}