【[SCOI2010]生成字符串】
发布时间:2020-12-14 05:17:10 所属栏目:大数据 来源:网络整理
导读:(n=m) 时候经典的卡特兰 那 (n!=m) 呢,还是按照卡特兰的方式来推 首先总情况数就是 (binom{n+m}{n}) ,在 (n+m) 个里选择 (n) 个 (1) 显然有不合法的情况,减掉它们 对于一种不合法的情况,必然存在一个前缀 (0) 的个数比 (1) 多 (1) 我
(n=m)时候经典的卡特兰 那(n!=m)呢,还是按照卡特兰的方式来推 首先总情况数就是(binom{n+m}{n}),在(n+m)个里选择(n)个(1) 显然有不合法的情况,减掉它们 对于一种不合法的情况,必然存在一个前缀(0)的个数比(1)多(1) 我们考虑构造出一个由(n+1)个(1)和(m-1)个(0)组成的序列,其必然存在一个前缀使得(1)的个数比(0)多(1) 于是就能一一对应了 也可以这样理解,对于每一个不合法的情况,找到第一个不合法的前缀,将其取反,之后就会得到一个(n+1)个(1)和(m-1)个(0)组成的字符串,还是可以一一对应 答案就是(binom{n+m}{n}-binom{n+m}{n+1}) 代码 #include<iostream> #include<cstring> #include<cstdio> #define LL long long #define re register #define maxn 1000005 const LL mod=20100403; LL n,m,fac[maxn*2]; inline int read() { char c=getchar(); int x=0; while(c<‘0‘||c>‘9‘) c=getchar(); while(c>=‘0‘&&c<=‘9‘) x=(x<<3)+(x<<1)+c-48,c=getchar(); return x; } LL exgcd(LL a,LL b,LL &x,LL &y) { if(!b) return x=1,y=0,a; LL r=exgcd(b,a%b,y,x); y-=a/b*x; return r; } inline LL inv(LL a) { LL x,y; LL r=exgcd(a,mod,x,y); return (x%mod+mod)%mod; } inline LL C(LL n,LL m) { if(m>n) return 0; return (fac[n])*inv(fac[m]*fac[n-m]%mod)%mod; } int main() { n=read(),m=read(); fac[0]=1; for(re int i=1;i<=n+m;i++) fac[i]=(fac[i-1]*i)%mod; printf("%lldn",(C(n+m,n)-C(n+m,n+1)+mod)%mod); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |