• 组合数的求解（打表，逆元，Lucas 定理，大整数求解）

    885. 求组合数 I

    给定 n

    组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(109+7)

    的值。

    输入格式

    第一行包含整数 n

    。

    接下来 n

    行，每行包含一组 a 和 b

    。

    输出格式

    共 n

    行，每行输出一个询问的解。

    数据范围

    1≤n≤10000

    ,
    1≤b≤a≤2000

    输入样例：

    1. 3
    2. 3 1
    3. 5 3
    4. 2 2

    输出样例：

    1. 3
    2. 10
    3. 1

     coding:

    由于1 ≤ b ≤ a ≤ 2000；所以可以用二维数组把所有组合数的值都存储下来，

    1. /**
    2.  * 由于1 ≤ b ≤ a ≤ 2000；所以可以用二维数组把所有组合数的值都存储下来，
    3. */
    4.  
    5. #include 
    6.  
    7. using namespace std;
    8.  
    9. const int maxn=2010 , mod=1e9+7;
    10. int C[maxn][maxn];
    11.  
    12. void init()
    13. {
    14.     for(int i=0;i
    15.     {
    16.         C[i][0]=1;
    17.         C[i][i]=1;
    18.     }
    19.     
    20.     for(int i=2;i
    21.         for(int j=1;j<=i/2;++j)
    22.         {
    23.             C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    24.             C[i][i-j]=C[i][j];
    25.         }
    26. }
    27.  
    28. int main()
    29. {
    30.     init();
    31.     int n;
    32.     cin >> n;
    33.     while (n -- )
    34.     {
    35.         int a,b;
    36.         cin >> a >> b;
    37.         cout << C[a][b] << endl;
    38.     }
    39.     return 0;
    40. }

    886. 求组合数 II

    给定 n

    组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(109+7)

    的值。

    输入格式

    第一行包含整数 n

    。

    接下来 n

    行，每行包含一组 a 和 b

    。

    输出格式

    共 n

    行，每行输出一个询问的解。

    数据范围

    1≤n≤10000

    ,
    1≤b≤a≤105

    输入样例：

    1. 3
    2. 3 1
    3. 5 3
    4. 2 2

    输出样例：

    1. 3
    2. 10
    3. 1

    假设 a,b,m都是整数，m>1,且ab与1模m同余，则a与b互为模m的逆元。
     * 所以当m为质数的时候，a的m-2次方就是a模m的逆元。(费马小定理)。
     *
     * C(a,b)%mod= a!/(b!*(a-b)!)%mod;
     * 由于1 ≤ b ≤ a ≤ 10^5,所以可以预处理出fac[maxn],infac[maxn](阶乘的结果，阶乘的逆元的结果)
     * 结果直接用逆元进行计算。

    1. /**
    2.  * 假设 a,b,m都是整数，m>1,且ab与1模m同余，则a与b互为模m的逆元。
    3.  * 所以当m为质数的时候，a的m-2次方就是a模m的逆元。(费马小定理)。
    4.  * 
    5.  * C(a,b)%mod= a!/(b!*(a-b)!)%mod;
    6.  * 由于1 ≤ b ≤ a ≤ 10^5,所以可以预处理出fac[maxn],infac[maxn](阶乘的结果，阶乘的逆元的结果)
    7.  * 结果直接用逆元进行计算。
    8. */
    9.  
    10. #include 
    11.  
    12. using namespace std;
    13.  
    14. typedef long long LL;
    15.  
    16. const int maxn=1e5+10,mod=1e9+7;
    17. int fac[maxn],infac[maxn];
    18.  
    19. int qmi(int a,int b,int p) //a^b%p
    20. {
    21.     int res=1;
    22.     while(b)
    23.     {
    24.         if(b&1)
    25.             res=(LL)res*a%p;
    26.         a=(LL)a*a%p;
    27.         b>>=1;
    28.     }
    29.     
    30.     return res;
    31. }
    32.  
    33. void init()
    34. {
    35.     fac[0]=infac[0]=1;
    36.     for(int i=1;i//求阶乘的结果及阶乘的逆元的结果
    37.     {
    38.         fac[i]=(LL)fac[i-1]*i%mod;
    39.         infac[i]=(LL)infac[i-1]*qmi(i,mod-2,mod)%mod;
    40.     }
    41. }
    42.  
    43. int main()
    44. {
    45.     init();
    46.     int n;
    47.     cin >> n;
    48.     while (n -- )
    49.     {
    50.         int a,b;
    51.         cin >> a >> b;
    52.         cout << (LL)fac[a] * infac[b] % mod * infac[a-b] % mod << endl;
    53.     }
    54.     
    55.     return 0;
    56. }
    57.

    887. 求组合数 III

    给定 n

    组询问，每组询问给定三个整数 a,b,p，其中 p 是质数，请你输出 Cbamodp

    的值。

    输入格式

    第一行包含整数 n

    。

    接下来 n

    行，每行包含一组 a,b,p

    。

    输出格式

    共 n

    行，每行输出一个询问的解。

    数据范围

    1≤n≤20

    ,
    1≤b≤a≤1018,
    1≤p≤105

    ,

    输入样例：

    1. 3
    2. 5 3 7
    3. 3 1 5
    4. 6 4 13

    输出样例：

    1. 3
    2. 3
    3. 2

     证明如下：

     

     

     

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. typedef long long LL;
    6.  
    7. int qmi(int a,int b,int p)
    8. {
    9.     int res=1;
    10.     while(b)
    11.     {
    12.         if(b&1)
    13.             res=(LL)res*a%p;
    14.         a=(LL)a*a%p;
    15.         b>>=1;
    16.     }
    17.     return res;
    18. }
    19.  
    20. int CP(int a,int b,int p)
    21. {
    22.     int res=1;
    23.     for(int i=1;i<=b;++i)
    24.     {
    25.         res=(LL)res*(a-b+i) % p;
    26.         res=(LL)res*qmi(i,p-2,p) % p;  //根据费马小定理用逆元求解
    27.     }
    28.     
    29.     return res;
    30. }
    31.  
    32. int Lucas(LL a,LL b,int p)
    33. {
    34.      if(a
    35.         return CP(a,b,p);
    36.     else
    37.         return (LL)CP(a%p,b%p,p) * Lucas(a/p,b/p,p) % p;
    38. }
    39.  
    40. int main()
    41. {
    42.     int n;
    43.     cin >> n;
    44.     while (n -- )
    45.     {
    46.         LL a,b;
    47.         int p;
    48.         cin >> a >> b >>p;
    49.         cout << Lucas(a,b,p) << endl;
    50.     }
    51.     
    52.     return 0;
    53. }

    将求逆元的过程拿到for循环外面能快一个数量级不止。

    如果CP函数这么写，还能快上一倍：

    int CP(int a,int b,int p)
    {
        if(a         return 0;
        int mul=a-b;  //假设b < a-b
        if((a-b) < b) //如果a-b < a，那么还得改变mul和b 的值；（原因是使求阶乘的运算步骤最少）
        {
            mul=b;
            b=a-b;
        }
        
        LL x=1,y=1;
        for(int i=1;i<=b;++i)
        {
            x=(mul+i)*x%p;  //先分别求分子与分母的阶乘，最后再用逆元求结果
            y=y*i%p;
        }
        
        return x*qmi(y,p-2,p) %p;  //用逆元求结果
    }

     将求逆元的过程拿到for循环外面：

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. typedef long long LL;
    6.  
    7. int qmi(int a,int b,int p)
    8. {
    9.     int res=1;
    10.     while(b)
    11.     {
    12.         if(b&1)
    13.             res=(LL)res*a%p;
    14.         a=(LL)a*a%p;
    15.         b>>=1;
    16.     }
    17.     return res;
    18. }
    19.  
    20. int CP(int a,int b,int p)
    21. {
    22.     LL x=1,y=1;
    23.     for(int i=1;i<=b;++i)
    24.     {
    25.         x=x*(a-b+i) % p;
    26.         y=y*i % p;
    27.     }
    28.     
    29.     return x*qmi(y,p-2,p)%p;
    30. }
    31.  
    32. int Lucas(LL a,LL b,int p)
    33. {
    34.      if(a
    35.         return CP(a,b,p);
    36.     else
    37.         return (LL)CP(a%p,b%p,p) * Lucas(a/p,b/p,p) % p;
    38. }
    39.  
    40. int main()
    41. {
    42.     int n;
    43.     cin >> n;
    44.     while (n -- )
    45.     {
    46.         LL a,b;
    47.         int p;
    48.         cin >> a >> b >>p;
    49.         cout << Lucas(a,b,p) << endl;
    50.     }
    51.     
    52.     return 0;
    53. }

    888. 求组合数 IV

    输入 a,b

    ，求 Cba

    的值。

    注意结果可能很大，需要使用高精度计算。

    输入格式

    共一行，包含两个整数 a

    和 b

    。

    输出格式

    共一行，输出 Cba

    的值。

    数据范围

    1≤b≤a≤5000

    输入样例：

    5 3

    输出样例：

    10

    C(a,b) 是个整数，那么我们一定能进行质因数分解；
     * 同样，C(a,b)=a!/(b!*(a-b)!),我们可以把分母与分子也进行质因数分解，
     * 将分子与分母相同的质因子进行指数相减，最后将所有得到的质因数进行相乘，
     * 就能得到最后的结果。
     *
     * 将分子与分母相同的质因子进行指数相减得到的指数一定是大于等于0的吗？
     * 证明：假定存在质因子相减得到的指数小于0的质因子，那么分母一定存在一个
     * 质因子，它与任何质因子都是互质的，因此C(a,b) 的结果就以应该是小数，而不是
     * 整数，这与C(a,b) 应该为整数矛盾，所以将分子与分母相同的质因子进行指数相减
     * 得到的指数一定是大于等于0的，得证！

    1. /**
    2.  * C(a,b) 是个整数，那么我们一定能进行质因数分解；
    3.  * 同样，C(a,b)=a!/(b!*(a-b)!),我们可以把分母与分子也进行质因数分解，
    4.  * 将分子与分母相同的质因子进行指数相减，最后将所有得到的质因数进行相乘，
    5.  * 就能得到最后的结果。
    6.  * 
    7.  * 将分子与分母相同的质因子进行指数相减得到的指数一定是大于等于0的吗？
    8.  * 证明：假定存在质因子相减得到的指数小于0的质因子，那么分母一定存在一个
    9.  * 质因子，它与任何质因子都是互质的，因此C(a,b) 的结果就以应该是小数，而不是
    10.  * 整数，这与C(a,b) 应该为整数矛盾，所以将分子与分母相同的质因子进行指数相减
    11.  * 得到的指数一定是大于等于0的，得证！
    12. */
    13.  
    14. #include 
    15. #include 
    16.  
    17. using namespace std;
    18.  
    19. const int maxn=5010;
    20. int p[maxn] ,num=0 , sum[maxn]; //p存素数，sum素数的指数
    21. bool hs[maxn];
    22.  
    23. void get_primer(int n); //获得n以内的素数
    24. int cal(int a,int p); //a! 内有多少个 质因子p
    25. void get_pow(int a,int b);  //获得C(a,b)内的 质因子的指数
    26. vector<int> mul(vector<int> &A,int b); //高精度与整数的乘法
    27.  
    28. int main()
    29. {
    30.     int a,b;
    31.     cin >> a >> b;
    32.     
    33.     get_primer(a); 
    34.     get_pow(a,b);
    35.     
    36.     vector<int> res;
    37.     res.push_back(1);
    38.     
    39.     for(int i=0;i
    40.         for(int j=0;j
    41.             res=mul(res,p[i]);
    42.             
    43.     for(int i=res.size()-1;i>=0;--i)
    44.         cout << res[i];
    45.     return 0;
    46. }
    47.  
    48. void get_primer(int n) //获得n以内的素数
    49. {
    50.     for(int i=2;i<=n;++i)
    51.     {
    52.         if(!hs[i])
    53.             p[num++]=i;
    54.         for(int j=0;p[j] <= n/i;++j)
    55.         {
    56.             hs[p[j]*i]=1;
    57.             if(i%p[j]==0)
    58.                 break;
    59.         }
    60.     }
    61. }
    62.  
    63. int cal(int a,int p) // a! 内有多少个 质因子p
    64. {
    65.     if(a
    66.         return 0;
    67.     else
    68.         return cal(a/p,p) + a/p ;
    69. }
    70.  
    71. void get_pow(int a,int b)  //获得C(a,b)内的 质因子的指数
    72. {
    73.     for(int i=0;i
    74.     {
    75.         int cnt=cal(a,p[i]) - cal(a-b,p[i]) - cal(b,p[i]);
    76.         sum[i]=cnt;
    77.     }
    78. }
    79.  
    80. vector<int> mul(vector<int> &A,int b) //高精度与整数的乘法
    81. {
    82.     vector<int> res;
    83.     int d=0;
    84.     for(int i=0;isize();++i)
    85.     {
    86.         d+=A[i]*b;
    87.         res.push_back(d%10);
    88.         d/=10;
    89.     }
    90.     
    91.     while(d)
    92.     {
    93.         res.push_back(d%10);
    94.         d/=10;
    95.     }
    96.     
    97.     return res;
    98. }

  • 相关阅读:
    视频画面噪点太多难处理？AI工具一键消除
    B站：AB test [下]
    HBase学习笔记
    物体6D位姿估计方法总结
    Hadoop（HDFS）
    d3dx9_43.dll缺失怎么办？教你一分钟修复d3dx9_43.dll丢失问题
    [附源码]Python计算机毕业设计Django的项目管理系统
    数字样机的前世今生
    【算法练习Day27】买卖股票的最佳时机 II&&跳跃游戏&&跳跃游戏 II
    2022杭电多校 第一场 个人题解（ABCDIHK）
  • 原文地址：https://blog.csdn.net/qq_51825761/article/details/126305599