C(m,n)%P

时间：2023-03-09 02:27:37
C(m,n)%P

program1 n!%P(P为质数)

我们发现n! mod P的计算过程是以P为周期的的，举例如下：
n = 10, P = 3
n! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10
    = 1 * 2 *
       4 * 5 *
       7 * 8 *
      10 *
      3 * 6 * 9
   = (1 * 2)^3 *
      1*
      3^3 * (1 * 2 * 3)
最后一步中的1 * 2 *3可递归处理。
因为P的倍数与P不互质，所以P的倍数不能直接乘入答案，应当用一个计数器变量g来保存答案中因子P的个数。
我们提前预处理出fac[i] = 1 * 2 * 3 * … * (i – 1) * i mod P，函数calcfac(n)返回n! mod P的值，power(a, b, c)返回ab mod c的值，注意，calcfac(n)算出来的值不包含因子P，我们另外把因子P的个数另外存在g中。
代码如下：
typedef long long LL;
LL calcfac(LL n)
{
if (n < P) return fac[n];
LL s = n / P, t = n % P;
LL res = power(fac[P - 1], s, P); //fac[P - 1]重复出现了s次
res = res * fac[t] % P; //除去s次fac[P – 1]外，剩下的零头
g += n / P; //提出n / P个因子P
res = res* calcfac(n / P) % P; //递归处理
return res;
}
program2 C(m,n)%P(P为质数)
运用program1，算出m!%P，n!%P和(m-n)!%P，已知这三者的答案中因子P的个数为g1,g2,g3。
我们可以得到：
C(m,n)%P

我们不假思索地认为g1-g2-g3>=0（否则C(m,n)算出来就是分数了），而且容易知道calcfac(n)*falcfac(m-n)与P互质（我们除去了P因子）所以可以变成：

C(m,n)%P

这样就可以直接算了。

program3 C(m,n)%P(P不一定为质数)
基本思路与program2相同。
对P进行质因数分解，得到P = p1c1 * p2c2 * … * ptct。
对于每个1≤i≤t，以pici为模运行program2，最后用中国剩余定理合并。这里pici不一定为质数，不过只需对原算法稍加修改即可。令modi = pici，fac[i] = 除去pi的倍数外i的阶乘。例如pi = 3,ci = 2，那么fac[10] = 1 * 2 * 4 * 5 * 7 * 8 * 10，除去了3的倍数3、6和9。阶乘依然是以modi为周期的，calcfac(n)与program2主体相同，只是统计因子个数时，应使用ret += n / pi而不是ret += n / modi，递归处理时也应该是calcfac(n / pi)而不是calcfac(n / modi)。
当然，这个算法也有些局限，因为要求fac数组，所以pici要比较小，如果P是一个大质数就不行了。
#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<fstream>

#include<algorithm>

#include<cstring>

#include<string>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<utility>

#include<set>

#include<bitset>

#include<vector>

#include<functional>

using namespace std;

typedef long long LL;

typedef double DB;

typedef pair<int,int> PII;

#define mmst(a,v) memset(a,v,sizeof(a))

#define mmcy(a,b) memcpy(a,b,sizeof(a))

#define re(i,a,b) for(i=a;i<=b;i++)

#define red(i,a,b) for(i=a;i>=b;i--)

#define fi first

#define se second

template<class T>inline T sqr(T x){return x*x;}

template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}

template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;}

const DB EPS=1e-;

inline int dblcmp(DB x){if(abs(x)<EPS)return ;return(x>)?:-;}

inline void SetOpen(string s)

{

freopen((s+".in").c_str(),"r",stdin);

freopen((s+".out").c_str(),"w",stdout);

}

inline int Getin_Int()

{

int res=,flag=;char z;

for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());

if(z==EOF)return ;

if(z=='-'){flag=-flag;z=getchar();}

for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());

return res*flag;

}

inline LL Getin_LL()

{

LL res=,flag=;char z;

for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar());

if(z==EOF)return ;

if(z=='-'){flag=-flag;z=getchar();}

for(;z!=EOF && isdigit(z);res=res*+z-'',z=getchar());

return res*flag;

}

const LL maxpici=;

const LL maxcnt=;

LL n,m,P;

LL cnt,p[maxcnt+],c[maxcnt+],mod[maxcnt+],euler[maxcnt+],fac[maxcnt+][maxpici+];

LL ans;

inline LL power(LL a,LL b,LL Mod)

