首页 > 代码库 > 洛谷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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。