hdu5446——Unknown Treasure

淡淡的烟草味﹌ 2022-07-18 21:26 154阅读 0赞

#### 题意：给定n和m，求c(n,m)%(∏ p)的值，相当于lucas定理的一个推广，在p不是素数的情况下的一个解决方法。 ####

#### 思路： 首先对于c(n,m)%p\[i\]来讲，是一个lucas的裸题，那么对于c(n,m)%(∏ p)划分成lucas子问题求解后就变成了M%p\[i\]==a\[i\]的问题，这个问题就是裸的中国剩余定理了。 ####

#### code： ####

#include <iostream>
        #include <cstdio>
        #include <cmath>
        #include <algorithm>
        #include <cstring>
        #include <sstream>
        #include <string>
        #include <vector>
        #include <list>
        #include <queue>
        #include <stack>
        #include <map>
        #include <set>
        #include <bitset>
    
        using namespace std;
    
        typedef long long ll;
        typedef unsigned long long ull;
        typedef long double ld;
    
        const int INF=0x3fffffff;
        const int inf=-INF;
        const int N=1e5+5;
        const int M=2005;
        const int mod=1000000007;
        const double pi=acos(-1.0);
    
        #define cls(x,c) memset(x,c,sizeof(x))
        #define cpy(x,a) memcpy(x,a,sizeof(a))
        #define ft(i,s,n) for (int i=s;i<=n;i++)
        #define frt(i,s,n) for (int i=s;i>=n;i--)
        #define lson l,m,rt<<1
        #define rson m+1,r,rt<<1|1
        #define lrt rt<<1
        #define rrt rt<<1|1
        #define middle int m=(r+l)>>1
        #define lowbit(x) (x&-x)
        #define pii pair<int,int>
        #define mk make_pair
        #define IN freopen("in.txt","r",stdin)
        #define OUT freopen("out.txt","w",stdout)
    
        int read() {
        char ch;
        while (ch = getchar(), !isdigit(ch));
        int res = ch - '0';
        while (ch = getchar(), isdigit(ch))
        res = res * 10 + ch - '0';
        return res;
        }
        ll powm(ll a,ll n,ll m){
        ll ans=1;
        while (n){
        if (n&1) ans=ans*a%m;
        a=a*a%m;
        n>>=1;
        }
        return ans%m;
        }
        //++++++++++++密++++++++++++++封++++++++++++++++++++线
        ll f[N],inv[N];
        int init(int n){
            f[0]=1;
            for (int i=1;i<n;i++) f[i]=f[i-1]*i%n;
            inv[n-1] = powm(f[n-1], n-2, n);  
        for (int i = n - 2; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % n;  
        }
        ll Lucas(ll n,ll m,ll p){
            ll ans=1;
            while (n&&m){
                ll a=n%p,b=m%p;
                if (a<b) return 0;
                ans=ans*f[a]%p*inv[b]%p*inv[a-b]%p;
                n/=p;m/=p;
            }
    
            return ans%p;
        }
        ll mul(ll a, ll b, ll mod) {
            a = (a % mod + mod) % mod;
            b = (b % mod + mod) % mod;
            ll ret = 0;
            while(b){
                if(b&1){
                    ret += a;
                    if(ret >= mod) ret -= mod;
                }
                b >>= 1;
                a <<= 1;
                if(a >= mod) a -= mod;
            }
            return ret;
        }
        void ex_gcd(ll a,ll b,ll d,ll& x,ll& y){
            if (!b) {d=a;x=1;y=0;}
            else {ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}
        }
        ll China(int n,ll* a,ll* m)
        {
            ll M=1,d,x=0,y;
            for (int i=0;i<n;i++) M*=m[i];
            for (int i=0;i<n;i++){
                ll w=M/m[i];
                ex_gcd(m[i],w,d,d,y);
                x=x+mul(mul(a[i],y,M),w,M);
            }
            return (x+M)%M;
        }
        ll p[N],a[N];
        int main()
        {
            ll n,m;
            int T=read(),k;
            while (T--){
                scanf("%lld%lld%d",&n,&m,&k);
                ft(i,0,k-1){
                    scanf("%lld",p+i);
                    init(p[i]);
                    a[i]=Lucas(n,m,p[i]);
                    //cout<<a[i]<<endl;
                }
                printf("%lld\n",China(k,a,p));
            }
        }