2023.02.15 日寄
一言
爱并不是完美的，爱的背后不可避免地有控制和占有。 爱的恐怖与温柔，不管是好是坏，都一并带它上路吧。——《爱的恐怖主义》
模拟赛
Natasha, Sasha and the Prefix Sums
题意
\(~~~~\) 求所有 \(n\) 个 \(1\) ，\(m\) 个 \(-1\) 组成的序列的与 \(0\) 取最大值的前缀最大值的和。
\(~~~~\) \(1\leq n,m\leq 2000\).
题解
\(~~~~\) 很显然可以枚举最后的最大值，恰好不好算，但我们可以算 \(\geq i\) 的方案，然后差分求解。
\(~~~~\) 那么一个经典的模型:\(\binom{n+m}{n}\) 为从 \((0,0)\) 每次走 \((1,1)\) 或 \((1,-1)\) 然后到达 \((n+m,n-m)\) 的方案数。而 \(\geq i\) 就是要求在路径中要接触 \(y=i\) 这条线。
\(~~~~\) 套路性地，若终点在线的两侧那就直接算，否则翻折终点到关于 \(y=i\) 的对称点，显然这样是一一对应地，然后我们再算方案就好了。
代码
查看代码
#include <bits/stdc++.h>
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
const int MOD=998244853;
inline int Add(int a,int b){a+=b;return a>=MOD?a-MOD:a;}
inline int Dec(int a,int b){a-=b;return a<0?a+MOD:a;}
inline int Mul(int a,int b){return 1ll*a*b%MOD;}
inline int qpow(int a,int b)
{
int ret=1;
while(b)
{
if(b&1) ret=Mul(ret,a);
b>>=1;a=Mul(a,a);
}
return ret;
}
int res[2005],Fac[4005],Inv[4005];
inline int C(int n,int r){return r>n?0:Mul(Fac[n],Mul(Inv[r],Inv[n-r]));}
int main() {
Fac[0]=1;
int n,m;read(n);read(m);
for(int i=1;i<=n+m;i++) Fac[i]=Mul(Fac[i-1],i);
Inv[n+m]=qpow(Fac[n+m],MOD-2);
for(int i=n+m-1;i>=0;i--) Inv[i]=Mul(Inv[i+1],i+1);
for(int i=0;i<=n;i++)//前缀和最大值 >= i
{
if(n-m>=i) res[i]=C(n+m,n);
else res[i]=C(n+m,n-i);
// cerr<<res[i]<<endl;
}
int Ans=0;
for(int i=0;i<=n;i++) Ans=Add(Ans,Mul(i,Dec(res[i],res[i+1])));
printf("%d",Ans);
return 0;
}
/*
瑶草一何碧，春入武陵溪。溪上桃花无数，花上有黄鹂。我欲穿花寻路，直入白云深处，浩气展虹霓。只恐花深里，红露湿人衣。
坐玉石，欹玉枕。拂金徽。谪仙何处，无人伴我白螺杯。我为灵芝仙草，不为朱唇丹脸，长啸亦何为。醉舞下山去，明月逐人归。
套路性地枚举值，求交某条线的方案数
对称，变成直接组合数可算的东西
*/