Brief description :
… 大家好我是 Lucas 定理 .. .
http://en.wikipedia.org/wiki/Lucas%27_theorem
Analysis :
… 可以用我来求 mod p 组合数..
。。本模板 p 要控制在 10000 以内。
。。对于求阶乘逆元,似乎有稍微快一些的方法。
/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **/ #include <algorithm> #include <iostream> #include <iomanip> #include <sstream> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <bitset> #include <queue> #include <cmath> #include <ctime> #include <list> #include <set> #include <map> using namespace std; #define REP(i, n) for (int i=0;i<int(n);++i) #define FOR(i, a, b) for (int i=int(a);i<int(b);++i) #define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i) #define REP_1(i, n) for (int i=1;i<=int(n);++i) #define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i) #define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i) #define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i) #define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i) #define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i) #define REP_N(i, n) for (i=0;i<int(n);++i) #define FOR_N(i, a, b) for (i=int(a);i<int(b);++i) #define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i) #define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i) #define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i) #define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i) #define REP_1_N(i, n) for (i=1;i<=int(n);++i) #define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i) #define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i) #define REP_C_N(i, n) for (n____=int(n),i=0;i<n____;++i) #define FOR_C_N(i, a, b) for (b____=int(b),i=a;i<b____;++i) #define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i>=a____;--i) #define REP_1_C_N(i, n) for (n____=int(n),i=1;i<=n____;++i) #define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i<=b____;++i) #define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i>=a____;--i) #define DO(n) while(n--) #define DO_C(n) int n____ = n; while(n____--) #define TO(i, a, b) int s_=a<b?1:-1,b_=b+s_;for(int i=a;i!=b_;i+=s_) #define TO_1(i, a, b) int s_=a<b?1:-1,b_=b;for(int i=a;i!=b_;i+=s_) #define SQZ(i, j, a, b) for (int i=int(a),j=int(b)-1;i<j;++i,--j) #define SQZ_1(i, j, a, b) for (int i=int(a),j=int(b);i<=j;++i,--j) #define REP_2(i, j, n, m) REP(i, n) REP(j, m) #define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m) #define ALL(A) A.begin(), A.end() #define LLA(A) A.rbegin(), A.rend() #define CPY(A, B) memcpy(A, B, sizeof(A)) #define INS(A, P, B) A.insert(A.begin() + P, B) #define ERS(A, P) A.erase(A.begin() + P) #define BSC(A, X) find(ALL(A), X) // != A.end() #define CTN(T, x) (T.find(x) != T.end()) #define SZ(A) int(A.size()) #define PB push_back #define MP(A, B) make_pair(A, B) #define Rush int T____; RD(T____); DO(T____) #pragma comment(linker, "/STACK:36777216") #pragma GCC optimize ("O2") #define Ruby system("ruby main.rb") #define Haskell system("runghc main.hs") #define Pascal system("fpc main.pas") typedef long long LL; typedef double DB; typedef unsigned UINT; typedef unsigned long long ULL; typedef vector<int> VI; typedef vector<char> VC; typedef vector<string> VS; typedef vector<LL> VL; typedef vector<DB> VD; typedef set<int> SI; typedef set<string> SS; typedef set<LL> SL; typedef set<DB> SD; typedef map<int, int> MII; typedef map<string, int> MSI; typedef map<LL, int> MLI; typedef map<DB, int> MDI; typedef map<int, bool> MIB; typedef map<string, bool> MSB; typedef map<LL, bool> MLB; typedef map<DB, bool> MDB; typedef pair<int, int> PII; typedef pair<int, bool> PIB; typedef vector<PII> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; typedef set<PII> SII; typedef map<PII, int> MPIII; typedef map<PII, bool> MPIIB; /** I/O Accelerator **/ /* ... :" We are I/O Accelerator ... Use us at your own risk ;) ... " .. */ template<class T> inline void RD(T &); template<class T> inline void OT(const T &); inline int RD(){ int x; RD(x); return x;} template<class T> inline T& _RD(T &x){ RD(x); return x;} inline void RC(char &c){scanf(" %c", &c);} inline void RS(char *s){scanf("%s", s);} template<class T0, class T1> inline void RD(T0 &x0, T1 &x1){RD(x0), RD(x1);} template<class T0, class T1, class T2> inline void RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2);} template<class T0, class T1, class T2, class T3> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3);} template<class T0, class T1, class T2, class T3, class T4> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);} template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);} template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);} template<class T0, class T1> inline void OT(T0 &x0, T1 &x1){OT(x0), OT(x1);} template<class T0, class T1, class T2> inline void OT(T0 &x0, T1 &x1, T2 &x2){OT(x0), OT(x1), OT(x2);} template<class T0, class T1, class T2, class T3> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);} template<class T0, class T1, class T2, class T3, class T4> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);} template<class T0, class T1, class T2, class T3, class T4, class T5> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);} template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void OT(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);} template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));} template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);} template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);} template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);} template<class T0, class T1, class T2, class T3, class T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);} template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);} template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);} template<class T> inline void CLR(T &A){A.clear();} template<class T0, class T1> inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);} template<class T0, class T1, class T2> inline void CLR(T0 &A0, T1 &A1, T2 &A2){CLR(A0), CLR(A1), CLR(A2);} template<class T0, class T1, class T2, class T3> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);} template<class T0, class T1, class T2, class T3, class T4> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);} template<class T0, class T1, class T2, class T3, class T4, class T5> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);} template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);} template<class T> inline void CLR(T &A, int n){REP(i, n) CLR(A[i]);} template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));} template<class T0, class T1> inline void FLC(T0 &A0, T1 &A1, int x){FLC(A0, x), FLC(A1, x);} template<class T0, class T1, class T2> inline void FLC(T0 &A0, T1 &A1, T2 &A2){FLC(A0), FLC(A1), FLC(A2);} template<class T0, class T1, class T2, class T3> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3){FLC(A0), FLC(A1), FLC(A2), FLC(A3);} template<class T0, class T1, class T2, class T3, class T4> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4);} template<class T0, class T1, class T2, class T3, class T4, class T5> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5);} template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){FLC(A0), FLC(A1), FLC(A2), FLC(A3), FLC(A4), FLC(A5), FLC(A6);} template<class T> inline void SRT(T &A){sort(ALL(A));} template<class T, class C> inline void SRT(T &A, C B){sort(ALL(A), B);} /** Add - On **/ int MOD = 1000000007; const int INF = 0x7fffffff; const DB PI = acos(-1.0); const DB EPS = 1e-6; const DB OO = 1e15; // <<= ` 0. Daily Use ., template<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;} template<class T> inline void checkMax(T &a,const T b){if (b>a) a=b;} template <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;} template <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;} template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);} template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);} template<class T> inline T sqr(T a){return a*a;} template<class T> inline T cub(T a){return a*a*a;} int Ceil(int x, int y){return (x - 1) / y + 1;} // <<= ` 1. Bitwise Operation ., inline bool _1(int x, int i){return x & 1<<i;} inline int _1(int i){return 1<<i;} inline int _U(int i){return _1(i) - 1;}; inline int count_bits(int x){ x = (x & 0x55555555) + ((x & 0xaaaaaaaa) >> 1); x = (x & 0x33333333) + ((x & 0xcccccccc) >> 2); x = (x & 0x0f0f0f0f) + ((x & 0xf0f0f0f0) >> 4); x = (x & 0x00ff00ff) + ((x & 0xff00ff00) >> 8); x = (x & 0x0000ffff) + ((x & 0xffff0000) >> 16); return x; } template<class T> inline T low_bit(T x) { return x & -x; } template<class T> inline T high_bit(T x) { T p = low_bit(x); while (p != x) x -= p, p = low_bit(x); return p; } // <<= ` 2. Modular Arithmetic Basic ., inline void INC(int &a, int b){a += b; if (a >= MOD) a -= MOD;} inline int sum(int a, int b){a += b; if (a >= MOD) a -= MOD; return a;} inline void DEC(int &a, int b){a -= b; if (a < 0) a += MOD;} inline int dff(int a, int b){a -= b; if (a < 0) a += MOD; return a;} inline void MUL(int &a, int b){a = a * b % MOD;} inline int pdt(int a, int b){return a * b % MOD;} inline int pow(int a, int b){ int c = 1; while (b) { if (b&1) MUL(c, a); MUL(a, a), b >>= 1; } return c; } inline int _I(int b){ int a = MOD, x1 = 0, x2 = 1, q; while (true){ q = a / b, a %= b; if (!a) return (x2 + MOD) % MOD; DEC(x1, pdt(q, x2)); q = b / a, b %= a; if (!b) return (x1 + MOD) % MOD; DEC(x2, pdt(q, x1)); } } inline void DIV(int &a, int b){MUL(a, _I(b));} inline int qtt(int a, int b){return pdt(a, _I(b));} // <<= ' 0. I/O Accelerator interface ., template<class T> inline void RD(T &x){ //cin >> x; //scanf("%d", &x); char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0'; //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0'; } //int ____Case; template<class T> inline void OT(const T &x){ //cout << x << endl; printf("%d\n", x); //printf("%.2lf\n", x); //printf("Case %d: %d\n", ++____Case, x); } #define For_each(it, A) for (SII::iterator it = A.begin(); it != A.end(); ++it) /* .................................................................................................................................. */ const int N = 9973, M = 1229, L = 1001; int P[M], F[M][N], F_[M][N]; int n, m; int h(int p){ return lower_bound(P, P + M, p) - P; } void init(){ bitset<N> C; FOR_1(i, 2, N){ if(!C[i]) P[m++] = i; REP_C(j, m){ if (i * P[j] >= N) break; C[i * P[j]] = true; } } /* REP(i, m){ F[i][0] = F[i][1] = F_[i][0] = F_[i][1] = 1; FOR_C(j, 2, MOD = P[i]){ F[i][j] = pdt(F[i][j-1], j); _F[i][j] = qtt(_F[i][j-1], j); } } */ REP(i, m){ F[i][0] = F[i][1] = F_[i][0] = F_[i][1] = 1; FOR_C(j, 2, MOD = P[i]){ F[i][j] = pdt(F[i][j-1], j); F_[i][j] = -MOD / j * F_[i][MOD % j] % MOD; if (F_[i][j] < 0) F_[i][j] += MOD; } } REP(i, m) FOR(j, 2, MOD = P[i]) MUL(F_[i][j], F_[i][j-1]); } int _c(int n, int m){ if (n < m) return 0; int p = h(MOD); return pdt(pdt(F[p][n], F_[p][m]), F_[p][n-m]); } int c(int n, int m){ int res = 1; while (n && m){ MUL(res, _c(n % MOD, m % MOD)); n /= MOD, m /= MOD; } return res; } int main(){ init(); while (cin >> n >> m >> MOD){ OT(c(n, m)); } }