P10426 [蓝桥杯 2024 省 B] 宝石组合

· · 题解

题目描述

给定 n 个宝石，每种宝石的数量无限制，从中选出 m 个宝石，求共有多少种不同的选法。结果对 10^9+7 取模。

解题思路

这是一道典型的组合数学问题，我们可以使用组合数公式计算出答案。设 C(n,m) 表示从 n 个元素中选出 m 个元素的方案数，则有：

C(n,m)=\frac{n!}{m!(n-m)!}

但是，直接使用组合数公式计算时，由于 n 和 m 的范围非常大，因此需要使用高精度计算。而高精度计算的时间复杂度较高，在本题中容易超时。

因此，我们需要寻找一种更加高效的计算组合数的方法。由于本题中需要对结果取模，我们可以使用 Lucas 定理来计算组合数。

Lucas 定理：设 p 为质数，则对于任意整数 n,m，有：

C(n,m)\equiv C(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)C(n \bmod p ,m \bmod p)\

其中，\lfloor x\rfloor 表示不超过 x 的最大整数。

根据 Lucas 定理，我们可以先将答案分解为模质数的余数，再使用组合数公式计算。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+1;
vector<int>a[N];
int s[N];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    sort(s,s+n);
    for(int i=0;i<n;i++){
        for(int j=1;j<=sqrt(s[i]);j++){
            if(s[i]%j==0){
                a[j].push_back(s[i]);
                if(s[i]/j!=j){
                    a[s[i]/j].push_back(s[i]);
                }
            }
        }
    }
    for(int i=N-1;i>=0;i--){
        if(a[i].sizae()>=3){
            cout<<a[i][0]<<" ";
            for(int j=1;j<3;j++){
                cout<<a[i][j]<<" ";
            }
            break;
        }
    }
    return 0;
}