Luogu P1641 [SCOI2010]生成字符串 组合数学

时间：2024-05-31 13:34:02

神仙。。。。

当时以为是，$x$代表$1$,$y$代表$0$，所以不能过$y=x$的路径数。。。结果不会。。。

然后康题解。。。ヾ(｡｀Д´｡)竟然向右上是$1$，向右下是$0$。。。。

所以现在就是不能过$y=-1$；

所以我们可以这样想：如果有非法路径的话，那么就把他第一次与$y=-1$交点与起点之间的路径沿$y=-1$翻转；

然后现在非法路径的条数就是从$(0,-2)$到$(n+m,n-m)$路径数量，把他拿所有路径的减掉就行了。

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<vector>

#include<map>

#include<set>

#define ll long long

#define R register int

static char B[<<],*S=B,*D=B;

#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)

const int M=;

using namespace std;

inline int g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

}

int fac[M];

inline ll Inv(ll x) {

    if(x==) return ; if(x<=) return ; return (M-M/x*Inv(M%x)%M)%M;

}

inline ll C(ll n,ll m) {

    if(n<m) return ; return (ll)fac[n]*Inv((ll)fac[n-m]*fac[m]%M)%M;

} ll n,m;

signed main() {

#ifdef JACK

    freopen("NOIPAK++.in","r",stdin);

#endif

    n=g(),m=g();

    fac[]=fac[]=; for(R i=;i<n+m;++i) fac[i]=(ll)fac[i-]*i%M;

    printf("%lld\n",(C(n+m,n)-C(n+m,n+)+M)%M);

}

2019.06.05

相关文章