做完整的网站设计需要的技术,怎么注册公司教程,微信公众号小程序搭建,免费的网站推广题意#xff1a;给定n和m#xff0c;求c(n,m)%(∏ p)的值#xff0c;相当于lucas定理的一个推广#xff0c;在p不是素数的情况下的一个解决方法。
思路#xff1a; 首先对于c(n,m)%p[i]来讲#xff0c;是一个lucas的裸题#xff0c;那么对于c(n,m)%(∏ p)划分成lucas子…题意给定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 bitsetusing namespace std;typedef long long ll;typedef unsigned long long ull;typedef long double ld;const int INF0x3fffffff;const int inf-INF;const int N1e55;const int M2005;const int mod1000000007;const double piacos(-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 is;in;i)#define frt(i,s,n) for (int is;in;i--)#define lson l,m,rt1#define rson m1,r,rt1|1#define lrt rt1#define rrt rt1|1#define middle int m(rl)1#define lowbit(x) (x-x)#define pii pairint,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 ans1;while (n){if (n1) ansans*a%m;aa*a%m;n1;}return ans%m;}//密封线ll f[N],inv[N];int init(int n){f[0]1;for (int i1;in;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[i1] * (i1) % n; }ll Lucas(ll n,ll m,ll p){ll ans1;while (nm){ll an%p,bm%p;if (ab) return 0;ansans*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(b1){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) {da;x1;y0;}else {ex_gcd(b,a%b,d,y,x);y-x*(a/b);}}ll China(int n,ll* a,ll* m){ll M1,d,x0,y;for (int i0;in;i) M*m[i];for (int i0;in;i){ll wM/m[i];ex_gcd(m[i],w,d,d,y);xxmul(mul(a[i],y,M),w,M);}return (xM)%M;}ll p[N],a[N];int main(){ll n,m;int Tread(),k;while (T--){scanf(%lld%lld%d,n,m,k);ft(i,0,k-1){scanf(%lld,pi);init(p[i]);a[i]Lucas(n,m,p[i]);//couta[i]endl;}printf(%lld\n,China(k,a,p));}}
