题意:n*m的格子,中间有若干点不能走,问从左上角到右下角有多少种走法。

思路:CountWay(i,j) 表示从 i 点到 j 点的种数。然后用容斥原理加加减减解决

 #pragma comment(linker, "/STACK:1000000000")
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define LL long long
#define MAXN 100005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
struct Node
{
LL x, y;
};
Node p[MAXN];
LL factor[ * MAXN], w[ * MAXN];
LL res[MAXN];
bool compare(Node a, Node b)
{
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
LL CountWay(LL x, LL y)
{
LL res = factor[x + y];
res = res * w[x] % MOD;
res = res * w[y] % MOD;
return res;
}
LL quick_power(LL x, LL y)
{
if (y == ){
return (LL);
}
if (y == ){
return x % MOD;
}
LL res = quick_power(x, y >> );
res = (res * res) % MOD;
if (y & ){
res = (res * x) % MOD;
}
return res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // OPEN_FILE
int T;
factor[] = ;
w[] = ;
for (LL i = ; i <= ; i++){
factor[i] = (factor[i - ] * i) % MOD;
w[i] = quick_power(factor[i], MOD - );
}
scanf("%d", &T);
LL n, m, k;
while (T--){
scanf("%I64d%I64d%I64d", &n, &m, &k);
for (int i = ; i <= k; i++){
scanf("%I64d%I64d", &p[i].x, &p[i].y);
}
p[k + ].x = n;
p[k + ].y = m;
sort(p + , p + k + , compare);
for (int i = ; i <= k + ; i++){
res[i] = CountWay(p[i].x - , p[i].y - );
}
for (int i = ; i <= k + ; i++){
for (int j = i + ; j <= k + ; j++){
if (p[j].x < p[i].x || p[j].y < p[i].y) continue;
//if(p[j].x == p[i].x && p[j].y == p[i].y) continue;
res[j] = (res[j] - (res[i] * CountWay(p[j].x - p[i].x, p[j].y - p[i].y)) % MOD) % MOD;
}
}
printf("%I64d\n", (res[k + ] + MOD) % MOD);
}
}

最新文章

  1. Error configuring application listener of class。。。NoClassDefFoundError。。某Listener 之启动tomcat报错
  2. JAX-WS(一)之使用wsgen从Java创建简单的WebService
  3. activemq重启
  4. jQuery on()方法绑定动态元素的点击事件
  5. 《数据结构与算法分析:C语言描述》读书笔记------List的C语言实现
  6. Java字符串进阶
  7. JavaWeb(一)Servlet中的request与response
  8. lesson - 1 笔记 网络连接 /putty 密钥登陆
  9. 一个Dotnet数据框架的bug
  10. JS案例六_1:添加城市
  11. Git使用详细教程(4):git rm使用详解
  12. 【C#复习总结】细说委托
  13. Centos6中Docker使用中国官方镜像加速
  14. element-ui上传文件带token
  15. 在Ubuntu环境下安装eclipse
  16. HDU 5985 Lucky Coins(概率)
  17. RRT路径规划算法
  18. mysqladmin: connect to server at &#39;localhost&#39; failed
  19. IntelliJ IDEA 配置JSP &amp; Servlet开发环境
  20. 全面了解 Nginx 主要应用场景

热门文章

  1. Python求阴影部分面积
  2. 表达式中含or的赋值
  3. P1017 进制转换 (负进制转换)
  4. 2019年北航OO第三单元(JML规格任务)总结
  5. 【C语言】递归函数DigitSum(n)
  6. Thinking in States
  7. POJ 1741 Tree 树的分治(点分治)
  8. angularjs 缓存 $q
  9. angularjs 标签指令
  10. angularjs作用域和函数调用