epee_no_front's Notes
Happy learning! Happy Coding!
Toggle navigation
epee_no_front's Notes
主页
codeforces
人工智能
JAVA
python
Latex&Markdown
计算机系统
关于我
归档
标签
数论模板
ACM
模板
2020-05-26 15:02:30
233
0
0
admin
ACM
模板
#数论模板 [TOC] ##扩展欧几里得 ```cpp LL exgcd(LL a, LL b, LL& x, LL& y){ LL d = a; if(b != 0){ d = exgcd(b, a % b, y, x); y -= (a / b) * x; } else{ x = 1; y = 0; } return d; } ``` ##求逆元 ```cpp // 求a的逆元(模P意义下的) #define P 998244353 LL inv(LL a){ LL x, y; exgcd(a, P, x, y); return (P + x % P) % P; } ``` ##求 $C_x^k$ mod P ```cpp void init(){ f[1] = 1; // m 为组合数中x的最大值 for(LL i = 2; i <= m; i++){ f[i] = i* f[i - 1]; f[i] %= P; } return ; } LL mod_fact(LL x, LL& e){ init(); e = 0; if(x == 0) return 1; LL res = mod_fact(x / P, e); e += x / P; if(x / P % 2 != 0) return res * (P - f[x % P]) % P; return res * f[x % P] % P; } LL mod_comb(LL x, LL k){ if(x < 0 || k < 0 || x < k) return 0; LL e1, e2, e3; LL a1 = mod_fact(x, e1); LL a2 = mod_fact(k, e2); LL a3 = mod_fact(x - k, e3); if(e1 > e2 + e3) return 0; return a1 * inv(a2 * a3 % P) % P; } ```
上一篇:
ch01 Java语言基础
下一篇:
逻辑与形式化方法复习
0
赞
233 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
皖ICP备20006612号
皖公网安备 34020302000165号
文档导航
admin
epee_no_front's Notes
没有帐号? 立即注册