排列组合 get ！

· · 个人记录

组合数

1.公式 ：C^m_n = \dfrac{m!}{n! (m-n)!}

2.递推式：C^m_n = C^{m-1}_{n-1} + C^{m-1}_n

3.性质：C^m_n = C^{n-m}_n

和一些其他性质:

证明：

传送门

这其实就是一个简单的快速幂，

但是证明了组合数的一个性质

即：

由于这个需要二项式定理证明，在下太蒟就不证了。

但是可以这样想，对于每一个数，只有取或不取两种状态，所以 n个数的方案数为 2^n ，但是由于是偶数（或奇数），所以要除 2

代码就不放了，就是一个快速幂。

排列：

1.公式：A^m_n = \dfrac{m!}{(m-n)!}

2.与组合数转化：A^m_n = n! \times C^m_n

t1:

传送门

这道题 需要的是逆向思维，

求相邻罪犯状态相同的方案数，可以先求出总方案数，再减去状态不同的方案数，

总方案数显然是 m ^ n

相邻罪犯状态不相同的方案数可能需要想一下，

对于第一个罪犯，选择的方案数是 n ，

对于后面的罪犯，为了与前面的不相同，选择的方案数是 n - 1

所以，答案就是 m ^ n - m * ( m - 1 ) ^ ( n - 1 )

int main(void)
{
    cin >> m >> n;
    LL tot = FastPow(m,n)%p;
    LL els = m*FastPow(m-1,n-1)%p;
    LL ans = tot-els;
    cout << (ans+p)%p;
    return 0;
}

t2:

传送门

与上一题挺像的，也是先求出所有组合，再减去不合法的情况

不合法的情况即是没有任何一块长为 k 的区间颜色相同

int main(void)
{
    cin >> n >> m >> k;
    f[0] = 1;
    LL tot = FastPow(m,n)%p;
    for(int i=1;i<=n;i++)
    {
        if(i < k)
        {
            f[i] = f[i-1]*m%p;
            sum  = (sum+f[i])%p;
        }
        else
        {
            f[i] = sum*(m-1)%p;
            sum = (sum+f[i]-f[i-k+1])%p;
        }
    }
    LL ans = tot - f[n];
    cout << (ans+p)%p;
    return 0;
}