hud 5689 瞬间移动(组合数+逆元)

el/2024/6/24 17:18:18

http://acm.hdu.edu.cn/showproblem.php?pid=5698

有一个无限大的矩形,初始时你在左上角(即第一行第一列),每次你都可以选择一个右下方格子,并瞬移过去(如从下图中的红色格子能直接瞬移到蓝色格子),求到第nn行第mm列的格子有几种方案,答案对10000000071000000007取模。 

Input

多组测试数据。 

两个整数n,m(2≤n,m≤100000)n,m(2≤n,m≤100000) 

Output

一个整数表示答案

Sample Input

4 5

Sample Output

10

规律是a[i][j] = a[i-1][j] + a[i][j-1],  可以发现是个斜着的杨辉三角, 根据杨辉三角的通项公式C(m,i),

可以得出C(m+n-2, n-1)

涉及到除法取余就inv吧

#include<bits/stdc++.h> 
using namespace std;
using lon = long long;const lon mod= 1e9 + 7;
const lon M = 200005;// m+n 开两倍 
lon inv[M], f[M], finv[M];void getinv()
{finv[0] = finv[1] = f[0] = f[1] = inv[0] = inv[1] = 1;for(int i=2; i <= M; i++){f[i] = f[i-1] * i % mod;inv[i]=mod - mod / i * inv[mod%i] % mod;finv[i] = finv[i-1] * inv[i] % mod;}
}lon C(lon a, lon b)
{return f[a] * finv[b] % mod * finv[a-b] % mod;
}int main()
{lon n, m;getinv();while(cin >> n >> m)cout << C(m+n-4, m-2) << endl;return 0;
}

 


http://www.ngui.cc/el/3419443.html

相关文章

多态中成员变量的使用

Dog 继承 Animal 类&#xff0c; 多态中成员变量没有重写。

Java之数据结构

前言 Java工具包提供了强大的数据结构。在Java中的数据结构主要包括以下几种接口和类&#xff1a; 枚举&#xff08;Enumeration&#xff09;位集合&#xff08;BitSet&#xff09;向量&#xff08;Vector&#xff09;栈&#xff08;Stack&#xff09;字典&#xff08;Dictio…

各种办法解决IntelliJ IDEA控制台输出中文乱码问题

output输出乱码 试了网上很多办法 网上流行的方法&#xff1a;https://blog.csdn.net/liu865033503/article/details/81094575 都没有解决&#xff01;&#xff01;&#xff01; 重点要在 也有可能是c盘下的C:\Users\你自己的用户名\.IntelliJIdea2019.1\config配置下还有一…

IDEA 显示Cannot resolve plugin org.apache.maven.plugins:maven-site-plugin:3.3

今天将IntellIJ IDEA 关于Maven的配置总结一下&#xff0c;方便以后可参考。 一.配置Maven环境 前提是jdk环境变量已经配置好 1.下载apache-maven文件&#xff0c;选择自己需要的版本&#xff0c;地址&#xff1a; http://maven.apache.org/download.cgi 2.解压下载文件&…

javaweb项目前端找不到后台servlet解决办法

原因是注解里面没加 urlPatterns"/XXXXX" servlet必须是3.0以上 成功运行&#xff1a;

实现简单的用户名校验,是否存在(ajax)

实现百度注册框的用户名校验功能&#xff1a; 在输入框内输入一个用户名&#xff0c;如果此用户名存在&#xff0c;则红色显示一段文字&#xff0c;否则绿色显示 用的是Jquery和jackson 目录结构&#xff1a; 前端index.html: <!DOCTYPE html> <html lang"en&…

ccf 201909-2 小明种苹果(续)

#include<bits/stdc.h> using namespace std;bool vis[20005]; //第i棵树是否掉过苹果 int main() {long n, ans_sum 0, ans_has 0, ans_con 0;cin >> n;for(int i 1; i < n; i){int start, m, x;bool flag true;cin >> m >> start;for(int j…

const位置的含义

int num 1024; const int num2 num1; //只能第一次赋值 num2 2048 // 报错const int * p &num; //const 在 * 前面时&#xff0c;指针的位置可以修改&#xff0c;但不能通过指针修改指向的变量 int const * p &num; //同上 int * const p &num;//const 在 …

武林秘籍

面向对象&#xff08;一&#xff09;----类的基础语法 &#xff1a; 第1关&#xff1a;类的声明与定义 # 请在下面填入定义Book类的代码 #********** Begin *********# class Book: #********** End *********## 书籍类def __init__(self,name,author,data,version):self.nam…

C++技能树

来源于水印。