已知数组a[]及其和sum, 求sum! / (a1!a2!...an!) 的个位数的值。
求某数的逆元表写成了求某数阶乘的逆元表，故一直没找到错误。
P 是质数的幂
B 表示质数,P 表示模数,cal(n) 将返回 n!,以 a × B^b 形式表示，a为模P的情况下。
ll n,x,y,P,B,s[];
ll exgcd(ll a,ll b){
if(!b)return x=,y=,a;
ll d=exgcd(b,a%b),t=x;
return x=y,y=t-a/b*y,d;
}
ll rev(ll a,ll P){exgcd(a,P);while(x<)x+=P;return x%P;}
ll pow(ll a,ll b,ll P){ll t=;for(;b;b>>=1LL,a=a*a%P)if(b&1LL)t=t*a%P;return t;}
struct Num{
ll a,b;
Num(ll a = , ll b = ): a(a), b(b){}
Num operator*(Num x){return Num(a*x.a%P, b+x.b);}
Num operator/(Num x){return Num(a*rev(x.a,P)%P, b-x.b);}
};
Num cal(ll n){return n? Num(s[n%P]*pow(s[P],n/P,P)%P,n/B)*cal(n/B): Num();}
void pre(){
for(int i = s[] = ; i < P; i++)
if(i%B) s[i]=s[i-]*i%P;
else s[i] = s[i-];
s[P] = s[P-];
}
int main(){
B = , P = , pre();
cal(n);
}
自己的题解如下：
#include <bits/stdc++.h> #define ll long long
#define ull unsigned long long
#define st first
#define nd second
#define pii pair<int, int>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tiii tuple<int, int, int>
#define pw(x) ((1LL)<<(x))
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sqr(x) ((x)*(x))
#define SIZE(A) ((int)(A.size()))
#define LENGTH(A) ((int)(A.length()))
#define FIN freopen("A.in","r",stdin);
#define FOUT freopen("A.out","w",stdout);
using namespace std;
/***********/
template<typename T>
bool scan (T &ret) {
char c;
int sgn;
if (c = getchar(), c == EOF) return ; //EOF
while (c != '-' && (c < '' || c > '') ) c = getchar();
sgn = (c == '-') ? - : ;
ret = (c == '-') ? : (c - '');
while (c = getchar(), c >= '' && c <= '') ret = ret * + (c - '');
ret *= sgn;
return ;
}
template<typename N,typename PN>inline N flo(N a,PN b){return a>=?a/b:-((-a-)/b)-;}
template<typename N,typename PN>inline N cei(N a,PN b){return a>?(a-)/b+:-(-a/b);}
template<typename T>inline int sgn(T a) {return a>?:(a<?-:);}
template<class T> int countbit(const T &n) { return (n==)?:(+countbit(n&(n-))); }
template <class T1, class T2>
bool gmax(T1 &a, const T2 &b) { return a < b? a = b, :;}
template <class T1, class T2>
bool gmin(T1 &a, const T2 &b) { return a > b? a = b, :;}
template <class T> inline T lowbit(T x) {return x&(-x);} template<class T1, class T2>
ostream& operator <<(ostream &out, pair<T1, T2> p) {
return out << "(" << p.st << ", " << p.nd << ")";
}
template<class A, class B, class C>
ostream& operator <<(ostream &out, tuple<A, B, C> t) {
return out << "(" << get<>(t) << ", " << get<>(t) << ", " << get<>(t) << ")";
}
template<class T>
ostream& operator <<(ostream &out, vector<T> vec) {
out << "("; for(auto &x: vec) out << x << ", "; return out << ")";
}
void testTle(int &a){
while() a = a*(ll)a%;
}
const ll inf = 0x3f3f3f3f;
const ll INF = 1e17;
const int mod = 1e9+;
const double eps = 1e-;
const int N = +;
const double pi = acos(-1.0); /***********/ int quick(int x, long long n, int mod) {
int ans = ;
while(n) {
if(n&) ans = ans*x%mod;
x = x*x%mod;
n >>= ;
}
return ans;
} long long get2(long long n) {
long long ans = ;
while(n >>= )
ans += n;
return ans;
} int m[] = {, , , , }; //阶乘%5
int inv[] = {, , , , }; //i的逆元，写成i!的逆元，狂WA
pair<long long, int> get5(long long n) {
if(n < ) return {, m[n]};
pair<long long, int> ret = get5(n/);
ret.st += n/;
ret.nd = ret.nd*quick(m[], n/, )*m[n%]%;
return ret;
} int main() {
int T; scanf("%d", &T);
long long a[];
while(T--) {
int n; scanf("%d", &n);
long long sum = ;
for(int i = ; i < n; i++)
scanf("%lld", a+i), sum += a[i];
long long mod2 = get2(sum);
auto mod5 = get5(sum);
for(int i = ; i < n; i++) {
mod2 -= get2(a[i]);
auto ret = get5(a[i]);
mod5.st -= ret.st;
mod5.nd = mod5.nd*inv[ret.nd]%;
}
int ans;
if(mod5.st) ans = mod2? : ;
else {
ans = mod5.nd;
if(mod2) {
if(ans&) ans = (ans+)%;
}
else {
if(!(ans&)) ans = (ans+)%;
}
}
printf("%d\n", ans);
}
return ;
}
附：
一句话阐明如何求阶乘的末尾非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
再合并一下~