A Simple Chess
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2672 Accepted Submission(s): 713
Problem Description
There is a
n×m
board, a chess want to go to the position
(n,m) from the position (1,1) .
The chess is able to go to position (x2,y2) from the position (x1,y1) , only and if only x1,y1,x2,y2 is satisfied that (x2−x1)2+(y2−y1)2=5, x2>x1, y2>y1 .
Unfortunately, there are some obstacles on the board. And the chess never can stay on the grid where has a obstacle.
I want you to tell me, There are how may ways the chess can achieve its goal.
(n,m) from the position (1,1) .
The chess is able to go to position (x2,y2) from the position (x1,y1) , only and if only x1,y1,x2,y2 is satisfied that (x2−x1)2+(y2−y1)2=5, x2>x1, y2>y1 .
Unfortunately, there are some obstacles on the board. And the chess never can stay on the grid where has a obstacle.
I want you to tell me, There are how may ways the chess can achieve its goal.
Input
The input consists of multiple test cases.
For each test case:
The first line is three integers, n,m,r,(1≤n,m≤1018,0≤r≤100) , denoting the height of the board, the weight of the board, and the number of the obstacles on the board.
Then follow r lines, each lines have two integers, x,y(1≤x≤n,1≤y≤m) , denoting the position of the obstacles. please note there aren't never a obstacles at position (1,1) .
For each test case:
The first line is three integers, n,m,r,(1≤n,m≤1018,0≤r≤100) , denoting the height of the board, the weight of the board, and the number of the obstacles on the board.
Then follow r lines, each lines have two integers, x,y(1≤x≤n,1≤y≤m) , denoting the position of the obstacles. please note there aren't never a obstacles at position (1,1) .
Output
For each test case,output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer after module
110119
.
Sample Input
1 1 0 3 3 0 4 4 1 2 1 4 4 1 3 2 7 10 2 1 2 7 1
Sample Output
Case #1: 1 Case #2: 0 Case #3: 2 Case #4: 1 Case #5: 5
Author
UESTC
Source
2016 Multi-University Training Contest 6
题解
不贴代码了，差不多照着打的。
公 式
c(m,n)=m!/((m-n)!*n!)
性质1
C(n,m)= C(n,n-m)
性质2
C(n,m)= C(n-1,m-1)+C(n-1,m)
Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)
最后
以上就是完美大船最近收集整理的关于HDU 5794 A Simple Chess (lucas定理+费马小定理) A Simple Chess的全部内容，更多相关HDU内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复