\(EXLucas\) 扩展卢卡斯定理
·题意
试求：
\[C^{m}_n \mod P \ \ \ \ \ \ \ \ \ \ \ ( P \in N ^* ) \]注意， \(P\) 非整数。
·转化
可以给他进行质因数分解，成为：
\[P = \prod_{ i = 1 } ^ k p _ i ^ { { \alpha } _ i } \]\[\begin{cases} x \equiv C^{m}_n ( \mod p_1^{ { \alpha }_1 } ) \\ \dots \\ x \equiv C^{m}_n ( \mod p _ i ^ { { \alpha } _ i } ) \end{cases}\]然后因为这些后面的模数全都是互质的，所以可以用 \(CRT\) 解决他。
直接拿出随便一个式子，
得到的是
\[C_n^m \mod p _ i ^ { { \alpha } _ i } \]展开得：
\[\frac{n!}{m! \times (n-m)! } \mod p _ i ^ { { \alpha } _ i } \]但是不能把分母部分直接转逆元，因为你怎么知道 $ gcd( \beta! , p _ i ^ { { \alpha } _ i } ) $
所以你可以定义一个 $ f ( x ) 和 g( x ) $
\(f(x):\) 表示 \(x!\) 中除去所有 \(p\) 剩余的值
\(g(x):\) 表示 \(x!\) 中可以除几个 \(p\)
所以式子变成：
\[\frac{ f ( n ) }{f ( n - m ) \times f ( m ) } \times p ^ { g ( n ) - g( n - m ) - g( m ) } \mod p _ i ^ { { \alpha } _ i } \]现在求子任务：
\[n! \mod p _ i ^ { { \alpha } _ i } \]可以将能除 \(p\) 的数提出来。
得：
\[( p \times 2p \times \dots \times \left \lfloor \frac{n}{p} \right \rfloor ) \times \prod_{i=1}^{n}{ [ i \mod p \neq 0 ]i } \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \mod p _ i ^ { { \alpha } _ i } \]每个地方分一下，得：(写这玩意属实恶心)
\[=\left( \left\lfloor \frac{ n }{ p } \right\rfloor ! \right) \times p ^{\left\lfloor \frac{ n }{ p } \right\rfloor } \times \left(\prod_{i=1}^{p _ i ^ { { \alpha } _ i }}[i \mod p \ne 0 ]i \right)\times \left(\prod_{i=p _ i ^ { { \alpha } _ i }+1}^{ 2 \times p _ i ^ { { \alpha } _ i } }[ i \mod p \neq 0 ]\right) \dots \left(\prod_{i=(\left\lfloor \frac{ n }{ p } \right\rfloor-1)\times p _ i ^ { { \alpha } _ i } }^{\left\lfloor \frac{ n }{ p } \right\rfloor \times p _ i ^ { { \alpha } _ i }}[ i \mod p \neq 0 ]\right )\times \left(\prod_{ i = \left\lfloor \frac{ n }{ p } \right\rfloor \times p _ i ^ { { \alpha } _ i }}^{n}[i \mod p \neq 0 ]\right) \ \ \ \ \mod p _ i ^ { { \alpha } _ i } \]最后面的是剩余的。
注意，你的后面是有个取模的，
所以........
\[=\left( \left\lfloor \frac{ n }{ p } \right\rfloor ! \right) \times p ^{\left\lfloor \frac{ n }{ p } \right\rfloor } \times \left(\prod_{i=1}^{p _ i ^ { { \alpha } _ i }}[ i \mod p \neq 0 ]\right)^{\left\lfloor \frac{ n }{ p } \right\rfloor}\times \left(\prod_{ i = \left\lfloor \frac{ n }{ p } \right\rfloor \times p _ i ^ { { \alpha } _ i }}^{n}[i \mod p \neq 0 ]\right) \ \ \ \ \mod p _ i ^ { { \alpha } _ i } \]由于这是\(n!\),我们想要 \(f(n)\)
首先的，\(f(n)\) 中 肯定没有 \(p\) , 那么将有 \(p\) 的全提出来， （注意，\(\left\lfloor \frac{ n }{ p } \right\rfloor ! 可能含有\)）
再浅浅的变一下形：
\[=f\left(\left\lfloor \frac{ n }{ p } \right\rfloor \right) \times p^{g(\left\lfloor \frac{ n }{ p } \right\rfloor)} \times p ^{\left\lfloor \frac{ n }{ p } \right\rfloor } \times \left(\prod_{i=1}^{p _ i ^ { { \alpha } _ i }}[ i \mod p \neq 0 ]\right)^{\left\lfloor \frac{ n }{ p } \right\rfloor}\times \left(\prod_{ i = \left\lfloor \frac{ n }{ p } \right\rfloor \times p _ i ^ { { \alpha } _ i }}^{n}[i \mod p \neq 0 ]\right) \ \ \ \ \mod p _ i ^ { { \alpha } _ i } \]那么 $f( n ) $ 就是将所有含 \(p\) 的式子择出去 （烦恼丢出去）
得：
\[f(n) = f\left(\left\lfloor \frac{ n }{ p } \right\rfloor \right) \times \left(\prod_{i=1}^{p _ i ^ { { \alpha } _ i }}[ i \mod p \neq 0 ]\right)^{\left\lfloor \frac{ n }{ p } \right\rfloor}\times \left(\prod_{ i = \left\lfloor \frac{ n }{ p } \right\rfloor \times p _ i ^ { { \alpha } _ i }}^{n}[i \mod p \neq 0 ]\right) \ \ \ \ \mod p _ i ^ { { \alpha } _ i } \]同时我们也可以得到：
\[g(n)=g \left(\left\lfloor \frac{ n }{ p } \right\rfloor \right) + \left\lfloor \frac{ n }{ p } \right\rfloor \]这个可以通过择出去得 \(p\) 得知。
· \(Code\)
\[exlucas の 板子 \]点击查看代码
#include<bits/stdc++.h>
using namespace std ;
#define int long long
const int N = 1000010 ;
int prime_num[ N ] , prime[ N ] , tot ;
int bemod[ N ] , relive[ N ] ;
inline int read( )
{
int x = 0 , f = 1 ;
char c = getchar( ) ;
while ( c > '9' || c < '0' )
{
if( c == '-' )
{
f = -f ;
}
c = getchar( ) ;
}
while ( c >= '0' && c <= '9' )
{
x = x * 10 + c - '0' ;
c = getchar( ) ;
}
return x * f ;
}
int exgcd( int a , int b , int &x , int &y )
{
if ( ! b )
{
x = 1;
y = 0;
return a;
}
int d = exgcd( b , a % b , x , y ) ;
int t = x ;
x = y ;
y = t - ( a / b ) * y ;
return d ;
}
int inv( int Original , int mo )
{
int x , y ;
exgcd( Original , mo , x , y ) ;
return ( x + mo ) % mo ;
}
void decompose( int mod )
{
int tmp = mod ;
for ( int i = 2 ; i <= sqrt( mod ) ; ++ i )
{
if( tmp % i == 0 )
{
prime[ ++ tot ] = i ;
while( tmp % i == 0 )
{
tmp /= i ;
prime_num[ tot ] ++ ;
}
}
}
if( tmp != 1 )
{
prime[ ++ tot ] = tmp ;
prime_num[ tot ] ++ ;
}
return ;
}
int g( int n , int p )
{
if( n < p )
{
return 0 ;
}
return ( n / p ) + g( n / p , p ) ;
}
inline int Quick_Pow( int a , int b , int c )
{
int ans = 1 ;
a %= c ;
while ( b > 0 )
{
if( b & 1 ) ans = ( ans * a ) % c ;
b >>= 1 ;
a = ( a * a ) % c ;
}
return ans ;
}
inline int Regular_Quick_Pow( int a , int b )
{
int ans = 1 ;
while ( b > 0 )
{
if( b & 1 ) ans *= a ;
b >>= 1 ;
a *= a ;
}
return ans ;
}
int f( int n , int p , int kala )
{
if( !n ) return 1 ;
int res = 1 , vim = 1 ;
// int kala = Regular_Quick_Pow( p , k ) ;
// cout << kala << '\n' ;
// if( n >= kala )
// {
for ( int i = 1 ; i <= kala ; ++ i )
{
if( i % p != 0 )
{
res = ( res * i ) % kala ;
}
}
// }
int up = n / kala ;
res = Quick_Pow( res , up , kala ) ;
for( int i = kala * ( n / kala ) ; i <= n ; ++ i )
{
if( i % p != 0 ) vim = ( vim * ( i % kala ) ) % kala ;
}
int returning = ( ( ( ( f( n / p , p , kala ) * vim ) % kala ) * res ) % kala ) ;
// cout << returning << '\n' ;
return returning ;
}
int EXCRT( int r[ ] , int mo[ ] , int n )
{
int m1 , m2 , r1 , r2 , p , q ;
m1 = mo[ 1 ] , r1 = r[ 1 ] ;
for( int i = 2 ; i <= n ; ++ i )
{
int x , y ;
m2 = mo[ i ] , r2 = r[ i ] ;
int d = exgcd( m1 , m2 , x , y ) ;
//cout << d << '\n' ;
if( ( r2 - r1 ) % d != 0 ) return -1 ;
x = x * ( r2 - r1 ) / d ;
int delta = m2 / d ;
x = ( x % delta + delta ) % delta ;
r1 = m1 * x + r1 ;
m1 = m1 * delta ;
}
return ( r1 % m1 + m1 ) % m1 ;
}
int n , m , mod , ksum ;
void get_fge( int now , int num , int i )
{
int kala = Regular_Quick_Pow( now , num ) ;
int C1 = f( n , now , kala ) ;
int C2 = f( m , now , kala ) ;
int C3 = f( n - m , now , kala ) ;
int G1 = g( n , now ) , G2 = g( m , now ) , G3 = g( n - m , now ) ;
bemod[ i ] = ( ( ( ( ( C1 * inv( C2 , kala ) ) % kala ) * inv( C3 , kala ) % kala ) % kala ) * ( Quick_Pow( now , G1 - G2 - G3 , kala ) ) % kala ) % kala ;
relive[ i ] = kala ;
}
signed main( )
{
#ifndef ONLINE_JUDGE
freopen( "1.in" , "r" , stdin ) ;
freopen( "1.out", "w" , stdout ) ;
#endif
// 扩展卢卡斯板子 -> C( n , m ) mod ( p ∈ N * )
cin >> n >> m >> mod ;
// decompose( mod ) ;
int tmp = mod ;
for ( int i = 2 ; i <= sqrt( mod ) ; ++ i )
{
if( tmp % i == 0 )
{
prime[ ++ tot ] = i ;
while( tmp % i == 0 )
{
tmp /= i ;
prime_num[ tot ] ++ ;
}
get_fge( prime[ tot ] , prime_num[ tot ] , tot ) ;
}
}
if( tmp != 1 )
{
prime[ ++ tot ] = tmp ;
prime_num[ tot ] ++ ;
get_fge( prime[ tot ] , prime_num[ tot ] , tot ) ;
}
int ans = 0 ;
for ( int i = 1 ; i <= tot ; ++ i )
{
int mer = mod / relive[ i ] ;
int invmer = inv( mer , relive[ i ] ) ;
ans = ( ans + ( mer * ( invmer * bemod[ i ] ) % mod ) % mod ) % mod ;
}
cout << ans ;
}