HDU3037-卢卡斯(Lucas)定理模板 组合数模板

扩展lucas定理：
传送门1 传送门2 传送门3 传送门4
线性求逆元方法：
传送门
隔板法：传送门

前言：

 写上一个题的时候用到组合数了，就去百度了下，在此更新一下。

HDU3037：传送门

//一般p在1e6以下
#include 
using namespace std;
typedef long long LL;
int p;
inline void read(int &x){x = 0; char ch = getchar(), c = ch;while(ch < '0' || ch > '9') c = ch, ch = getchar();while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar();if(c == '-') x = -x;
}
inline LL exp_mod(LL a,int b){LL ret=1;while(b){if(b&1){ret=ret*a%p;}a=a*a%p;b>>=1;}return ret;
}
LL comb(int n, int m){if(m==0)return 1;LL x=1, y=1;m=min(m,n-m);for(int i=0;i<m;++i){x=x*(n-i)%p;y=y*(m-i)%p;}return x*exp_mod(y,p-2)%p;
}
LL lucas(int n, int m){if(n<m)return 0;if(n < p && m < p)return comb(n, m);return lucas(n % p, m % p) * lucas(n / p, m / p) % p;
}
int main(){int T;read(T);while(T--) {int n, m;read(n);read(m);read(p);printf("%lld\n", lucas(n + m, m));}return 0;
}

const int MX = 1e6 + 5;
LL F[MX], invF[MX];
LL power(LL a, LL b) {LL ret = 1;while (b) {if (b & 1) ret = ret * a % mod;a = a * a % mod;b >>= 1;}return ret;
}
void init() {F[0] = 1;for (int i = 1; i < MX; i++) F[i] = F[i - 1] * i % mod;invF[MX - 1] = power(F[MX - 1], mod - 2);for (int i = MX - 2; i >= 0; i--) invF[i] = invF[i + 1] * (i + 1) % mod;
}
LL COMB(LL n, LL m) {LL ret = 1;while (n && m) {LL nn = n % mod, mm = m % mod;if (nn < mm) return 0;ret = ((ret * F[nn] % mod) * invF[mm] % mod) * invF[nn - mm] % mod;n /= mod, m /= mod;}return ret;
}
LL lucas(LL n,LL m){if(m == 0)return 1;if(m > n) return 0;return (lucas(n/MOD,m/MOD)*comb(n%MOD,m%MOD)%MOD);
}

组合数模板：here

引自：clove_unique

错位重排公式：
D n = n ! × ∑ k = 0 n ( − 1 ) k k ! D_n=n!\times \sum_{k=0}^{n} \frac{(-1)^k}{k!} Dn​=n!×k=0∑n​k!(−1)k​

C n m = n ! m ! ∗ ( n − m ) ! C_n^m = \frac {n!}{m!*(n-m)!} Cnm​=m!∗(n−m)!n!​
C n m = C n − 1 m + C n − 1 m − 1 C_n^m = C_{n-1}^m + C_{n-1}^{m-1} Cnm​=Cn−1m​+Cn−1m−1​
C n m = C n n − m C_n^m = C_n^{n-m} Cnm​=Cnn−m​
C n + r + 1 r = ∑ i = 0 r C n + i i C_{n+r+1}^r = \sum_{i=0}^{r}C_{n+i}^i Cn+r+1r​=∑i=0r​Cn+ii​
C m n ∗ C n r = C m r ∗ C m − r n − r C_m^n * C_n^r = C_m^r * C_{m-r}^{n-r} Cmn​∗Cnr​=Cmr​∗Cm−rn−r​
∑ i = 0 m C m i = 2 m \sum_{i=0}^{m}C_m^i=2^m ∑i=0m​Cmi​=2m
C m 0 − C m 1 + C m 2 − . . . C m m = 0 C_m^0-C_m^1+C_m^2-...C_m^m = 0 Cm0​−Cm1​+Cm2​−...Cmm​=0
C m 0 + C m 2 + C m 4 . . . = C m 1 + C m 3 + C m 5 . . . = 2 m − 1 C_m^0+C_m^2+C_m^4...=C_m^1+C_m^3+C_m^5...=2^{m-1} Cm0​+Cm2​+Cm4​...=Cm1​+Cm3​+Cm5​...=2m−1
C n m = C a 0 × C b m + C a 1 × C b m − 1 . . . + C a m × C b 0        a + b = n C_{n}^{m} = C_{a}^{0}\times C_{b}^{m}+C_{a}^{1}\times C_{b}^{m-1}...+C_{a}^{m}\times C_{b}^{0}\;\;\;a+b = n Cnm​=Ca0​×Cbm​+Ca1​×Cbm−1​...+Cam​×Cb0​a+b=n
n ∗ C m n = m ∗ C m − 1 n − 1 n*C_m^n = m*C_{m-1}^{n-1} n∗Cmn​=m∗Cm−1n−1​
∑ i = 1 n C n i ∗ i = n ∗ 2 n − 1 \sum_{i=1}^{n}C_n^i * i = n * 2^{n-1} ∑i=1n​Cni​∗i=n∗2n−1
∑ i = 1 n C n i ∗ i 2 = n ∗ ( n + 1 ) ∗ 2 n − 2 \sum_{i=1}^{n}C_n^i * i^2 = n * (n+1) *2^{n-2} ∑i=1n​Cni​∗i2=n∗(n+1)∗2n−2
∑ i = 1 n ( C n i ) 2 = C 2 n n \sum_{i=1}^{n}(C_n^i)^2 = C_{2n}^n ∑i=1n​(Cni​)2=C2nn​
C m n = C m / p n / p ∗ C m % p n % p C_m^n = C_{m/p}^{n/p}*C_{m\%p}^{n\%p} Cmn​=Cm/pn/p​∗Cm%pn%p​

