[組合數取模] 方法匯總

[組合數取模] 方法匯總

1.利用整數唯一分解定理，求(n+1-m) * (n+m)! / ( m! * (n+1)! )

任何正整數都有且只有一種方法寫出其素因子冪相乘的形式。比如18= 2 * 3^2

A=(p1^k1)*(p2^k2)*(p3^k3)*(p4^k4)*......*(pn^kn) pi為素數

還有把階層看作一個數,比m! 怎樣求m!裡面素數2的指數呢？

cnt=0; while(m) { m/=2; cnt+=m; } 就可以了，為什麼呢？考慮m=4，則m!= 4*3*2*1, 第一次m/=2，是計算m!裡面有多少個數能整除2的（有4，2）,所以cnt+=2，有兩個數貢獻

了兩個素數2，接下來第二次m/=2，是計算m!裡面有多少個數能整除4的，有1個數又貢獻了一個素數2.

所以先預先篩出最大范圍內的素數，然後考慮每個素數就好了，關鍵是求出整個式子的該素數的指數是多少。

模板：

bool isprime[maxn*2+10];
int prime[maxn*2+10];
int len=0;//素數的個數
int n,m;
void sieve(int n)//篩n以內的素數
{
    for(int i=0;i<=n;i++)
        isprime[i]=1;
    isprime[0]=isprime[1]=0;
    for(int i=2;i<=n;i++)
        if(isprime[i])
        {
            prime[len++]=i;
            for(int j=2*i;j<=n;j+=i)
                isprime[j]=0;
        }
}
int cal(int p,int n)//計算n!裡面有多少個p相乘
{
    int ans=0;
    while(n)
    {
        n/=p;
        ans+=n;
    }
    return ans;
}

int main()
{
        sieve(maxn*2);
        long long ans=1;//記得要用long long
        cin>>n>>m;
        int nm=n+1-m;
        for(int i=0;i=mod)
                    ans%=mod;
            }
        }
        cout<