组合数数论小结 · 归纳篇

CuO同学 · 2019-11-05 12:07:22 · 个人记录

求组合数·水星

水利万物而不争

本体的数据范围是：

n和m都较小，mod也没有超出int范围

因此可以采取直接暴力递推的方式（杨辉三角公式递推）
需要注意的是，每次都要求取模，因此不能够记忆化

相反的，还需要每次重置，注意边界

#include <cstdio>
#include <algorithm>
#include <cmath>
#define lld long long 
//水利万物而不争
using namespace std;
const int maxn = 2003;
lld c[maxn][maxn];
int main(){

 c[0][0] = 1;

 int T;

 scanf("%d", &T);
 while(T--){
     int n, m, q;
     scanf("%d%d%d", &n, &m, &q);//不会暴int 
     for(int i = 1; i <= n; i++)
         for(int j = 0; j <= i; j++)
//              if(!c[i][j])
                 c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % q;
     printf("%lld\n", c[n][m]);
 }
 return 0;
}

求组合数·金星

锲而不舍，金石可镂

本题的数据范围是：

注意这个n已经很大了，但是m仍然比较小

因此可以采取储存m为下标的数组（本题要求以n为底，输出一系列数字）
依然采用了递推的方式，不是线性，但是相对于水有了倍增优化

本题具体分析请看这里：组合数小结（一）

#include <cmath>
#include <cstring> 

#define lld long long

using namespace std;
//在苍茫的大海上，狂风卷积着乌云
//在乌云和大海之间，有一只高傲的海燕 
const int maxn = 1003;

lld n, m;
lld f[maxn], g[maxn], q;
//f用来储存答案，g相当于暂时性存储
lld qmul(lld a, lld b) {

    a %= q;
    b %= q;
    lld ans = 0;
    while (b) {
        if (b & 1)
            ans = (ans + a) % q;
        a = (a + a) % q;
        b >>= 1;
    }
    return ans;
}
//留在这里的qmul只是为了提醒自己，never to 不判断条件就用快速乘
void cloud(lld n){

    if(n == 1)
        return;

    if(n % 2 == 0){
//n是偶数时，假设p等于n/2，然后卷积式求和        
        cloud(n >> 1);

        for(int i = 0; i <= m; i++){
            for(int j = 0; j <= i; j++)
                g[i] += f[j] % q * f[i - j] % q;
/*就是这里，用快速乘你就输了！！！！，正如陈老师所说 balabalabalala...*/
/*没错一定要注意这里，需要用数组储存而不是每次递归
（记忆化也不行，正如陈老师所说，对于一个要刷满的表，记忆化不如填表优）*/
//              g[i] = (g[i] + qmul(f[j], f[i - j])) ;// % q;
//              g[i] += qmul(f[j], f[i - j]);
            g[i] %= q;
        }

//              

        for(int i = 0; i <= m; i++)
            f[i] = g[i];//储存本次m的组合数

        memset(g, 0, sizeof g);//就是每次tmp数组的重置啦
    }else{

        cloud(n - 1);
//n为奇数时，先求出 n - 1 为总数的组合数
//然后利用杨辉三角基本转移方程写出下面的转移方程

        for(int i = 1; i <= m; i++)
            g[i] = (f[i - 1] % q + f[i] % q) % q;

        for(int i = 1; i <= m; i++)
            f[i] = g[i];//储存本次m的组合数

        memset(g, 0, sizeof g);//就是每次tmp数组的重置啦
    }
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){

        memset(f, 0, sizeof f);
        f[0] = 1;
        f[1] = 1;

        scanf("%lld %lld %lld", &n, &m, &q);
        cloud(n);
//注意只要进行一次递归操作（如果不想T死的话），而不是每次输出都进行递归
//虽然n很大，但是递归次数和m都是数组可存大小（尽量不要考虑map的奇葩用法）
//在这里不选择记忆化，因此储存每个f[m]

        for(int i = 0; i <= m; i++)
            printf("%lld ", f[i]);
        puts("");
    }
    return 0;
}

求组合数·地球

淼茫积水非吾土，飘泊浮萍是我身。

本体的数据范围是：

显然，这个n,m都不是数组可存下标范围，而且Q是质数（还是比较小的质数）
所以我们使用Lucas定理（注意要求取模的数为质数并且不是很大）
- 还记得吗？
- 卢卡斯说：
- C(n, m) % p = C(n / p, m / p) * C(n % p, m % p) % p
  
  对于C(n / p, m / p)，如果n / p 还是很大，可以递归下去，~~一直到世界的尽头~~

