首页 > 代码库 > 洛谷1002 容斥原理+dfs OR DP

洛谷1002 容斥原理+dfs OR DP

//By SiriusRen#include <bits/stdc++.h>using namespace std;#define int long longint n,m,sx,sy,xx[]={1,1,2,2,-1,-1,-2,-2,0},yy[]={2,-2,1,-1,2,-2,1,-1,0};int stk1[25],stk2[25],stk[25],C[45][45],Ans,top;bool check(int x,int y){return x>=0&&y>=0&&x<=n&&y<=m;}int solve(int dep){    int lastx=0,lasty=0,ans=1;    for(int i=1;i<=dep;i++){        int tx=stk1[stk[i]]-lastx,ty=stk2[stk[i]]-lasty;//        printf("tx=%d ty=%d\n",tx,ty);        ans*=C[tx+ty][tx];        lastx=stk1[stk[i]],lasty=stk2[stk[i]];    }    int tx=n-lastx,ty=m-lasty;    return ans*C[tx+ty][tx];}void dfs(int x,int y,int nw,int dep){    if(dep&1)Ans-=solve(dep);    else Ans+=solve(dep);//    printf("x=%lld y=%lld dep=%lld Ans=%lld\n",x,y,dep,solve(dep));    for(int i=1;i<=top;i++){        if(i!=nw&&stk1[i]>=x&&stk2[i]>=y){            stk[dep+1]=i;            dfs(stk1[i],stk2[i],i,dep+1);        }    }}signed main(){    scanf("%lld%lld%lld%lld",&n,&m,&sx,&sy);    for(int i=0;i<=40;i++){        C[i][0]=C[i][i]=1;        for(int j=1;j<i;j++)            C[i][j]=C[i-1][j-1]+C[i-1][j];    }    for(int i=0;i<=8;i++){        int dx=sx+xx[i],dy=sy+yy[i];        if(check(dx,dy))stk1[++top]=dx,stk2[top]=dy;    }    dfs(0,0,0,0);    printf("%lld\n",Ans);}
//By SiriusRen#include <stdio.h>long long n,m,sx,sy,i,j,vis[25][25],F[25][25],xx[]={1,1,2,2,-1,-1,-2,-2,0},yy[]={2,-2,1,-1,2,-2,1,-1,0};int check(int x,int y){return x>=0&&y>=0&&x<=n&&y<=m;}signed main(){    scanf("%I64d%I64d%I64d%I64d",&n,&m,&sx,&sy);    for(i=0;i<=8;i++){        int dx=sx+xx[i],dy=sy+yy[i];        if(check(dx,dy))vis[dx][dy]=1;    }    F[0][0]=1;    for(i=0;i<=n;i++){        for(j=0;j<=m;j++)if(!vis[i][j]){            if(i)F[i][j]+=F[i-1][j];            if(j)F[i][j]+=F[i][j-1];        }    }printf("%I64d\n",F[n][m]);    return 0;}

 

洛谷1002 容斥原理+dfs OR DP