hdu5446——Unknown Treasure

题意：给定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));}}

总结

以上是生活随笔为你收集整理的hdu5446——Unknown Treasure的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。