热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

NEFU628Gardenvisiting(数论)

GardenvisitingProblem:628TimeLimit:1000msMemoryLimit

            Garden visiting

    Problem:628  Time Limit:1000ms  Memory Limit:65536K

Description

There is a very big garden at Raven’s residence. We regard the garden as an n*m rectangle. Raven’s house is at the top left corner, and the exit of the garden is at the bottom right. He can choose to take one step to only one direction (up, down, left or right) each time. Raven wants to go out of the garden as quickly as possible, so he wonders how many routes he could choose. 
Raven knows there are many possible routes, so he only wants to know the number, which is the result that the total number of possible routes modes a given value p. He knows it is a simple question, so he hopes you may help him to solve it. 

Input

The first line of the input contains an integer T, which indicates the number of test cases.
Then it is followed by three positive integers n, m and p (1 <= n, m, p <= 10^5), showing the length and width of the garden and p to be the mod of the result. 

Output

For each case, output one number to show the result (the sum modes p).

Sample Input

3
2 2 5
2 6 16
6 6 24

Sample Output

2
6
12

Hint

Sample 1: There are 2 routes in total. 
Sample 2: There are 6 routes in total.
Sample 3: There are 252 routes in total.

题意:给定一个n*m的矩阵,让你求从左上角走到右下角有多少方法。

析:很明显一个组合问题,C(n+m-2, m-1),这就是答案,我们只要计算这个就好,所以暴力去分解分子和分母,然后再乘起来。

代码如下:

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
//#include 
//#define freopenr freopen("in.txt", "r", stdin)
//#define freopenw freopen("out.txt", "w", stdout)
using namespace std;
//using namespace std :: tr1;

typedef long long LL;
typedef pair P;
const int INF = 0x3f3f3f3f;
//const double inf = 0x3f3f3f3f3f3f;
//const LL LNF = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 10005;
//const LL mod = 10000000000007;
const int N = 1e6 + 5;
const int dr[] = {-1, 0, 1, 0, 1, 1, -1, -1};
const int dc[] = {0, 1, 0, -1, 1, -1, 1, -1};
const char *Hex[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
inline LL gcd(LL a, LL b){  return b == 0 ? a : gcd(b, a%b); }
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline int Min(int a, int b){ return a  b ? a : b; }
inline LL Min(LL a, LL b){ return a  b ? a : b; }
inline bool is_in(int r, int c){
    return r >= 0 && r = 0 && c  prime;
bool a[200050];

void init(){
    int m = sqrt(200050+0.5);
    memset(a, false, sizeof a);
    for(int i = 2; i <= m; ++i)  if(!a[i])
        for(int j = i*i; j <200050; j += i)  a[j] = true;
    for(int i = 2; i <200050; ++i)  if(!a[i])  prime.push_back(i);
}
int p;

LL quick_pow(LL a, int n){
    LL ans = 1;
    while(n){
        if(n & 1)  ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}

int cal(int x, int n){
    int ans = 0;
    while(n){
        ans += n / x;
        n /= x;
    }
    return ans;
}

LL solve(int n, int m){
    LL ans = 1;
    for(int i = 0; i > T;
    while(T--){
        scanf("%d %d %d", &n, &m, &p);
        n += m-2;
        --m;
        printf("%lld\n", solve(n, m));
    }
    return 0;
}

 


推荐阅读
author-avatar
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有