精华内容
下载资源
问答
  • 一些常见组合数

    千次阅读 2015-11-01 16:13:07
    上面的排列,不考虑其顺序。也就是说,这k个循环排列之间互相交换顺序,还是算一种。而且每个循环排列是按特定顺序的...n个不同的物品划分成k个非空的不可区分的集合的数目是 第二类stiring

    上面的排列,不考虑其顺序。也就是说,这k个循环排列之间互相交换顺序,还是算一种。而且每个循环排列是按特定顺序的,即{A D C}与{A C D}是不同的,即有向环,按特定方向。



    这里n个物品是被标号的物品,互不相同,可以被区分开来。


    n个不同的物品划分成k个非空的不可区分的集合的数目是 第二类stiring数




    展开全文
  • 关于acm中常见的计算组合数的方法总结

    千次阅读 多人点赞 2014-02-27 20:28:46
    关于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(不一定,受限于内存)
      const int MAXN1 = 1000;
      const int MAXN2 = 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;
      }


    展开全文
  • C++求解组合数的具体实现

    千次阅读 多人点赞 2020-09-20 12:54:34
    很少写关于具体算法的总结笔记,因为很难把一个算法...这次想总结一下组合数的具体实现,原因是最近总是碰见组合数,所以决定来写写,免得每次从头推导公式耽误时间。排列组合经常会作为一个问题解决方案中一部分...

    前言

    很少写关于具体算法的总结笔记,因为很难把一个算法从头到尾的叙述清晰并且完整,容易造成误解。这次想总结一下组合数的具体实现,原因是最近总是碰见组合数,所以决定来写写,免得每次从头推导公式耽误时间。排列组合经常会作为一个问题解决方案中一部分,通常是求某个问题有多少个解,达到某种状态有多少种操作方式等等。

    问题起因

    今天下午解一道简单题,难度简直刷新了我的认知,其中需要用到组合数,但这仅仅是解题的一小部分,没办法,从头推导的,简单优化下,写出了如下代码:

    int C(int a, int b)
    {
        int ans = 1;
        for (int i = a; i > a - b; i--) ans *= i;
        for (int i = b; i > 1; i--) ans /= i;
        return ans;
    }
    

    因为时间紧迫,范围也比较小,同时可以控制 ab 的大小,所以临时写下的这段代码可以运行,不然这段代码会出现各种错误的。

    组合公式

    既然是想做总结,还是从头来看看组合公式,根据原始公式实现算法,并尝试优化它,当熟悉这个套路之后,就可以直接拿来用了,可以节省不少时间,组合公式的常见表示方式如下:

    C n m = n ! m ! ( n − m ) ! = C n n − m , ( n ≥ m ≥ 0 ) C^m_n = \frac{n!}{m!(n-m)!} = C^{n-m}_n,(n \geq m \geq 0) Cnm=m!(nm)!n!=Cnnm,(nm0)

    这个公式写出来清晰多了,n!表示n的阶乘,计算方式为 n*(n-1)*(n-2)*(n-3)*…*3*2*1, 相信很多人都清楚,我们只要把这个数据公式翻译成代码就可以了:

    int C2(int n, int m)
    {
        int a = 1, b = 1, c = 1;
        for (int i = n; i >= 1; --i) a *= i;
        for (int i = m; i >= 1; --i) b *= i;
        for (int i = n-m; i >= 1; --i) c *= i;
        return a/(b*c);
    }
    

    代码比较简单,依次计算公式中三个数的阶乘,然后再做乘除法就可以了,但是你有没有思考过一个问题,int 类型的整数最大能表示的阶乘是多少?是12!,它的值是 479,001,600,它是 int 表示范围内最大的阶乘数,看来这种实现方式局限性很大,如果 n 大于12就没有办法计算了。

    公式变形

    实际上根据阶乘的定义,n! 和 (n-m)! 是可以约分的,将这两个式子约分后,公式可以化简为:

    C n m = n ! m ! ( n − m ) ! = n ( n − 1 ) ( n − 2 ) . . . ( n − m + 1 ) ) m ! , ( n ≥ m ≥ 0 ) C^m_n = \frac{n!}{m!(n-m)!} = \frac{n(n-1)(n-2)...(n-m+1))}{m!},(n \geq m \geq 0) Cnm=m!(nm)!n!=m!n(n1)(n2)...(nm+1)),(nm0)

    公式写成这样之后可以少计算一个阶乘,并且计算的范围也会缩小,代码实现和一开始展示的代码思想是一样的:

    int C3(int n, int m)
    {
        int a = 1, b = 1;
        for (int i = n; i > n - m; --i) a *= i;
        for (int i = m; i >= 1; i--) b *= i;
        return a/b;
    }
    

    这段代码虽然经过了化简,但是当 n 和 m 非常接近的时候,分子还是接近于 n!,所以表示的范围还是比较小。

    递推公式

    直接给出的公式经过化简后还是受制于计算阶乘的范围,得想个办法看看能不能绕过阶乘计算,方法总是有的,并且前辈们已经给我们整理好了,我们总是站在巨人的肩膀上,下面就是递推公式:

    { C n m = 1 , ( m = 0 或 m = n ) C n m = C n − 1 m + C n − 1 m − 1 , ( n > m > 0 ) \begin{cases} {C^m_n} = 1,\qquad\qquad\qquad (m=0 或 m=n) \\ {C^m_n} = {C^m_{n-1}} + {C^{m-1}_{n-1}},\qquad(n > m > 0) \end{cases} {Cnm=1,(m=0m=n)Cnm=Cn1m+Cn1m1,(n>m>0)

    递归实现

    有了上面的分段函数表示,就满足了递归的条件,既有递归调用缩小规模,也有递归出口,这样实现起来很简单,代码如下:

    int C4(int n, int m)
    {
        if (n == m || m == 0) return 1;
        return C4(n-1, m) + C4(n-1, m-1);
    }
    

    这两行代码是不是很秀?不过使用递归常常会出现一问题,那就是相同子问题多次计算,导致效率低下,这个计算组合数的方式同样存在重复计算子问题的缺点,我们以调用C4(5, 3)为例,看看下面的调用关系图:

    5,3
    4,3
    3,3
    3,2
    2,2
    2,1
    1,1
    1,0
    4,2
    3,2
    3,1
    2,2
    2,1
    2,1
    2,0
    1,1
    1,0
    1,1
    1,0

    从这个图可以清晰看出C4(3, 2)C4(2, 1) 都被计算了多次,当 m 和 n 的数字比较大的时候,会进行更多次的重复计算,严重影响计算的效率,有没有什么办法解决重复计算的问题呢?

    备忘递归

    解决重复计算的常用方法是利用一个备忘录,将已经计算式子结果存储起来,下次再遇到重复的计算时直接取上次的结果就可以了,我们可以将中间结果简单存储到map中。

    假设 n 不超过10000,这比12已经大太多了,我们可以使用 n * 10000 + m 作为map的键,然后将结果存储到map中,每次计算一个式子前先看查询备忘录,看之前有没有计算过,如果计算过直接取结果就可以了,代码简单实现如下:

    int C5(int n, int m, map<int, int>& memo)
    {
        if (n == m || m == 0) return 1;
    
        auto itora = memo.find((n-1)*10000+m);
        int a = itora != memo.end() ? itora->second : C4(n-1, m);
        if (itora == memo.end()) memo[(n-1)*10000+m] = a;
    
        auto itorb = memo.find((n-1)*10000+m-1);
        int b = itorb != memo.end() ? itorb->second : C4(n-1, m-1);
        if (itorb == memo.end()) memo[(n-1)*10000+m-1] = b;
    
        return a + b;
    }
    

    使用 map 作为备忘录可以避免重复计算,这是解决递归效率低下的常用方法,那么有了递推公式不使用递归实现可不可以呢?当然可以了,针对于这个问题,有了递推公式我们还可以使用动态规划(dp)的方式来实现。

    动态规划

    动态规划常常适用于有重叠子问题和最优子结构性质的问题,试图只解决每个子问题一次,具有天然剪枝的功能。基本思想非常简单,若要解一个给定问题,我们需要解其不同子问题,再根据子问题的解以得出原问题的解。

    再回顾一下递推公式:

    { C n m = 1 , ( m = 0 或 m = n ) C n m = C n − 1 m + C n − 1 m − 1 , ( n > m > 0 ) \begin{cases} {C^m_n} = 1,\qquad\qquad\qquad (m=0 或 m=n) \\ {C^m_n} = {C^m_{n-1}} + {C^{m-1}_{n-1}},\qquad(n > m > 0) \end{cases} {Cnm=1,(m=0m=n)Cnm=Cn1m+Cn1m1,(n>m>0)

    翻译成人话就是,当m等于0或者等于n的时候,组合数结果为1,否则组合数结果等于另外两个组合数的和,我们可以采用正向推导的方式,将 n 和 m 逐步扩大,最终得到我们想要的结果,定义dp表格如下:

    n\m(0)(1)(2)(3)(4)(5)
    (0)1
    (1)11
    (2)121
    (3)1331
    (4)1464<1>
    (5)1510==>10<5><1>

    从表格可以清晰的看出求解 C(5,3) 只需要计算5行3列(从0开始)的数据,其余的值可以不用计算,这样我们就可以对照着表格写代码啦,定义一个dp数组,然后双重for循环就搞定了:

    int C6(int n, int m)
    {
        if (n == m || m == 0) return 1;
    
        vector<vector<int>> dp(n+1, vector<int>(m+1));
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= i && j <= m; j++)
                if (i == j || j == 0) dp[i][j] = 1;
                else dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
    
        return dp[n][m];
    }
    

    至此,我们就采用了非递归的方式求解出了组合数的结果,但是这里的空间有点浪费,每次都要花费O(mn)的空间复杂度,有没有办法降低一点呢?我们可以找找规律进行压缩。

    压缩DP

    观察之前的动态规划实现的代码,我们发现求解第 i行的数据时只与第 i-1 行有关,所以我们可以考虑将二维数据压缩成一维,还是逐行求解,只不过可以用一维数组来记录求解的结果,优化代码如下:

    int C7(int n, int m)
    {
        if (n == m || m == 0) return 1;
    
        vector<int> dp(m+1);
        for (int i = 0; i <= n; i++)
            for (int j = min(i, m); j >= 0; j--)
                if (i == j || j == 0) dp[j] = 1;
                else dp[j] = dp[j] + dp[j-1];
    
        return dp[m];
    }
    

    这样我们就将空间复杂度降低到了O(m),需要注意的是在计算dp时,因为采用了压缩结构,为防止前面的修改影响后续结果,所以采用里倒序遍历,这是一个易错的点。

    其他优化

    代码实现到这里,我们的时间复杂度是O(nm),空间复杂是O(m),其实还有进一步的优化空间:

    • 减小m: 因为题目是求解C(n, m),但是我们知道组合公式中,C(n, m) 和 C(n, n-m) 相等,所以当 n-m 小于 m 的时候求解C(n, n-m)可以降低时间复杂度和空间复杂度。

    • 部分剪枝: 观察函数int C7(int n, int m),实际上当i为n时,j没必要遍历到0,只需要计算j等于m的情况就可以了,可以提前计算出结果。

    • 缩小计算范围: 从上面的剪枝操作得到启示,其实每一行没必要全部计算出来,以 C(5,3) 为例,我们只需要计算出表格中有数字的位置的结果就可以了:

    n\m(0)(1)(2)(3)(4)(5)
    (0)1
    (1)11
    (2)121
    (3)331
    (4)64
    (5)==>10

    这样来看每行最多需要计算3个值,那么时间复杂度可以降低到 O(3n),去掉常数,时间复杂度降为 O(n)

    总结

    • 计算组合数可以采用逆向递归和正向递推两种方式,递归时注意写好递归出口
    • 采用正向递推方法时利用动态规划思想,使用子问题的解拼凑出最终问题的解
    • 计算组合数若使用了计算阶乘应注意范围,避免在计算时产生溢出,int最多能表示 12!
    • 使用动态规划方法时可以逐步优化空间和时间,这其实就是优化算法的过程,也是提升的过程
    • 关于组合数的求解方式,我们可以找到时间复杂度O(n)、空间复杂度O(m)的非递归解法

    补充

    感谢 @小胡同的诗 同学的补充和提醒,让我再次感受到数学力量的深不可测,原来求解组合数还有这样一个递推公式:

    { C n m = 1 , ( m = 0 或 m = n ) C n m = n − m + 1 m C n m − 1 , ( n > m > 0 ) \begin{cases} {C^m_n} = 1,\qquad\qquad\qquad (m=0 或 m=n) \\ C_n^m=\frac{n-m+1}{m}C_n^{m-1},\qquad(n > m > 0) \end{cases} {Cnm=1,(m=0m=n)Cnm=mnm+1Cnm1,(n>m>0)

    这个公式厉害就厉害在它是一个线性的,不存在分叉的情况,也就是说即使递归也不会出现重复的计算,我们简单实现一下。

    反向递归

    int C8(int n, int m)
    {
        if (n == m || m == 0) return 1;
        return C8(n, m-1) * (n-m+1) / m;
    }
    

    代码非常紧凑,也不存在重复计算的情况,当然我们也可以使用正向计算的方式来实现。

    正向递推

    int C9(int n, int m)
    {
        if (n == m || m == 0) return 1;
    
        int ans = 1;
        m = min(m, n-m);
    
        for (int i = 1; i <= m; i++) ans = ans * (n-i+1) / i;
        return ans;
    }
    

    这段代码将时间复杂度降到了O(m),空间复杂度降到了O(1),不过特定的场景还是要选择特定的实现,虽然C9函数在时间复杂度和空间复杂度上都优于 C5 函数,但是如果一个实际问题中需要用到多个组合数的时候,C5 这种采用缓存的方式可能会是更好的选择。


    ==>> 反爬链接,请勿点击,原地爆炸,概不负责!<<==

    想讲故事?没人倾听?那是因为你还未到达一个指定的高度,当你在某个领域站稳了脚跟,做出了成绩,自然有的是时间去讲故事或者“编”故事,到时候随便一句话都会被很多人奉为圭臬,甚至会出现一些鸡汤莫名其妙的从你嘴里“说”出来。在你拥有了讲故事权利的同时,批判的声音也将随之而来~

    展开全文
  • 组合数取模

    万次阅读 多人点赞 2012-10-03 12:41:30
    组合数C(n,m)与C(n[k],m[k])*C(n[k-1],m[k-1])*...*C(n[0],m[0]) mod p同余  除了这个Lucas定理以外,还要用到快速幂和另外一个不知名定理: 若p为质数,则(a/b)(mod p) = a * b^(p-2) (mod p)。如果p不...

    组合数取模在ACM竞赛中是一个很重要的问题,很多选手因为数据太大而束手无策,今天就来详细讲解它。

     

    组合数取模就是求的值,当然根据的取值范围不同,采取的方法也不一样。

     

    接下来,我们来学习一些常见的取值情况

     

    (1)

     

         这个问题比较简单,组合数的计算可以靠杨辉三角,那么由于的范围小,直接两层循环即可。

     

    (2),并且是素数

     

         这个问题有个叫做Lucas的定理,定理描述是,如果

     

        

     

         那么得到

     

        

       

         这样然后分别求,采用逆元计算即可。

     

     

    题目:http://acm.fzu.edu.cn/problem.php?pid=2020

     

    题意:,其中,并且是素数。

     

    代码:

    #include <iostream>
    #include <string.h>
    #include <stdio.h>
    
    using namespace std;
    typedef long long LL;
    
    LL n,m,p;
    
    LL quick_mod(LL a, LL b)
    {
        LL ans = 1;
        a %= p;
        while(b)
        {
            if(b & 1)
            {
                ans = ans * a % p;
                b--;
            }
            b >>= 1;
            a = a * a % p;
        }
        return ans;
    }
    
    LL C(LL n, LL m)
    {
        if(m > n) return 0;
        LL ans = 1;
        for(int i=1; i<=m; i++)
        {
            LL a = (n + i - m) % p;
            LL b = i % p;
            ans = ans * (a * quick_mod(b, p-2) % p) % p;
        }
        return ans;
    }
    
    LL Lucas(LL n, LL m)
    {
        if(m == 0) return 1;
        return C(n % p, m % p) * Lucas(n / p, m / p) % p;
    }
    
    int main()
    {
        int T;
        scanf("%d", &T);
        while(T--)
        {
            scanf("%I64d%I64d%I64d", &n, &m, &p);
            printf("%I64d\n", Lucas(n,m));
        }
        return 0;
    }
    


    由于上题的比较大,所以组合数只能一个一个计算,如果的范围小点,那么就可以进行阶乘预处理计算了。

     

    (3),并且可能为合数

     

        这样的话先采取暴力分解,然后快速幂即可。

     

    题目:http://acm.nefu.edu.cn/JudgeOnline/problemshow.php?problem_id=628

     

    代码:

    #include <iostream>
    #include <string.h>
    #include <stdio.h>
    
    using namespace std;
    typedef long long LL;
    const int N = 200005;
    
    bool prime[N];
    int p[N];
    int cnt;
    
    void isprime()
    {
        cnt = 0;
        memset(prime,true,sizeof(prime));
        for(int i=2; i<N; i++)
        {
            if(prime[i])
            {
                p[cnt++] = i;
                for(int j=i+i; j<N; j+=i)
                    prime[j] = false;
            }
        }
    }
    
    LL quick_mod(LL a,LL b,LL m)
    {
        LL ans = 1;
        a %= m;
        while(b)
        {
            if(b & 1)
            {
                ans = ans * a % m;
                b--;
            }
            b >>= 1;
            a = a * a % m;
        }
        return ans;
    }
    
    LL Work(LL n,LL p)
    {
        LL ans = 0;
        while(n)
        {
            ans += n / p;
            n /= p;
        }
        return ans;
    }
    
    LL Solve(LL n,LL m,LL P)
    {
        LL ans = 1;
        for(int i=0; i<cnt && p[i]<=n; i++)
        {
            LL x = Work(n, p[i]);
            LL y = Work(n - m, p[i]);
            LL z = Work(m, p[i]);
            x -= (y + z);
            ans *= quick_mod(p[i],x,P);
            ans %= P;
        }
        return ans;
    }
    
    int main()
    {
        int T;
        isprime();
        cin>>T;
        while(T--)
        {
            LL n,m,P;
            cin>>n>>m>>P;
            n += m - 2;
            m--;
            cout<<Solve(n,m,P)<<endl;
        }
        return 0;
    }
    


     

    接下来看一些关于组合数取模的典型题目。

     

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=3944

     

    分析:组合数取模的典型题目,用Lucas定理,注意要阶乘预处理,否则会TLE的。

     

     

    题目:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4536

     

    题意:给一个集合,一共个元素,从中选取个元素,选出的元素中没有相邻的元素的选法一共有多少种?

     

    分析:典型的隔板法,最终答案就是。然后用Lucas定理处理即可。

     

     

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=4373

     

    题意:for循环嵌套,有两种形式,第一类从1开始到,第二类从上一层循环当前数开始到,第一层一定

         是第一种类型,求总的循环的次数对364875103取余的结果。

     

    分析:首先可以看出,每一个第一类循环都是一个新的开始,与前面的状态无关,所以可以把个嵌套分为几个不

         同的部分,每一个部分由第一类循环开始,最终结果相乘即可。剩下的就是第二类循环的问题,假设一个

         层循环,最大到,分析一下得到如下结果

        

         (1)只有一层,则循环次数为

     

         (2)只有前两层,则循环次数为

     

             

     

         (3)只有前三层,则循环次数为

     

            

     

          由此得到结论:第的循环次数为

     

    代码:

    #include <iostream>
    #include <string.h>
    #include <stdio.h>
    
    using namespace std;
    typedef long long LL;
    
    const int N = 25;
    const int MOD1 = 97;
    const int MOD2 = 3761599;
    const int MOD = MOD1 * MOD2;
    
    int m,n,k;
    int a[N];
    LL fac1[MOD1+10];
    LL fac2[MOD2+10];
    LL inv1,inv2;
    
    LL quick_mod(LL a,LL b,LL m)
    {
        LL ans = 1;
        a %= m;
        while(b)
        {
            if(b & 1)
            {
                ans = ans * a % m;
                b--;
            }
            b >>= 1;
            a = a * a % m;
        }
        return ans;
    }
    
    LL C(LL n,LL m,LL p,LL fac[])
    {
        if(n < m) return 0;
        return fac[n] * quick_mod(fac[m] * fac[n-m], p - 2, p) % p;
    }
    
    LL Lucas(LL n,LL m,LL p,LL fac[])
    {
        if(m == 0) return 1;
        return C(n % p, m % p, p, fac) * Lucas(n / p, m / p, p, fac);
    }
    
    void Init()
    {
        fac1[0] = fac2[0] = 1;
        for(int i=1; i<MOD1; i++)
            fac1[i] = (fac1[i-1] * i) % MOD1;
        for(int i=1; i<MOD2; i++)
            fac2[i] = (fac2[i-1] * i) % MOD2;
        inv1 = MOD2 * quick_mod(MOD2, MOD1-2, MOD1);
        inv2 = MOD1 * quick_mod(MOD1, MOD2-2, MOD2);
    }
    
    int main()
    {
        Init();
        int T, tt = 1;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d%d",&n,&m,&k);
            for(int i=0; i<k; i++)
                scanf("%d",&a[i]);
            a[k] = m;
            LL ans = 1;
            for(int i=0; i<k; i++)
            {
                LL m1 = Lucas(a[i+1] - a[i] + n - 1, a[i+1] - a[i], MOD1, fac1);
                LL m2 = Lucas(a[i+1] - a[i] + n - 1, a[i+1] - a[i], MOD2, fac2);
                LL mm = (m1 * inv1 + m2 * inv2) % MOD;
                ans = ans * mm % MOD;
            }
            printf("Case #%d: ",tt++);
            cout<<ans<<endl;
        }
        return 0;
    }
    


     

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=4349

     

    题意:中有多少个奇数,其中

     

    分析:其实组合数判断奇偶性有一个优美的结论

              

                如果,那么为奇数,否则为偶数

     

                当然本题要判断的组合数很多,所以不能用上述结论,只能另辟蹊径。由于是判断奇偶性,那么就是判断

         是否为1,利用Lucas定理,先把化为二进制,这样它们都是01序列了。我们又知道

         。这样中为0的地方对应的中的位置只有一种可能,那就是0

     

          这样我们可以不用管中为0的地方,只考虑中为1的位置,可以看出,中为1的位置对应的中为0

          或1,其结果都是1,这样答案就是:1<<(二进制表示中1的个数)

     

    代码:

    #include <iostream>
    #include <string.h>
    #include <stdio.h>
    
    using namespace std;
    
    int main()
    {
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            int cnt = 0;
            while (n)
            {
                if (n & 1) cnt++;
                n >>= 1;
            }
            printf("%d\n",1<<cnt);
        }
        return 0;
    }
    

     

    题目:http://61.187.179.132/JudgeOnline/problem.php?id=1951

     

    题意:给定两个正整数,其中,求下面表达式的值

     

        

     

    分析:由于999911659是素数,用费马小定理降幂得到

     

         

     

         现在关键是求

        

        

     

         那么我们枚举分别计算,但是模的是合数,所以对999911658进行分解得到

     

         ,那么分别求,即

     

         

     

         然后进一步得到同余方程组为

     

          

     

         再通过中国剩余定理(CRT)可以求得最终答案

     

    代码:

    #include <iostream>
    #include <string.h>
    #include <stdio.h>
    
    using namespace std;
    typedef long long LL;
    
    const int P = 999911659;
    
    LL a[5] = {0, 0, 0, 0};
    LL m[5] = {2, 3, 4679, 35617};
    LL fac[5][36010];
    LL N, G;
    
    void Init()
    {
        for(int i=0; i<4; i++)
        {
            fac[i][0] = 1;
            for(int j=1; j<36010; j++)
                fac[i][j] = fac[i][j-1] * j % m[i];
        }
    }
    
    LL quick_mod(LL a,LL b,LL m)
    {
        LL ans = 1;
        a %= m;
        while(b)
        {
            if(b & 1)
            {
                ans = ans * a % m;
                b--;
            }
            b >>= 1;
            a = a * a % m;
        }
        return ans;
    }
    
    LL C(LL n,LL k,int cur)
    {
        LL p = m[cur];
        if(k > n) return 0;
        return fac[cur][n] * quick_mod(fac[cur][k] * fac[cur][n-k], p - 2, p) % p;
    }
    
    LL Lucas(LL n,LL k,int cur)
    {
        LL p = m[cur];
        if(k == 0)  return 1;
        return C(n % p, k % p, cur) * Lucas(n / p, k / p, cur) % p;
    }
    
    void extend_Euclid(LL a, LL b, LL &x, LL &y)
    {
        if(b == 0)
        {
            x = 1;
            y = 0;
            return;
        }
        extend_Euclid(b, a % b,x, y);
        LL tmp = x;
        x = y;
        y = tmp - a / b * y;
    }
    
    LL RemindChina(LL a[],LL m[],int k)
    {
        LL M = 1;
        LL ans = 0;
        for(int i=0; i<k; i++)
            M *= m[i];
        for(int i=0; i<k; i++)
        {
            LL x, y;
            LL Mi = M / m[i];
            extend_Euclid(Mi, m[i], x, y);
            ans = (ans + Mi * x * a[i]) % M;
        }
        if(ans < 0)
            ans += M;
        return ans;
    }
    
    int main()
    {
        Init();
        while(cin>>N>>G)
        {
            a[0] = a[1] = 0;
            a[2] = a[3] = 0;
            if(G == P)
            {
                cout<<"0"<<endl;
                continue;
            }
            G %= P;
            for(int i=1; i*i <= N; i++)
            {
                if(N % i == 0)
                {
                    LL x = i;
                    a[0] = (a[0] + Lucas(N, x, 0)) % m[0];
                    a[1] = (a[1] + Lucas(N, x, 1)) % m[1];
                    a[2] = (a[2] + Lucas(N, x, 2)) % m[2];
                    a[3] = (a[3] + Lucas(N, x, 3)) % m[3];
                    x = N / i;
                    if(i * i != N)
                    {
                        a[0] = (a[0] + Lucas(N, x, 0)) % m[0];
                        a[1] = (a[1] + Lucas(N, x, 1)) % m[1];
                        a[2] = (a[2] + Lucas(N, x, 2)) % m[2];
                        a[3] = (a[3] + Lucas(N, x, 3)) % m[3];
                    }
                }
            }
            LL ans = quick_mod(G, RemindChina(a, m, 4), P);
            cout<<ans<<endl;
        }
        return 0;
    }
    


     

    题目:已知有如下表达式

     

        

     

          给定,求

     

    分析:如果直接二项式展开,这样会很麻烦,而且不容易求出,本题有技巧。做如下变换

     

         

      

         所以问题变为求的值。     

     

    展开全文
  • 4. 常见的边界

    千次阅读 2014-05-26 23:30:31
    1) 对16-bit 的整数而言 32767 和 -32768 是边界 2) 屏幕上光标在最左上...1) 边界分析使用与等价类划分法相同的划分,只是边界分析假定错误更多地存在于划分的边界上,因此在等价类的边界上以及两侧的情况设计测
  • 数电4_4——常见组合逻辑电路(3)数据选择器

    千次阅读 多人点赞 2020-05-06 09:44:25
    数据选择器1.1 工作原理1.1.1 电路图1.1.2 写出逻辑表达式1.1.3 对应真表1.2 应用1.2.1 用双四选一设计八选一1.2.2 用数据选择器设计组合逻辑电路1.2.2.1 用四选一实现1.2.2.2 用八选一实现1.2.2.3 设计全减器 ...
  • 这个问题也比较常见的,在面试题或者工作中都有类似情况。
  • 常见数字IC设计,FPGA面试问题总结

    万次阅读 多人点赞 2018-07-16 21:53:01
    可以将较大的组合逻辑分解为较小的N块,通过适当的方法平均分配组合逻辑,然后在中间插入触发器,并和原触发器使用相同的时钟,就可以避免在两个触发器之间出现过大的延时,消除速度瓶颈,这样可以提高电路的工作...
  • (三)常见的数字逻辑电路器件及属性

    千次阅读 2019-11-06 13:59:33
    #组合逻辑电路 编码器 译码器 数据选择器(多路开关、多路复用器) 加法器 数值比较器 #半导体存储电路 锁存器 触发器 锁存器与触发器的比较 寄存器 存储器 随机存储器(静态SRAM、动态DRAM 是时序逻辑电路) ...
  • 从给定有序数组中选取任意个(可重复),使其和为给定(leetcode39): Example 1: Input: candidates = [2,3,6,7], target = 7 A solution set is: [ [7], [2,2,3] ] 思路:回溯法的练习题。因为可以重复,...
  • 思路:从头遍历,查找当前这个在路径中时能不能和后面的构成和,如果可以就输出这个路径,如果加上这个比和sum大,说明不能有当前这个,如果现在的和比sum小,就放入路径,继续查找。 在VS2010中的程序如下...
  • JavaScript在其内部封装了一个Array对象,使得我们可以方便地使用数组这种简单的数据结构,同时,也在 Array对象的原型上定义了一些常用并且很有用的操作组的函数。...JavaScritp常见的操作组的
  • 一、十一个组合恒等式 、 二、组合恒等式 证明方法 、 三、组合数 求和 ∑ 方法
  • 采用逻辑门和MSI模块来进行组合逻辑电路的设计,需要我们根据实验的需求和电路的功能要求,明确输出量与输入量之间的关系,即得到一张真表(或者是功能表)。根据这张真表,我们还需要将其转化成逻辑函数,即用...
  • 本文主要总结在一个数组中取出两个,这两个满足条件为:两之和为制定目标target,并且函数返回这两个下表。 示例: 给定 nums = [5,6,7,8,9,10], target = 19 因为 nums[4] + nums[5] = 9 + 10 = 19 ...
  • 编程常见的命名法

    万次阅读 2019-02-28 12:07:21
    编程常见的命名法 1、匈牙利命名(Hungarian) 广泛应用于Microsoft Windows这类环境中的开发 标识符的名字以一个或者多个小写字母开头作为前缀,标识出变量的作用域, 类型等 前缀之后的是首字母大写的一个单词...
  • 常见Excel技巧表

    万次阅读 2018-12-09 16:31:39
    EXCEL常见技巧锦集 一、基础操作部分: 001、Excel365基础工作界面介绍 002、光标跳转设置、常用的录入技巧 003、多个单元格内容复制到一个单元格中、CTRL+D填充、快速做序列号 004、实时预览、双击格式刷、...
  • 数据库常见面试题(附答案)

    万次阅读 多人点赞 2019-03-13 00:54:20
    组合索引 为了更多的提高mysql效率可建立组合索引,遵循”最左前缀“原则 失效条件 条件是or,如果还想让or条件生效,给or每个字段加个索引 like查询,以%开发 内部函数 对索引列进行计算 is null不会用,is not ...
  • 常见数据库面试问题

    万次阅读 多人点赞 2018-03-08 20:12:45
    常见的数据库面试题有哪些呢?(非DBA向) (一)什么是存储过程?有哪些优缺点? 存储过程是一些预编译的SQL语句。 更加直白的理解:存储过程可以说是一个记录集,它是由一些T-SQL语句组成的代码块,这些T-SQL语句...
  • Jedis常见异常汇总

    万次阅读 2018-03-19 20:00:01
    四、客户端连接达到最大 1.异常堆栈 redis .clients .jedis .exceptions .JedisDataException : ERR max number of clients reached 2.异常描述: 如果客户端连接超过了Redis实例配置的最大...
  • Stata: 统计组内非重复

    千次阅读 2019-08-26 09:48:25
    3 应用范例 sysuse "auto.dta", clear egen a1 = nvals(rep78) //使用 nvals() 得到 rep78 的非重复 egen a2 = nvals(rep78), by(foreign) //不同 foreign 类别下 rep78 的非重复 egen a2 = nvals(rep...
  • DICOM图像像素、灰度与CT

    万次阅读 2018-08-28 11:03:18
    图像灰度的概念是什么?灰度也可以认为是亮度,简单说就是色彩的深浅程度。  实际上在我们的日常生活中,通过三原色色彩深浅的组合,可以组成各种不同的颜色。产品能够展现的灰度数量越多,也就意味着这款产品的...
  • 常见的引擎:InnoDB MyISAM Memory/Heap BDB Merge Example CSV MaxDB Archive 不同的引擎在保存表的结构和数据时采用不同的方式 MyISAM表文件含义:.frm表定义,.MYD表数据,.MYI表索引 InnoDB表文件含义:.frm...
  • 常见分类算法优缺点

    千次阅读 2018-10-21 21:36:54
    按这种算法得到的随机森林中的每一棵都是很弱的,但是大家组合起来就很厉害了。可以这样比喻随机森林算法:每一棵决策树就是一个精通于某一个窄领域的专家(因为我们从M个feature中选择m让每一棵决策树进行学习),...
  • 数据结构算法常见面试考题

    万次阅读 多人点赞 2018-11-08 09:29:44
    一般情况下,不是所有的节点都有对应的,只有叶子节点和部分内部节点所对应的键才有相关的。 在图示中,键标注在节点中,标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie 可以看作是一个确定...
  • 常见概率题

    万次阅读 2020-03-18 20:38:05
    从n个中生成m个不重复的随机数 import random for i in range(n): x = random.randint(i, n) if x < m: print(i) m -= 1 由这个for循环循环n次,且在满足条件时才输出i,可知,输出m个不同的要求已满足...
  • 笔试题—字符串常见的算法题集锦

    千次阅读 2016-09-21 00:01:35
    笔试题—字符串常见的算法题集锦本篇博客主要讲解一下四个问题 KMP算法 字母倒序输出 全排列 全组合 KMP算法关于KMP算法的分析,这里就不讲解了,有兴趣的可以参考这篇博客:从头到尾彻底理解KMP代码如下...
  • Python基础常见面试题总结

    万次阅读 多人点赞 2019-03-08 16:36:40
    以下是总结的一些常见的Python基础面试题,帮助大家回顾基础知识,了解面试套路。会一直保持更新状态。 PS:加粗为需要注意的点。 基础知识题 1、深拷贝和浅拷贝的区别是什么? 深拷贝是将对象本身复制给另一个对象...
  • MPAndroidChart常见设置属性(一)——应用层

    万次阅读 多人点赞 2016-08-16 17:08:37
    MPAndroidChart常见设置属性(一)——应用层 MPAndroidChart项目实战(一)——实现对比性柱状图 MPAndroidChart项目实战(二)——双平滑曲线(双折线图)和MarkView实现 MPAndroidChart项目实战(三)——饼状...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 209,822
精华内容 83,928
关键字:

常见组合数的值