Luogu2183 礼物 ExLucas、CRT

~~证明自己学过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;
}

巴特西

Luogu2183 礼物 ExLucas、CRT

最新文章

热门文章