关于acm中常见的计算组合数的方法总结

1. 最简单的情况，数据比较小，直接采用C(a, b) = a * (a - 1) *....* (a - b + 1) / (b * (b - 1) *...* 2 * 1)
   试用数据范围：a <= 29。在a = 30, b = 15时，计算分子乘机时即超范围
   

   LL C(LL a, LL b)
   {
       if (a < b) return 0;
       LL ret = 1;
       FE(i, a - b + 1, a)
           ret *= i;
       FE(i, 2, b)
           ret /= i;
       return ret;
   }

2. 也适用比较简单的情况，数据比较小，采用C(a, b) = a! / (b! * (a - b)!)
   由于分子比第一种方法更大，所以适用范围更小，为a <= 20
   

   LL fx[MAXN];
   
   void init()
   {
       fx[0] = 1;
       FF(i, 1, MAXN)
           fx[i] = fx[i - 1] * i;
   }
   
   LL C(LL a, LL b)
   {
       if (a < b) return 0;
       return fx[a] / fx[b] / fx[a - b];
   }

3. 预处理出需要的组合数，如需计算较大的组合数可采用（经常会取模，也很方便）。使用C(a, b) = C(a - 1, b - 1) + C(a - 1, b - 1)递推处理
   因为计算过程中采用递推的加法运算，所以不取模的时候最大可以算到a = 66
   但是，这种情况一般伴随着取模的操作，所以考虑到内存限制的时候，一般可以计算到a = 1000（不一定，受限于内存）
   

   LL f[MAXN1][MAXN2];
   
   void init()
   {
       FF(i, 0, MAXN1)
           f[i][0] = 1;
       FF(i, 1, MAXN1)
       {
           FE(j, 1, min(i, MAXN2 - 1))
               f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % MOD;
       }
   }

4. 采用分解质因子的方式，可以计算足够大的数（因为数字会超过long long的范围，所以结果依然用质因子表示，模板中计算出了相应的数）
   

   map <int, LL> m;
   
   //分解质因数
   //k为1或-1
   void fun(int n, int k)
   {
       for (int i = 2; i <= sqrt(n * 1.0); i++)
       {
           while (n % i == 0)
           {
               n /= i;
               m[i] += k;
           }
       }
       if (n > 1)
       {
           m[n] += k;
       }
   }
   
   //大数快速幂取模
   LL quick_pow(LL a, LL b)
   {
       LL ret = 1;
       while (b)
       {
           if (b & 1)
           {
               ret *= a;
               ret %= MOD;
           }
           b >>= 1;
           a *= a;
           a %= MOD;
       }
       return ret;
   }
   
   //求组合数
   LL C(LL a, LL b)
   {
       if (a < b || a < 0 || b < 0)
           return 0;
       m.clear();
       LL ret = 1;
       b = min(a - b, b);
       for (int i = 0; i < b; i++)
       {
           fun(a - i, 1);
       }
       for (int i = b; i >= 1; i--)
       {
           fun(i, -1);
       }
   
       ///以下计算出了具体的数
       for (__typeof(m.begin()) it = m.begin(); it != m.end(); it++)
       {
           if ((*it).second != 0)
           {
               ret *= quick_pow((*it).first, (*it).second);
               ret %= MOD;
           }
       }
       return ret;
   }

   
   
   

关于acm中常见的计算组合数的方法总结,布布扣,bubuko.com

关于acm中常见的计算组合数的方法总结

原文：http://blog.csdn.net/wty__/article/details/20048467