证明自己学过exLucas
这题计算的是本质不相同的排列数量,不难得到答案是\(\frac{n!}{\prod\limits_{i=1}^m w_i! \times (n - \sum\limits_{i=1}^m w_i)!}\)
但是模数不一定是质数,于是用exLucas计算即可。
#include<bits/stdc++.h>
#define int long long
//This code is written by Itst
using namespace std;
int peo[7] , ans[10][2];
int cnt , N , M , P;
inline int poww(int a , int b , int mod = 1e15){
int times = 1;
while(b){
if(b & 1)
times = times * a % mod;
a = a * a % mod;
b >>= 1;
}
return times;
}
void exgcd(int a , int b , int &x , int &y){
!b ? (x = 1 , y = 0) : (exgcd(b , a % b , y , x) , y -= a / b * x);
}
inline int inv(int a , int b){
a %= b;
int x , y;
exgcd(a , b , x , y);
return (x + b) % b;
}
int jc(int N , int p , int mod){
if(!N)
return 1;
int times = 1;
for(int j = 1 ; j < mod ; ++j)
if(j % p)
times = times * j % mod;
times = poww(times , N / mod , mod);
for(int j = N / mod * mod + 1 ; j <= N ; ++j)
if(j % p)
times = times * j % mod;
return times * jc(N / p , p , mod) % mod;
}
int cntp(int N , int p){
int sum = 0;
while(N >= p)
sum += (N /= p);
return sum;
}
void calc(int p , int k){
int mod = poww(p , k) , c = cntp(N , p);
for(int j = 1 ; j <= M ; ++j)
c -= cntp(peo[j] , p);
ans[++cnt][0] = mod;
if(c < k){
ans[cnt][1] = poww(p , c) * jc(N , p , mod) % mod;
for(int j = 1 ; j <= M ; ++j)
ans[cnt][1] = ans[cnt][1] * inv(jc(peo[j] , p , mod) , mod) % mod;
}
}
signed main(){
#ifndef ONLINE_JUDGE
//freopen("in" , "r" , stdin);
//freopen("out" , "w" , stdout);
#endif
cin >> P >> N >> M;
for(int i = 1 ; i <= M ; ++i){
cin >> peo[i];
peo[M + 1] += peo[i];
}
if(peo[M + 1] > N){
puts("Impossible");
return 0;
}
peo[M + 1] = N - peo[M + 1];
++M;
int tmp = P;
for(int i = 2 ; i * i <= tmp ; ++i)
if(tmp % i == 0){
int cnt = 0;
while(tmp % i == 0){
++cnt;
tmp /= i;
}
calc(i , cnt);
}
if(tmp - 1)
calc(tmp , 1);
int sum = 0;
for(int i = 1 ; i <= cnt ; ++i)
sum = (sum + ans[i][1] * (P / ans[i][0]) % P * inv(P / ans[i][0] , ans[i][0])) % P;
cout << sum;
return 0;
}