当前位置: 代码迷 >> 综合 >> 预处理(组合数) 重数
  详细解决方案

预处理(组合数) 重数

热度:56   发布时间:2024-01-15 07:53:08.0

组合数预处理:

问题:求解组合数C(n,m),即从n个相同物品中取出m个的方案数,由于结果可能非常大,对结果模10007即可。

方案1: 暴力求解,C(n,m)=n*(n-1)…(n-m+1)/m!,n<=15 
方案2: 打表,C(n,m)=C(n-1,m-1)+C(n-1,m),n<=1,000 
方案3: 质因数分解,C(n,m)=n!/(m!*(n-m)!),C(n,m)=p1a1-b1-c1p2a2-b2-c2…pkak-bk-ck,n<=10,000,000 

方案4:C(n,m) = (n - m + 1) * C(n, m - 1) / m

          两个实现,打表或直接算

方案5:大数
方案6: Lucas定理,将m,n化为p进制,有:C(n,m)=C(n0,m0)*C(n1,m1)…(mod p),算一个不是很大的C(n,m)%p,p为素数,n在int范围内,修改一下可以满足long long范围内。具体点这里

方案7:阶乘逆元+%1e9+7

方法八 、递推O(1)就能求出每一个的逆元

 

方案一适用范围小,不说了。

方案2

//M可以不是素数,单个求还比较快

const int M = 10007;
const int MAXN = 1000;
int C[MAXN+1][MAXN+1];
void Initial()
{int i,j;for(i=0; i<=MAXN; ++i){C[0][i] = 0;C[i][0] = 1;}for(i=1; i<=MAXN; ++i){for(j=1; j<=MAXN; ++j)C[i][j] = (C[i-1][j] + C[i-1][j-1]) % M;}
}int Combination(int n, int m)
{return C[n][m];
}

方案3:

//用筛法生成素数
const int MAXN = 2e+6;
bool arr[MAXN+1] = {false};
ll M; ///对M取模
vector<ll> produce_prim_number()
{vector<ll> prim;prim.push_back(2);int i,j;for(i=3; i*i<=MAXN; i+=2){if(!arr[i]){prim.push_back(i);for(j=i*i; j<=MAXN; j+=i)arr[j] = true;}}while(i<=MAXN){if(!arr[i])prim.push_back(i);i+=2;}return prim;
}//计算n!中素因子p的指数
ll Cal(ll x, ll p)
{ll ans = 0;long long rec = p;while(x>=rec){ans += x/rec;rec *= p;}return ans;
}//计算n的k次方对M取模,二分法
ll Pow(long long n, ll k, ll M)
{long long ans = 1;while(k){if(k&1){ans = (ans * n) % M;}n = (n * n) % M;k >>= 1;}return ans;
}//计算C(n,m)
ll C(ll n,ll m)
{vector<ll> prim = produce_prim_number();long long ans = 1;ll num;for(int i=0; i<prim.size() && prim[i]<=n; ++i){num = Cal(n, prim[i]) - Cal(m, prim[i]) - Cal(n-m, prim[i]);ans = (ans * Pow(prim[i], num, M)) % M;}return ans;
}

方案4:

typedef long long ll;
ll a[100000000];int C(ll n,ll m)
{if (n - m < m)m = n - m;a[0] = 1;for (int i = 1; i <= m; i++) {a[i] = (n - i + 1) * a[i - 1] / i;}return a[m];
}

 

ll C(ll n,ll m)
{ll x = 1;if (n - m < m)m = n - m;if(m==0) return x;for (int i = 1; i <= m; i++) {x = (n - i + 1) * x / i;}return x;
}

方案5:大数

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define MAX 100
#define BASE 10000
void multiply(int a[],int Max,int b)
{//大数乘法 int i,array=0;for(i=Max-1;i>=0;i--){array += b*a[i];a[i] = array%BASE;array /= BASE;		}
}void divide(int a[],int Max,int b)
{//大数除法 int i,div=0;for(i=0;i<Max;i++){div =div * BASE + a[i];a[i] = div/b;div%=b;	}
}int main()
{int i,j,n;int a[105][MAX];memset(a[1],0,sizeof(a[1]));for(i=2,a[1][MAX-1]=1;i<=100;i++){memcpy(a[i],a[i-1],sizeof(a[i-1]));multiply(a[i],MAX,4*i-2);divide(a[i],MAX,i+1);}while(cin>>n,n!=-1){for(i=0;i<MAX && a[n][i]==0;i++);cout<<a[n][i++];for(;i<MAX;i++)printf("%04d",a[n][i]);cout<<endl;}return 0;
}

方案6: 点这里

 

求质数p在n!的重数:

ll cal(ll n,ll p)
{ll num=0;while (n){num += n/p;n=n/ p;}return num;
}

方案7:阶乘逆元+%1e9+7

LL fac[N],finv[N],inv[N];void make()
{fac[0]=fac[1]=1;finv[0]=finv[1]=1;inv[1]=1;for(int i=2;i<100010;i++){inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;fac[i]=fac[i-1]* i%MOD;finv[i]=finv[i-1]*inv[i]%MOD;}
}
LL C(int x,int y)
{if(x<y) return 0;return fac[x]*(finv[y]*finv[x-y]%MOD)%MOD;
}

 

方法八 、递推O(1)就能求出每一个的逆元

//预处理逆元 i (i<N)关于MOD的逆元
void getinv()
{inv[0]=inv[1]=1;for(int i=2; i<N; i++)inv[i]=((-MOD/i*inv[MOD%i])%MOD+MOD)%MOD;
}
//计算C(n,m)
LL slove(int n,int m)
{LL ans=1;for(int i=1; i<=m; i++)ans=((ans*inv[i])%MOD*(n-i+1))%MOD;return ans;
}

 

  相关解决方案