注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2982]combination  

2014-10-15 19:44:52|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2982: combination

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 131  Solved: 72
[Submit][Status]

Description

LMZn个不同的基友,他每天晚上要选m个进行[河蟹],而且要求每天晚上的选择都不一样。那么LMZ能够持续多少个这样的夜晚呢?当然,LMZ的一年有10007天,所以他想知道答案mod 10007的值。(1<=m<=n<=200,000,000)

Input

  第一行一个整数t,表示有t组数据。(t<=200)
  接下来t行每行两个整数n, m,如题意。

Output

T行,每行一个数,为C(n, m) mod 10007的答案。

Sample Input

4
5 1
5 2
7 3
4 2

Sample Output

5
10
35
6

Solution

都告诉我们了求C(n,m)%10007,没有见过如此直白的题面。

Lucas定理:C(n,m)%p=C(b1,a1)*C(b2,a2)*...*C(bx,ax)%p,其中b,a分别为n,m的p进制展开。

C(b,a)=b!/a!/(b-a)!

当b<a时,由阶乘定义,(b-a)! = oo,于是C(b,a)=0

于是只要处理出阶乘以及阶乘的逆元。

线性求逆元做法:

inv[i]=p-p/i*inv[p%i]%p

具体是:设p=ia+b,因为是在mod p意义下,因此ia+b=0,于是1/i=-a/b=-(p/i)/(p%i)=p-p/i*inv[p%i]%p

最后+p是因为保证一下inv[]>=0否则可能出现一些奇奇怪怪的问题。

还有一点就是把inv[]前缀做乘积时,不要忘了inv[0]=1,因为1/0!=1

Code

/**************************************************************
    Problem: 2982
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:960 kb
****************************************************************/
 
#include<cstdio>
typedef long long ll;
int i;ll n,m,k,p=10007,fac[10010],inv[10010],t;
ll C(ll b,ll a)
{
    if(a>b)return 0;
    return fac[b]*inv[a]%p*inv[b-a]%p;
}
ll lucas(ll b,ll a)
{
    return a==0?1:C(b%p,a%p)*lucas(b/p,a/p)%p;
}
int main()
{
    for(inv[0]=inv[1]=1,i=2;i<p;i++)inv[i]=p-p/i*inv[p%i]%p;
    for(fac[1]=1,i=2;i<p;i++)fac[i]=fac[i-1]*i%p,inv[i]=inv[i]*inv[i-1]%p;
    for(scanf("%d",&t);t--;)
    {
        scanf("%lld%lld",&n,&m);
        printf("%lld\n",lucas(n,m));
    }
}
  评论这张
 
阅读(49)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018