首页 > 代码库 > HNU 12933 Random Walks Catalan数 阶乘求逆元新技能
HNU 12933 Random Walks Catalan数 阶乘求逆元新技能
一个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数。
所以我们只需要打一张表然后查表就好了。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <string> 8 #include <queue> 9 #include <stack>10 #include <vector>11 #include <map>12 #include <set>13 #include <functional>14 #include <cctype>15 #include <time.h>16 17 using namespace std;18 19 typedef __int64 ll;20 21 const int INF = 1<<30;22 const int MAXN = (int) 2e6+55;23 const ll MOD = (ll) 1e9+7;24 25 ll ans[MAXN];26 ll fac[MAXN];27 ll inv[MAXN];28 29 inline ll myPow(ll x, ll n) {30 ll res = 1;31 while (n>0) {32 if (n&1) res = (res*x)%MOD;33 x = (x*x)%MOD;34 n >>= 1;35 }36 return res;37 }38 39 int main() {40 #ifdef Phantom0141 freopen("HNU12933.txt", "r", stdin);42 #endif //Phantom0143 44 fac[0] = 1;45 for (int i = 1; i < MAXN; i++) fac[i] = (fac[i-1]*i)%MOD;46 inv[MAXN-1] = myPow(fac[MAXN-1], MOD-2);47 for (int i = MAXN-2; i > 0; i--) {48 inv[i] = (inv[i+1]*(i+1))%MOD;49 }50 51 for (int i = 1; i < (MAXN>>1); i++)52 ans[i] = (((fac[2*i]*inv[i+1])%MOD)*inv[i])%MOD;53 54 int T;55 scanf("%d", &T);56 57 int n;58 while (T--) {59 scanf("%d", &n);60 printf("%I64d\n", ans[n]);61 }62 63 return 0;64 }
其中，这个是用来打阶乘逆元的：
1 //阶乘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 }
HNU 12933 Random Walks Catalan数 阶乘求逆元新技能
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。