Gym - 100625F Count Ways 快速幂+容斥原理
2024-10-21 02:46:27
题意: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);
}
}
最新文章
- Error configuring application listener of class。。。NoClassDefFoundError。。某Listener 之启动tomcat报错
- JAX-WS(一)之使用wsgen从Java创建简单的WebService
- activemq重启
- jQuery on()方法绑定动态元素的点击事件
- 《数据结构与算法分析:C语言描述》读书笔记------List的C语言实现
- Java字符串进阶
- JavaWeb(一)Servlet中的request与response
- lesson - 1 笔记 网络连接 /putty 密钥登陆
- 一个Dotnet数据框架的bug
- JS案例六_1:添加城市
- Git使用详细教程(4):git rm使用详解
- 【C#复习总结】细说委托
- Centos6中Docker使用中国官方镜像加速
- element-ui上传文件带token
- 在Ubuntu环境下安装eclipse
- HDU 5985 Lucky Coins(概率)
- RRT路径规划算法
- mysqladmin: connect to server at &#39;localhost&#39; failed
- IntelliJ IDEA 配置JSP &; Servlet开发环境
- 全面了解 Nginx 主要应用场景