CF 348DTurtles
2024-10-21 13:39:14
题目:http://codeforces.com/contest/348/problem/D
如果只走一条路那就直接dp就可以了。
设cal(x1,y1,x2,y2)为(x1,y1)→(x2,y2)的路径数。
cal(1,2,n-1,m)*cal(2,1,n,m-1)把相交的情况也算进去了。
但是对于每一种相交的情况,发现它们都对应一种将两个终点反转的情况。
那么ans=cal(1,2,n-1,m)*cal(2,1,n,m-1)-cal(1,2,n,m-1)*cal(2,1,n-1,m)
#include<cstring>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define low(x) (x&(-x))
#define maxn 3005
#define inf int(1e9)
#define mm 1000000007
#define ll long long
using namespace std;
ll f[maxn][maxn],ans1,ans2,ans3,ans4;
int n,m,mp[maxn][maxn];
char s[maxn];
ll read(){
ll x=,f=; char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}
while (isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
int main(){
n=read(); m=read();
rep(i,,n){
scanf("%s",s+);
rep(j,,m) if (s[j]=='#') mp[i][j]=;
}
if (mp[][]==||mp[][]==) {puts(""); return ;}
f[][]=;
rep(i,,n) rep(j,,m) if (!mp[i][j]) f[i][j]+=(f[i-][j]+f[i][j-])%mm;
ans1=f[n-][m]; ans3=f[n][m-];
clr(f,); f[][]=;
rep(i,,n) rep(j,,m) if (!mp[i][j]) f[i][j]+=(f[i-][j]+f[i][j-])%mm;
ans2=f[n][m-]; ans4=f[n-][m];
printf("%lld\n",((ans1*ans2-ans3*ans4)%mm+mm)%mm);
return ;
}
最新文章
- jquery函数理解与运用
- webapi修改tt模板给字段添加JsonIgnore特性解决转换json循环引用问题
- asp.net core 使用EF7 Code First 创建数据库,同时使用命令创建数据库
- Can not issue data manipulation statements with executeQuery() 异常处理
- 常用 CSS 中文字体 Unicode 编码表
- 统一样式的View应该用style修饰
- C#_Ajax_分页
- mysql的数据导入导出
- 通过url给action传中文参数乱码解决方案
- DTD验证XML(转)
- NetMQ
- ios 网络/本地播放器
- 使用angular4和asp.net core 2 web api做个练习项目(三)
- ruby klb.rb irb
- BIOS 中断向量表
- 在linux和本地系统之间进行数据传输的简单方法--lrzsz
- Java开发岗位面试题归类
- 背水一战 Windows 10 (77) - 控件(控件基类): ContentControl, UserControl, Page
- ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression笔记
- 20170719 Mysql 配置远端Mysql访问,增加表/存储过程
热门文章
- java.lang.StringBuilder和java.lang.StringBuffer (JDK1.8)
- JAVA Socket编程(一)之UDP通信
- bzoj 4012: [HNOI2015]开店
- 点击按钮显示隐藏DIV,点击DIV外面隐藏DIV
- Logback分别打印info日志和error日志
- 记录优雅的pythonic代码
- Java数组的创建和初始化
- MyBatis单个多个参数传递
- Git-分布式版本控制系统(一)
- python3之序列化(pickle&;json&;shelve)