洛谷1002 容斥原理+dfs OR DP
2024-10-21 13:20:54
//By SiriusRen
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,sx,sy,xx[]={,,,,-,-,-,-,},yy[]={,-,,-,,-,,-,};
int stk1[],stk2[],stk[],C[][],Ans,top;
bool check(int x,int y){return x>=&&y>=&&x<=n&&y<=m;}
int solve(int dep){
int lastx=,lasty=,ans=;
for(int i=;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&)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=;i<=top;i++){
if(i!=nw&&stk1[i]>=x&&stk2[i]>=y){
stk[dep+]=i;
dfs(stk1[i],stk2[i],i,dep+);
}
}
}
signed main(){
scanf("%lld%lld%lld%lld",&n,&m,&sx,&sy);
for(int i=;i<=;i++){
C[i][]=C[i][i]=;
for(int j=;j<i;j++)
C[i][j]=C[i-][j-]+C[i-][j];
}
for(int i=;i<=;i++){
int dx=sx+xx[i],dy=sy+yy[i];
if(check(dx,dy))stk1[++top]=dx,stk2[top]=dy;
}
dfs(,,,);
printf("%lld\n",Ans);
}
//By SiriusRen
#include <stdio.h>
long long n,m,sx,sy,i,j,vis[][],F[][],xx[]={,,,,-,-,-,-,},yy[]={,-,,-,,-,,-,};
int check(int x,int y){return x>=&&y>=&&x<=n&&y<=m;}
signed main(){
scanf("%I64d%I64d%I64d%I64d",&n,&m,&sx,&sy);
for(i=;i<=;i++){
int dx=sx+xx[i],dy=sy+yy[i];
if(check(dx,dy))vis[dx][dy]=;
}
F[][]=;
for(i=;i<=n;i++){
for(j=;j<=m;j++)if(!vis[i][j]){
if(i)F[i][j]+=F[i-][j];
if(j)F[i][j]+=F[i][j-];
}
}printf("%I64d\n",F[n][m]);
return ;
}
最新文章
- 基于RN开发的一款视频配音APP(开源)
- 基于CkEditor实现.net在线开发之路(8)Vs开发怎么配置
- 【转】PL/SQL Developer各个窗口的功能
- Yii2.0学习笔记:创建登录表单
- 三维网格形变算法(Gradient-Based Deformation)
- kuohao
- 飞凌OK6410开发板SDIO无线8189WIFI模块驱动移植
- C实现通用数据结构--双向链表
- 各个JSON技术的比较
- 数往知来C#之 正则表达式 委托 XML<;六>;
- gcc的stdcall扩展
- thoughtworks家庭作业C++版本
- docker 安装与学习
- 一键安装gitlab7在rehl6.4上
- C. cltt的幸运数LCAtarjan
- FTP的应用
- python第四十三课——封装性
- hdu 4998 矩阵表示旋转
- hdu 5318 The Goddess Of The Moon
- Scratch GUI
热门文章
- php正则表达式匹配html标签
- 解决Python打包exe控制台无法粘贴问题
- L2-006. 树的遍历(不建树)
- ebay 如何获取用户token
- 【Codeforces 682C】Alyona and the Tree
- [luoguP2890] [USACO07OPEN]便宜的回文Cheapest Palindrome(DP)
- 撸呀撸的左手(KMP+DP)
- windows 2008 64位在指定的 DSN 中,驱动程序和应用程序之间的体系结构不匹配
- go语言slice的理解
- 小议C#错误调试和异常处理