插板法求得答案為:C(n+m,m)。
直接運用lucas定理即可,只是需要預處理出階乘值,否則會T。
1 #include <cstdio> 2 3 typedef long long ll; 4 const int N = 100000 ; 5 int f[N]; 6 7 void init( int p ) 8 { 9 f[ 0 ] = 1 ; 10 for ( int i = 1 ; i < p; i++ ) 11 { 12 f[i] = (ll) f[i - 1 ] * i % p; 13 } 14 } 15 16 int pow_mod( int a, int n, int mod ) 17 { 18 int ans = 1 , w = a % mod; 19 while ( n ) 20 { 21 if ( n & 1 ) 22 { 23 ans = (ll) ans * w % mod; 24 } 25 w = (ll) w * w % mod; 26 n = n >> 1 ; 27 } 28 return ans; 29 } 30 31 int c( int n, int m, int p ) 32 { 33 if ( m > n ) return 0 ; 34 int ans = (ll) f[n] * pow_mod( (ll) f[n - m] * f[m] % p, p - 2 , p ) % p; 35 return ans; 36 } 37 38 int lucas( int n, int m, int p ) 39 { 40 int ans = 1 ; 41 while ( m ) 42 { 43 ans = (ll) ans * c( n % p, m % p, p ) % p; 44 n = n / p, m = m / p; 45 } 46 return ans; 47 } 48 49 int main () 50 { 51 int t; 52 scanf( " %d " , & t); 53 while ( t-- ) 54 { 55 int n, m, p; 56 scanf( " %d%d%d " , &n, &m, & p); 57 init(p); 58 printf( " %d\n " , lucas( n + m, m, p )); 59 } 60 return 0 ; 61 }
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