{

LL x=,y=a;

while(b!=){if(b&)x=x*y%Mod;if(b==)break;y=y*y%Mod;b/=;}

return x;

}

inline LL calfac(LL N,LL id,LL &g)

{

if(N<p[id])return fac[id][N];

LL s=N/mod[id],t=N%mod[id],res=;

res=res*power(fac[id][mod[id]-],s,mod[id])%mod[id];

res=res*fac[id][t]%mod[id];

g+=N/p[id];

res=res*calfac(N/p[id],id,g)%mod[id];

return res;

}

inline LL solve(LL id)

{

LL g1=,g2=,g3=;

LL fenzi=calfac(m,id,g1),fenmo=calfac(n,id,g2)*calfac(m-n,id,g3)%mod[id];

return fenzi*power(fenmo,euler[id]-,mod[id])%mod[id]*power(p[id],g1-g2-g3,mod[id])%mod[id];

}

inline void extend_gcd(LL a,LL &x,LL b,LL &y)

{

if(b==){x=;y=;return;}

LL dx,dy;

extend_gcd(b,dx,a%b,dy);

x=dy;

y=dx-a/b*dy;

}

int main()

{

SetOpen("program");

LL i,j,temp;

m=Getin_Int();n=Getin_Int();P=Getin_Int();

if(m<n){puts("0\n");return ;}

temp=P;

re(i,,maxpici)if(temp%i==)

{

++cnt;

p[cnt]=i;

mod[cnt]=;

while(temp%i==){c[cnt]++;mod[cnt]*=i;temp/=i;}

euler[cnt]=mod[cnt]/p[cnt]*(p[cnt]-);

fac[cnt][]=;

re(j,,mod[cnt]-)fac[cnt][j]=(j%p[cnt]==)?fac[cnt][j-]:fac[cnt][j-]*j%mod[cnt];

}

ans=;

re(i,,cnt)

{

temp=solve(i);

LL a=P/mod[i],x,b=mod[i],y;

extend_gcd(a,x,b,y);

ans=(ans+temp*a%P*x%P)%P;

}

ans=(ans%P+P)%P;

cout<<ans<<endl;

return ;

}
 来自：

随机推荐

  1. fuel部署openStack

    https://code.launchpad.net/fuel [fuel项目] http://www.imgburn.com/ [各种镜像制作工具]

  2. LeetCode - 204. Count Primes - 埃拉托斯特尼筛法 95.12% - (C++) - Sieve of Eratosthenes

    原题 原题链接 Description: Count the number of prime numbers less than a non-negative number, n. 计算小于非负数n的 ...

  3. apache shiro内置过滤器 标签 注解

    内置过滤器 anon(匿名)  org.apache.shiro.web.filter.authc.AnonymousFilter authc(身份验证)       org.apache.shiro ...

  4. css浮动+应用（瀑布流效果的实现）

    首先是index.html文件: <!DOCTYPE html> <html> <head> <meta charset="UTF-8"& ...

  5. synchronized 与 Lock 的那点事

    最近在做一个监控系统,该系统主要包括对数据实时分析和存储两个部分,由于并发量比较高,所以不可避免的使用到了一些并发的知识.为了实现这些要求,后台使用一个队列作为缓存,对于请求只管往缓存里写数据.同时启 ...

  6. 单源最短路径（dijkstra算法）php实现

    做一个医学项目,当中在病例评分时会用到单源最短路径的算法.单源最短路径的dijkstra算法的思路例如以下: 如果存在一条从i到j的最短路径(Vi.....Vk,Vj),Vk是Vj前面的一顶点.那么( ...

  7. （3）选择元素——（9）为交替的列加样式（Styling alternate rows）

    Two very useful custom selectors in the jQuery library are :oddand :even. Let's take a look at how w ...

  8. Linux如何创建一个新进程

    2016-03-31 张超<Linux内核分析>MOOC课程http://mooc.study.163.com/course/USTC-1000029000 Linux如何创建一个新进程 ...

  9. Webstorm10.0.3破解程序及汉化包下载、Webstorm配置入门指南

    核心提示: WebStorm 是jetbrains公司旗下一款JavaScript 开发工具.被广大中国JS开发者誉为“Web前端开发神器”.“最强大的HTML5编辑器”.“最智能的JavaSscri ...

  10. html.css溢出

    <!DOCTYPE html><!DOCTYPE html><html><head> <title></title> <m ...

相关文章