https://blog.csdn.net/litble/article/details/75913032

//http://codeforces.com/gym/100633/problem/J
n,m1e18mod1e6
#include
using namespace std;
typedef long long LL;
const int N = 5e1 + 7;
const int ME = 1e6 + 7;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
LL n, m, Mod;
LL ksm(LL a, LL b, LL mod){LL res = 1;for(;b;b>>=1,a=a*a%mod){if(b&1)res = res * a % mod;}return res;
}
void exgcd(LL a,LL b,LL &x,LL &y){if (!b) x=1LL,y=0LL;else exgcd(b,a%b,y,x),y-=a/b*x;
}
LL Inv(LL A,LL mod){if (!A) return 0LL;LL a=A,b=mod,x=0LL,y=0LL;exgcd(a,b,x,y);x=((x%b)+b)%b;if (!x) x+=b;return x;
}
LL Mul(LL n,LL pi,LL pk){if (!n) return 1LL;LL ans=1LL;if (n/pk){for (LL i=2;i<=pk;++i)if (i%pi) ans=ans*i%pk;ans=ksm(ans,n/pk,pk);}LL r = n%pk;for (LL i=2;i<=r;++i)//不足的部分if (i%pi) ans=ans*i%pk;return ans*Mul(n/pi,pi,pk)%pk;//再递归一层算(n/pi)!
}
LL COMB(LL n,LL m,LL mod,LL pi,LL pk){if (n<m) return 0;LL a=Mul(n,pi,pk),b=Mul(m,pi,pk),c=Mul(n-m,pi,pk);LL k=0LL,ans;for (LL i=n;i;i/=pi) k+=i/pi;for (LL i=m;i;i/=pi) k-=i/pi;for (LL i=n-m;i;i/=pi) k-=i/pi;ans=a*Inv(b,pk)%pk*Inv(c,pk)%pk*ksm(pi,k,pk)%pk;return ans*(mod/pk)%mod*Inv(mod/pk,pk)%mod;//CRT合并
}
LL exLucas(LL n, LL m, LL mod){LL ans = 0;for (LL x=Mod,i=2;i<=Mod;++i){if (x%i==0){LL pk = 1LL;while (x%i==0) pk*=i,x/=i;ans=(ans+COMB(n,m,Mod,i,pk))%Mod;}}return ans;
}
int main(){while(~scanf("%I64d%I64d%I64d",&n,&m,&Mod)){printf("%I64d\n",exLucas(n, m, Mod));}
}
求解n!可以分为3部分：第一部分是pi的幂的部分，也就是3^6即pi^⌊n/pi⌋，可以直接求解；
第二部分是一个新的阶乘，也就是6!即⌊n/pi⌋!，可以递归下去求解；
第三部分是除前两部分之外剩下的数 考虑第三部分如何求解 
发现第三部分在模pi^ki意义下是以pi^ki为周期的，
即(1∗2∗4∗5∗7∗8)≡(10∗11∗13∗14∗16∗17)(mod pi^ki)，所以只求pi^ki长度的即可；
可以按pr分块，一共n/pr块
但是还剩下一个孤立的19，可以发现剩下孤立的数长度不会超过pi^ki，只需要暴力求解即可 
e.最后一个问题是对于求出的m!%pi^ki和(n−m)!%pi^ki有可能与pi^ki不互质，无法求逆元 
所以要将m!%pi^ki和(n−m)!%pi^ki中质因子pi先全部除去，求出逆元后再全部乘回去 
计算n!中质因子p的个数x的公式为x=⌊n/p⌋+⌊n/p2⌋+⌊n/p3⌋+... 
递推式也可以写为f(n)=f(⌊n/p⌋)+⌊n/p⌋

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！