#include <cstdio>
#include <algorithm>
#include <cmath>
#define lld long long
using namespace std;
//天地玄黄，宇宙洪荒
// Lucas定理，大数难挡
lld qpow(lld a, lld b, lld mod) {//快速幂
    lld ans = 1;
    while (b) {
        if (b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
lld comp(lld a, lld b, lld mod) {//求C(b,a)
    if (a < b)
        return 0;
    if (a == b)
        return 1;
    if (b > a - b)//利用组合数性质进行的简单优化
        b = a - b;

    int ans = 1, ca = 1, cb = 1;
    //求出 n * (n-1) * ··· * (n-m+1)
    //求出 m * (m-1) * ··· * 1
    for (lld i = 0; i < b; i++) {//求出a_i,b_i的阶乘
        ca = (ca * (a - i)) % mod;
        cb = (cb * (b - i)) % mod;
    }

    //下面无需证明地给出这个公式(就是费马小定理（二）啦)
    ans = (ca * qpow(cb, mod - 2, mod)) % mod;
    return ans;
}
lld lucas(lld n, lld m, lld mod) {
//Lucas定理具体简单应用
    lld ans = 1;

    while (n && m && ans) {//持续进行同步进制转化（作为一名没有学过进制的蒟蒻，我是现场学的板子）
        ans = (ans * comp(n % mod, m % mod, mod)) % mod;
        n /= mod;
        m /= mod;
    }
    return ans;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        lld m, n, mod;
        scanf("%lld %lld %lld", &n, &m, &mod);
        printf("%lld\n", lucas(n, m, mod));
    }
    return 0;
}

Get 本人未涉及/不熟悉知识点：

1. 进制转化

    while (n && m && ans) {//持续进行同步进制转化（作为一名没有学过进制的蒟蒻，我是现场学的板子）
        ans = (ans * comp(n % mod, m % mod, mod)) % mod;
        n /= mod;
        m /= mod;
    }

2. 费马小定理求逆元

假如是一个整数，是一个质数，那么是p的倍数，可以表示为

如果a不是p的倍数，这个定理也可以写成（这个书写方式更加常用）

因此可以得出：b ^ p (mod p)关于 p 的逆元可以写为 b ^ (p-2) (mod p)

得到下式：

    ans = (ca * qpow(cb, mod - 2, mod)) % mod;

例题：上帝与集合的正确用法

求组合数·火星

绿蚁新醅酒，红泥小火炉。晚来天欲雪，能饮一杯无？

本题数据范围如下

可以看出，n比较大，m仍在数据储存范围内，Q变大了但是Q是质数而且没有特别大（我以为，质数就是在暗示我们写Lucas定理）

#include <cstdio>
#include <algorithm>
#include <cmath>
#define lld long long
using namespace std;
//天地玄黄，宇宙洪荒
// Lucas定理，大数难挡
lld qpow(lld a, lld b, lld mod) {
 lld ans = 1;
 while (b) {
     if (b & 1)
         ans = (ans * a) % mod;
     a = (a * a) % mod;
     b >>= 1;
 }
 return ans;
}
lld comp(lld a, lld b, lld mod) {
 if (a < b)
     return 0;
 if (a == b)
     return 1;
 if (b > a - b)
     b = a - b;

 int ans = 1, ca = 1, cb = 1;
 for (lld i = 0; i < b; i++) {
     ca = (ca * (a - i)) % mod;
     cb = (cb * (b - i)) % mod;
 }
 ans = (ca * qpow(cb, mod - 2, mod)) % mod;
 return ans;
}
lld lucas(lld n, lld m, lld mod) {
 lld ans = 1;

 while (n && m && ans) {
     ans = (ans * comp(n % mod, m % mod, mod)) % mod;
     n /= mod;
     m /= mod;
 }
 return ans;
}
int main() {
 int T;
 scanf("%d", &T);
 while (T--) {
     lld m, n, mod;
     scanf("%lld %lld %lld", &n, &m, &mod);
     printf("%lld\n", lucas(n, m, mod));
 }
 return 0;
}

陈老师说

“

 这个可以把A(n,m)给拓展一下，一直往后乘就行了

 这个考点是逆元呀

 地没法用逆元做吧

 地可以不用逆元，只用Lucas定理

 呃，不能这么说……应该说要用逆元，只是逆元可以暴力算，不用exgcd或是费马小定理

 大家会通用做法当然是姿雌的啦

 最后一题（土）就是大合成

                                ”

~~艹我还是不知道为什么可以暴力算逆元~~

求组合数·木星

沉舟侧畔千帆过，病树前头万木春。

本题数据范围如下：

n, m, q均不在可枚举范围，同时q不保证是质数，那么就可以加入中国剩余定理了(需要注意的是，q的每一个因子的幂次都保证不会太大)