[SCOI2010]字符串

思路：

设1为向(1,1)方向走，0为向(1,-1)方向走。那么题意可转化为从(0,0)走到(n+m,n-m)且不能跨过y=0的方案数。总方案数C(n+m,n)，然后要减去不合法的即线路通过y=-1的。将线路与y=-1交点的左边沿着y=-1做对称操作，则最后等价于从(0,-2)走到(n+m,n-m)的方案数。因为从(0,-2)

走到(n+m,n-m)需要向上走n-m+2次，一共要走n+m次。设向上向下各走x,y，那么x+y=n+m,x-y=n-m+2得到x=n+1,y=m-1，所以不合法的方案为C(n+m,m-1)。

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const int mod=;

const int N=;

int n,m,ans,f[][N][N];

void dp(){

//    f[n+m][n][m]=1;

    int now=;

    f[now][n][m]=;

    for(int i=n+m-;~i;i--){

        now^=;

        for(int j=;j<=n;j++){

            for(int k=;k<=m;k++){

                if(j>k&&k<m) f[now][j][k]+=f[now^][j][k+];

                if(j<n) f[now][j][k]+=f[now^][j+][k];

                if(f[now][j][k]>=mod) f[now][j][k]-=mod;

            }

        }

    }

    printf("%d\n",f[now][][]);

}

int main(){

    freopen("string.in","r",stdin);

    freopen("string.out","w",stdout);

    cin>>n>>m;

    if(n<m){puts("");return ;}

    dp();

    return ;

}

10分dp

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const int mod=;

const int N=1e5+;

int n,m,ans,f[][N];

void dp(){

    int now=;

    f[][]=;

    for(int i=;i<=n;i++){

        now^=;

        for(int j=;j<=min(i,m);j++){

            if(i) f[now][j]+=f[now^][j];

            if(j) f[now][j]+=f[now][j-];

            if(f[now][j]>=mod) f[now][j]-=mod;

        }

        for(int j=;j<=min(i,m);j++) f[now^][j]=;

    }

    printf("%d\n",f[now][m]);

}

int main(){

    freopen("string.in","r",stdin);

    freopen("string.out","w",stdout);

    cin>>n>>m;

    if(n<m){puts("");return ;}

    dp();

    return ;

}

30分dp

//ans=C(n+m,n)-C(n+m,m-1){来源折线定理}

#include<cstdio>

#include<iostream>

using namespace std;

typedef long long ll;

const int N=2e6+;

const ll mod=;

int n,m;ll ans,fz[N],fm[N];

void exgcd(ll a,ll b,ll &d,ll &x,ll &y){

    if(!b){d=a;x=;y=;return ;}

    exgcd(b,a%b,d,y,x);

    y-=a/b*x;

}

ll inv(ll a,ll p){

    ll d,x,y;

    exgcd(a,p,d,x,y);

    return d==?(x%p+p)%p:-;

}

int main(){

    cin>>n>>m;

    int S=n+m;fz[]=fm[]=;

    for(ll i=;i<=S;i++) fz[i]=(fz[i-]*i)%mod;

    fm[S]=inv(fz[S],mod);

    for(ll i=S-;i;i--) fm[i]=(fm[i+]*(i+))%mod;

    ans=(fz[n+m]*fm[n]%mod*fm[m]%mod-fz[n+m]*fm[m-]%mod*fm[n+]%mod+mod)%mod;

    cout<<ans;

}