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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

O(n)求阶乘逆元(转)  

2014-12-26 20:48:34|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一个Catalan数的题,打表对每个数都求一次逆元会T,于是问到了一种求阶乘逆元的打表新方法。 比如打一个1~n的阶乘的逆元的表,假如叫inv[n],可以先用费马小定理什么的求出inv[n],再用递推公式求出前面的项。

  我们记数字 x 的逆元为f(x) (%MOD)。

  因为 n! = (n-1)! * n

  所以 f(n!) = f( (n-1)! * n) = f( (n-1)! ) * f(n)。

  所以 f( (n-1)! ) = f(n!) * f( f(n) ) = f(n!) * n   (逆元的逆元就是他自身)

这样子我们就可以用后项推出前面的项了。

 

题目是说,有一个人从0点开始走路,每次可以向前走或者向后走,每次可以走一步,但是所有的位置必须大于等于0,问走过2n步之后又回到0点有多少种方法。

  其实,如果我们把向前走看做是进栈,向后走看做是出栈,方法数就是Catalan数。

  所以我们只需要打一张表然后查表就好了。

  //阶乘
2     fac[0] = 1;
3     for (int i = 1; i < MAXN; i++) fac[i] = (fac[i-1]*i)%MOD;
4     //逆元
5     inv[MAXN-1] = myPow(fac[MAXN-1], MOD-2);
6     for (int i = MAXN-2; i > 0; i--) {
7         inv[i] = (inv[i+1]*(i+1))%MOD;
8     }
  评论这张
 
阅读(198)| 评论(6)

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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