HDU 5446 Unknown Treasure（lucas+中國(guó)剩余定理 / CRT）

2019-11-09 20:19:56

字體：大中小

供稿：網(wǎng)友

Lucas + CRT 模版題中間結(jié)果會(huì)爆long long Lucas: Cmnmodpk=ak $C_n^m /mod p_k=a_k$ CRT:Cmnmod(∏pk)=ans $C_n^m /mod (/<a >PR</a>od p_k)=ans$

#include <bits/stdc++.h>#define mem(a,b) memset(a,b,sizeof(a))#define rep(i,a,b) for(int i=a;i<b;i++)#define debug(a) printf("a =: %d/n",a);#define sc(x) scanf("%d",&x)const int INF=0x3f3f3f3f;const int maxn=1e5+50;const int Mod=1000000007;const double PI=acos(-1);typedef long long ll;typedef unsigned int ui;using namespace std;typedef long long ll;ll fac[maxn];ll qPow(ll x,ll n,ll mod){ ll ret=1; while(n){ if (n&1) ret=(ret*x)%mod; x=(x*x)%mod; n>>=1; } return ret; //x^n%mod}void initFac(int Mod){ //n! fac[0]=1; for(int i=1;i<=Mod;i++){ fac[i]=fac[i-1]*i%Mod; }}ll lucas(ll n,ll k,ll mod){ //C_n^k%mod if (n<0 || k<0 || k>n) return 0; ll ret=1; while(n && k){ ll np=n%mod,kp=k%mod; if (np<kp) return 0; ret=(ret*fac[np]%mod)*qPow(fac[kp]*fac[np-kp]%mod,mod-2,mod)%mod; n/=mod; k/=mod; } return ret;}ll extendEuclid(ll a, ll b, ll& x, ll& y) { if (b == 0) { x = 1; y = 0; return a; } ll d = extendEuclid(b, a % b, y, x); y -= x * (a / b); return d;}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;}ll CRT(ll a[],ll prime[],int n){ ll M = 1, d, y, x = 0; for (int i = 0; i < n; i++) M *= prime[i]; for (int i = 0; i < n; i++) { ll w = M / prime[i]; extendEuclid(prime[i], w, d, y); //x=x+(y*w%M)*a[i]%M; x = (x + mul(mul(y, w, M), a[i], M)); } return (x + M) % M;}ll a[15];ll p[15];int main(){#ifndef ONLINE_JUDGE //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout);#endif int T; scanf("%d",&T); while(T--){ ll n,m,k; scanf("%lld %lld %lld",&n,&m,&k); for(int i=0;i<k;i++){ scanf("%lld",&p[i]); initFac(p[i]); a[i]=lucas(n,m,p[i]); } printf("%lld/n",CRT(a,p,k)); } return 0;}

上一篇：vue項(xiàng)目導(dǎo)入外部css樣式和js文件

下一篇：leecode 解題總結(jié)：41. First Missing Positive