2018-08-24发表2018-08-24更新acm模板1 分钟读完 (大约166个字)0次访问求逆元和组合数模板求逆元$O(n)$求逆元1234ll inv[maxn];inv[1] = 1;rep(i,2,maxn) inv[i] = inv[mod%i] * (mod-mod/i) % mod; $O(n)$求阶乘1234ll f[maxn];ll f[1] = 1;rep(i,2,maxn) f[i] = f[i-1]*i; 求$n\choose k$123456789101112131415161718ll cur,p[maxn],q[maxn],inv[maxn];ll C(ll n,ll k){ return p[n]*q[k]%mod*q[n-k]%mod;}ll c(ll n,ll k){ if(n<maxn) return C(n,k); if(!k) return 1; return cur = cur*inv[k]%mod*((n-k+1)%mod)%mod;}void init(){ p[0]=p[1]=q[0]=q[1]=inv[0]=inv[1]=1; for(ll i = 2;i<maxn;i++){ inv[i] = (mod-mod/i)*inv[mod%i]%mod; q[i] = q[i-1] * inv[i] % mod; p[i] = p[i-1] * i % mod; }}//在每次的时候就得cur初始化为1 求$A^k_n$123int A(int n,int k){ return c(n,k)*p[k]%mod;} 求逆元和组合数模板https://www.cheasim.com/acm%E6%A8%A1%E6%9D%BF/2018/08/24/%E6%B1%82%E9%80%86%E5%85%83%E5%92%8C%E7%BB%84%E5%90%88%E6%95%B0%E6%A8%A1%E6%9D%BF.html作者CheaSim发布于2018-08-24更新于2018-08-24许可协议