「BZOJ2142」 礼物/exLucas

发布于 29 天前  84 次阅读


题目链接
题目是让你求一堆 $1e9$ 范围的组合数并且模数不保证是质数。
对于这一类题目,我们有一种叫做 exlucas 的方法来算组合数(但是和 lucas 没有半毛钱关系)。
首先我们将模数 $m$ 质因数分解,最后用 CRT 合并一下就好了。
然后我们现在只需要考虑组合数对 $p^e$ 取模的情况了。
这样还是不能直接去乘逆元的,因为分母可能有因子 $p$,直接求逆元会变成 $0$ 直接自闭。所以我们考虑提取组合数计算公式 $\frac{n!}{m!(n-m)!}$ 中所有的质因子 $p$单独计算。现在我们只需要快速计算出 $a! \mod p^e$ 除掉所有的因子 $p$ 的结果就可以了。
(更广义的说,我们需要计算 $a! \mod p^e$,分开处理 $p$ 和其他数对答案的贡献)
于是我们考虑对于目前处理到 $a! \mod p^e$ 这个问题如何处理:
1. 我们需要找出 $[1,n]$ 中所有是 $p$ 倍数的数,统一提出一个 $p$ ,然后划分为子问题 $(\frac{n}{p})!$ 继续计算
2. 对于非 $p$ 倍数的数,肯定存在连续的 $[1,p^e-1]$ 段,我们只需要统计出一段,然后用快速幂算一下贡献就可以了(因为在模意义下各段答案相同)。
3. 对于一些边角的小东西 暴力算一算就可以了。

时间复杂度由于我 太菜,不会分析。
所以代码大概是这样:

/*
 * Author: RainAir
 * Time: 2019-07-21 19:54:36
 */
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 1000+5;
int a[MAXN],n,m,mod;

inline int qpow(int a,int n,int ha){
    int res = 1ll;
    while(n){
        if(n & 1) res = 1ll*res*a%ha;
        a = 1ll*a*a%ha;
        n >>= 1;
    }
    return res;
}

inline void exgcd(int a,int b,int &x,int &y){
    if(!b){
        x = 1;y = 0;
        return;
    }
    exgcd(b,a%b,x,y);
    int t = x;x = y;y = t-(a/b)*y;
}

inline int inv(int a,int p){
 //   assert(p != 0);
    int x = 0,y = 0;
    exgcd(a,p,x,y);
    x = (x%p+p)%p;
   // assert(x != 0);
    return x;
}

inline int fac(int n,int p,int pk){
    int ans = 1ll;
    if(!n) return 1;
    FOR(i,1,pk){
        if(i%p) ans = 1ll*ans*i%pk;
    }
    ans = qpow(ans,n/pk,pk);
    FOR(i,1,n%pk){
        if(i % p) ans = 1ll*ans*i%pk;
    }
    return 1ll*ans*fac(n/p,p,pk)%pk;
}

inline int C(int n,int m,int mod,int p,int pk){
    if(n < m) return 0;
    int ans = 1ll;
    int a = fac(n,p,pk),b = fac(m,p,pk),c = fac(n-m,p,pk);
    int k = 0;
    for(int i = n;i;i /= p) k += i/p;
    for(int i = m;i;i /= p) k -= i/p;
    for(int i = n-m;i;i /= p) k -= i/p;
    ans = 1ll*a*inv(b,pk)%pk*inv(c,pk)%pk*qpow(p,k,pk)%pk;
    return 1ll*ans*(mod/pk)%mod*inv(mod/pk,pk)%mod;
}

LL ans = 1ll;

signed main(){
    scanf("%lld%lld%lld",&mod,&n,&m);int sm = 0;
    FOR(i,1,m) scanf("%lld",a+i),sm += a[i];
    if(sm > n){
        puts("Impossible");
        return 0;
    }
    int q = std::sqrt(1.0*mod);
    FOR(i,1,m){
        int x = mod,res = 0;
        FOR(k,2,q){
            if(!(x%k)){
                int pk = 1;
                while(!(x%k)) x /= k,pk *= k;
                res = (res+C(n,a[i],mod,k,pk))%mod;
            }
        }
        if(x > 1) res = (res+C(n,a[i],mod,x,x))%mod;
        ans = 1ll*ans*res%mod;
        n -= a[i];
    }
    printf("%lld\n",ans);
    return 0;
}


一个OIer。