nefu 628大组合数取模

题目连接:http://acm.nefu.edu.cn/JudgeOnline/problemshow.php?problem_id=628

关于ACM培训的通知

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)= n!/(m!*(n-m)!)   将分子和分母分别转化为素因子乘积的形式,然后上下同时约去,最后用快速幂搞一下就行了

如果p为素数的话,那么可以用lucas定理搞~

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
const int N=1e5+100;
using namespace std;
typedef long long ll;

int n,m,p,ct;
ll prime[2*N];
bool isprime[2*N];
int t[5][2*N];

void solve()
{
   ct=0;
   memset(isprime,false,sizeof(isprime));
   isprime[0]=isprime[1]=true;
   for(int i=2;i<=200100;i++)
   {
     if(!isprime[i])
     {
       prime[++ct]=i;
       for(int j=i+i;j<=200100;j+=i)
       isprime[j]=true;
     }
   }
}

int cal(int x,int pos)
{
   int i=1;
   for(;i<=ct&&prime[i]<=x;i++)
   {
       int ans=0,tmp=prime[i];
       while(x/tmp!=0)
       {
         ans+=x/tmp;
         tmp*=prime[i];
       }
       t[pos][i]=ans;
   }
   return i;
}

ll quick(ll a,int b )
{
   ll ans=1;
   while(b)
   {
      if(b&1)ans=ans*a%p;
      b=b/2;
      a=a*a%p;
   }
   return ans;
}

int main()
{
   int T;
   scanf("%d",&T);
   solve();
   while(T--)
   {
     scanf("%d%d%d",&n,&m,&p);
     memset(t,0,sizeof(t));

     if(n-1==0)
        {
            printf("1\n");
            continue;
        }
     if(n-1==1)
        {
            printf("%d\n",(n+m-2)%p);
            continue;
        }

     int t1=cal(n+m-2,1);
     int t2=cal(n-1,2);
     int t3=cal(m-1,3);
     int cnt=max(t1,max(t2,t3));

     for(int i=1;i<cnt;i++)
     {
       t[1][i]=t[1][i]-t[2][i]-t[3][i];
     }

     ll ans=1;
     for(int i=1;i<cnt;i++)
     {
         ans=ans*quick(prime[i],t[1][i])%p;
     }
     printf("%lld\n",ans);

   }
   return 0;
}
时间: 03-02

nefu 628大组合数取模的相关文章

大组合数取模之lucas定理模板,1&lt;=n&lt;=m&lt;=1e9,1&lt;p&lt;=1e6,p必须为素数

typedef long long ll; /********************************** 大组合数取模之lucas定理模板,1<=n<=m<=1e9,1<p<=1e6,p必须为素数 输入:C(n,m)%p 调用lucas(n,m,p) 复杂度:min(m,p)*log(m) ***********************************/ //ax + by = gcd(a,b) //传入固定值a,b.放回 d=gcd(a,b), x , y

Lucas定理--大组合数取模 学习笔记

维基百科:https://en.wikipedia.org/wiki/Lucas%27_theorem?setlang=zh 参考:http://blog.csdn.net/pi9nc/article/details/9615359 http://hi.baidu.com/lq731371663/item/d7261b0b26e974faa010340f http://hi.baidu.com/j_mat/item/8e3a891c258c4fe9dceecaba 综合以上参考,我做的一下总结:

大组合数取模

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1119 考虑从(1,1)->(n,m)必定会向下走n-1步,向右走m-1步,那么总的走法是C(n-1+m-1,m-1). 关于组合数取模:大神博客:http://blog.csdn.net/acdreamers/article/details/8037918 1 #include <iostream> 2 #include <string.h> 3 #

HDU 5698 大组合数取模(逆元)

瞬间移动 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1215    Accepted Submission(s): 600 Problem Description 有一个无限大的矩形,初始时你在左上角(即第一行第一列),每次你都可以选择一个右下方格子,并瞬移过去(如从下图中的红色格子能直接瞬移到蓝色格子),求到第n行第m列的格子有几

BZOJ 3129 [Sdoi2013]方程 不定方程解的个数+组合数取模

题意:链接 方法:不定方程解的个数+组合数取模 解析: 先看n1与n2的部分的限制. 对于后半部分的限制来说,我们直接减去An1+i?1就可以转化一下求正整数解. 但是前半部分呢? 跟上一道猴子那个很像. 所以我们容斥搞就行了. 但是这道题好像不好写的地方不在这? 这题TMD不就是礼物吗! 大组合数取模如何取? 请参见我<BZOJ 礼物>的题解. 另外吐槽题干 明明是X1+X2+-+Xn=m 并不是小于等于 代码: #include <cstdio> #include <cs

组合数取模终极版

以前讲述过很多组合数取模问题,详见:http://blog.csdn.net/acdreamers/article/details/8037918 今天,我们继续学习一些稍有难度的组合数取模问题,比如大组合数对合数取模,求大组合数的最后位数字等等. 首先来看组合数对合数取模问题 问题:求的值,其中和,并且是合数. 分析:先把素因子分解,然后转化为求,这里为素数,然后用CRT合并.所以现在重点来研究 如何求的值.这个问题AekdyCoin大神已经详细讲述了,如下链接     链接:http://h

组合数取模Lucas定理及快速幂取模

组合数取模就是求的值,根据,和的取值范围不同,采取的方法也不一样. 下面,我们来看常见的两种取值情况(m.n在64位整数型范围内) (1)  , 此时较简单,在O(n2)可承受的情况下组合数的计算可以直接用杨辉三角递推,边做加法边取模. (2) ,   ,并且是素数 本文针对该取值范围较大又不太大的情况(2)进行讨论. 这个问题可以使用Lucas定理,定理描述: 其中 这样将组合数的求解分解为小问题的乘积,下面考虑计算C(ni, mi) %p. 已知C(n, m) mod p = n!/(m!(

toj 4111 组合数取模 暴力分解

题目大意:组合数取模,n和m并不算大,p比较大且是合数. 思路:暴力分解+快速幂 注:暴力也是有区别的,分解质因数时可以用以下work函数,写的非常巧妙,摘录自互联网. 1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 typedef long long ll; 6 const ll mod = 1ll << 32; 7 const int N = 1000001; 8 const

排列组合+组合数取模 HDU 5894

1 // 排列组合+组合数取模 HDU 5894 2 // 题意:n个座位不同,m个人去坐(人是一样的),每个人之间至少相隔k个座位问方案数 3 // 思路: 4 // 定好m个人 相邻人之间k个座位 剩下就剩n-(m+1)*k个座位 5 // 剩下座位去插m个不同的盒子==就等价n个相同的球放m个不同的盒子 6 // 然后组合数出来了 7 // 乘n的话是枚举座位,除m是去掉枚举第一个座位的时候,剩下人相邻的座位相对不变的情况 8 9 #include <iostream> 10 #incl