已知数组a[]及其和sum, 求sum! / (a1!a2!...an!) 的个位数的值。
求某数的逆元表写成了求某数阶乘的逆元表，故一直没找到错误。
P 是质数的幂
B 表示质数,P 表示模数,cal(n) 将返回 n!,以 a × B^b 形式表示，a为模P的情况下。
1 ll n,x,y,P,B,s[2000000]; 2 ll exgcd(ll a,ll b){ 3 if(!b)return x=1,y=0,a; 4 ll d=exgcd(b,a%b),t=x; 5 return x=y,y=t-a/b*y,d; 6 } 7 ll rev(ll a,ll P){exgcd(a,P);while(x<0)x+=P;return x%P;} 8 ll pow(ll a,ll b,ll P){ll t=1;for(;b;b>>=1LL,a=a*a%P)if(b&1LL)t=t*a%P;return t;} 9 struct Num{ 10 ll a,b; 11 Num(ll a = 1, ll b = 0): a(a), b(b){} 12 Num operator*(Num x){return Num(a*x.a%P, b+x.b);} 13 Num operator/(Num x){return Num(a*rev(x.a,P)%P, b-x.b);} 14 }; 15 Num cal(ll n){return n? Num(s[n%P]*pow(s[P],n/P,P)%P,n/B)*cal(n/B): Num();} 16 void pre(){ 17 for(int i = s[0] = 1; i < P; i++) 18 if(i%B) s[i]=s[i-1]*i%P; 19 else s[i] = s[i-1]; 20 s[P] = s[P-1]; 21 } 22 int main(){ 23 B = 2, P = 512, pre(); 24 cal(n); 25 }
自己的题解如下：
1 #include <bits/stdc++.h> 2 3 #define ll long long 4 #define ull unsigned long long 5 #define st first 6 #define nd second 7 #define pii pair<int, int> 8 #define pil pair<int, ll> 9 #define pli pair<ll, int> 10 #define pll pair<ll, ll> 11 #define tiii tuple<int, int, int> 12 #define pw(x) ((1LL)<<(x)) 13 #define lson l, m, rt<<1 14 #define rson m+1, r, rt<<1|1 15 #define sqr(x) ((x)*(x)) 16 #define SIZE(A) ((int)(A.size())) 17 #define LENGTH(A) ((int)(A.length())) 18 #define FIN freopen("A.in","r",stdin); 19 #define FOUT freopen("A.out","w",stdout); 20 using namespace std; 21 /***********/ 22 template<typename T> 23 bool scan (T &ret) { 24 char c; 25 int sgn; 26 if (c = getchar(), c == EOF) return 0; //EOF 27 while (c != '-' && (c < '0' || c > '9') ) c = getchar(); 28 sgn = (c == '-') ? -1 : 1; 29 ret = (c == '-') ? 0 : (c - '0'); 30 while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0'); 31 ret *= sgn; 32 return 1; 33 } 34 template<typename N,typename PN>inline N flo(N a,PN b){return a>=0?a/b:-((-a-1)/b)-1;} 35 template<typename N,typename PN>inline N cei(N a,PN b){return a>0?(a-1)/b+1:-(-a/b);} 36 template<typename T>inline int sgn(T a) {return a>0?1:(a<0?-1:0);} 37 template<class T> int countbit(const T &n) { return (n==0)?0:(1+countbit(n&(n-1))); } 38 template <class T1, class T2> 39 bool gmax(T1 &a, const T2 &b) { return a < b? a = b, 1:0;} 40 template <class T1, class T2> 41 bool gmin(T1 &a, const T2 &b) { return a > b? a = b, 1:0;} 42 template <class T> inline T lowbit(T x) {return x&(-x);} 43 44 template<class T1, class T2> 45 ostream& operator <<(ostream &out, pair<T1, T2> p) { 46 return out << "(" << p.st << ", " << p.nd << ")"; 47 } 48 template<class A, class B, class C> 49 ostream& operator <<(ostream &out, tuple<A, B, C> t) { 50 return out << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ")"; 51 } 52 template<class T> 53 ostream& operator <<(ostream &out, vector<T> vec) { 54 out << "("; for(auto &x: vec) out << x << ", "; return out << ")"; 55 } 56 void testTle(int &a){ 57 while(1) a = a*(ll)a%1000000007; 58 } 59 const ll inf = 0x3f3f3f3f; 60 const ll INF = 1e17; 61 const int mod = 1e9+7; 62 const double eps = 1e-5; 63 const int N = 100000+10; 64 const double pi = acos(-1.0); 65 66 /***********/ 67 68 69 int quick(int x, long long n, int mod) { 70 int ans = 1; 71 while(n) { 72 if(n&1) ans = ans*x%mod; 73 x = x*x%mod; 74 n >>= 1; 75 } 76 return ans; 77 } 78 79 long long get2(long long n) { 80 long long ans = 0; 81 while(n >>= 1) 82 ans += n; 83 return ans; 84 } 85 86 int m[] = {1, 1, 2, 1, 4}; //阶乘%5 87 int inv[] = {1, 1, 3, 2, 4}; //i的逆元，写成i!的逆元，狂WA 88 pair<long long, int> get5(long long n) { 89 if(n < 5) return {0, m[n]}; 90 pair<long long, int> ret = get5(n/5); 91 ret.st += n/5; 92 ret.nd = ret.nd*quick(m[4], n/5, 5)*m[n%5]%5; 93 return ret; 94 } 95 96 97 98 int main() { 99 int T; scanf("%d", &T); 100 long long a[1000]; 101 while(T--) { 102 int n; scanf("%d", &n); 103 long long sum = 0; 104 for(int i = 0; i < n; i++) 105 scanf("%lld", a+i), sum += a[i]; 106 long long mod2 = get2(sum); 107 auto mod5 = get5(sum); 108 for(int i = 0; i < n; i++) { 109 mod2 -= get2(a[i]); 110 auto ret = get5(a[i]); 111 mod5.st -= ret.st; 112 mod5.nd = mod5.nd*inv[ret.nd]%5; 113 } 114 int ans; 115 if(mod5.st) ans = mod2? 0: 5; 116 else { 117 ans = mod5.nd; 118 if(mod2) { 119 if(ans&1) ans = (ans+5)%10; 120 } 121 else { 122 if(!(ans&1)) ans = (ans+5)%10; 123 } 124 } 125 printf("%d ", ans); 126 } 127 return 0; 128 }
附：
一句话阐明如何求阶乘的末尾非0数：
求末尾非0数模5的值，n = 5k时，
n! = (1*2*3*4) * (6*7*8*9) * ... * (5k-4)*(5k-3)*(5k-2)*(5k-1) *5^k * k!
= (1*2*3*4/2) * (6*7*8*9/2) * ... * [(5k-4)*(5k-3)*(5k-2)*(5k-1)/2] *10^k * k!
= (1*2*3*4/2) * (6*7*8*9/2) * ... * [(5k-4)*(5k-3)*(5k-2)*(5k-1)/2] * k! (去掉末尾的几个零，结果不变)
= (1*2*3*4/2) * (6*7*8*9/2) * ... * [(5k-4)*(5k-3)*(5k-2)*(5k-1)/2] *6^k * k! （乘6，模5下末尾不变）
= (1*2*3*4*3) * (6*7*8*9*3) * ... * [(5k-4)*(5k-3)*(5k-2)*(5k-1)*3] * k!
= 2^k * k!
阶乘末两位非0数？
P = 4, B = 2;
P = 25, B = 5
再合并一下~
