数论--组合数学相关

一：排列
1：不可重排列数:从n个数里取r个数的情况

2：可重复排列数:从n个数里取k个数的情况 （不放回）

3圆排列：从n个数中取m个数 使他们构成圆形的情况
(1<m<n)

4.不尽相异元素全排列：如果n个元素里，有p个元素相同，又有q的元素相同，......又有r个元素相同。且（p+q+...+r<=n），则它的所有排列种数为：

5.多重集的排列

二：组合
1：不可重组合数:从n个数里选r个的组合数

2：可重组合数：从n个数里选r个的组合数(放回)

3：不相邻组合：从1-n中选m个不相邻的组合

4:多重集的组合

三：模板：组合数取模(卢卡斯定律)

typedef long long LL;
const LL maxn(1000005), mod(1e9 + 7);
LL num[maxn];
void init()    //求maxn以内的数的阶乘
{
    num[0] = num[1] = 1;
    for(LL i = 2; i < maxn; i++)
        num[i] = num[i - 1] * i % mod;
}
/*
//拓展欧几里得算法求逆元
void exgcd(LL a, LL b, LL &x, LL &y)    //拓展欧几里得算法
{
    if(!b) x = 1, y = 0;
    else
    {
        exgcd(b, a % b, y, x);
        y -= x * (a / b);
    }
}
LL inv(LL a, LL b)   //求a对b取模的逆元
{
    LL x, y;
    exgcd(a, b, x, y);
    return (x + b) % b;
}
*/
//费马小定理求逆元
LL pow(LL a, LL n, LL p)    //快速幂 a^n % p
{
    LL ans = 1;
    while(n)
    {
        if(n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}
LL inv(LL a, LL b)   //费马小定理求逆元
{
    return pow(a, b - 2, b);
}
LL C(LL a, LL b)    //计算C(a, b)
{
    return num[a] * inv(num[b], mod) % mod * inv(num[a - b], mod) % mod;
}