牛客周赛79题解

A.小红的合数查找

$\hspace{15pt}$ 小红拿到了一个正整数 $x$ ，她希望你在 $[x, 2 \times x]$ 区间内找到一个合数，你能帮帮她吗？
$\hspace{15pt}$ 一个数为合数，当且仅当这个数是大于 $1$ 的整数，并且不是质数。

因为除了2意外的所有偶数都是合数，所以可选的答案要么是 $x$ 要么是 $x 1$ ,所以特判一下1和2再根据 $x$ 的奇偶性输出答案即可

# Python

def solve():
    x = int(input())
    if x == 1:
        print(-1)
    elif x == 2:
        print(4)
    elif x % 2 == 1:
        print(x + 1)
    else:
        print(x)

B.小红的小球染色

$\hspace{15pt}$ 有 $n$ 个白色小球排成一排。小红每次将随机选择两个相邻的白色小球，将它们染成红色。小红将持续这个操作直到无法操作，请你计算小红操作次数可能的最小值和最大值。

很显然最大操作是 $\left \lfloor \frac {n} {2} \right \rfloor$ ，最小操作是 $\left \lfloor \frac {n 1} {3} \right \rfloor$ ，特判一下几个比较小的数的情况防止出错

// C++

void solve(){
    int n;
    std :: cin >> n;
    if(n == 2) {std :: cout << 1 << " " << 1 << endl ; return;}
    else if(n == 3) {std :: cout << n / 3 << " " << n / 2 << endl ; return;}
    int m = n / 3 , mo = n % 3;
    std :: cout << m + (mo >= 2) << " " << n / 2 << endl;
}

C.小红的二叉树

$\hspace{15pt}$ 小红想知道，深度为 $n$ 的满二叉树 $^{\texttt{[1]}}$ 有多少条长度为 $2$ 的简单路径 $^{\texttt{[2]}}$ ？由于答案可能很大，请将答案对 $(10^9 7)$ 取模后输出。
$\hspace{15pt}$ 在本题中，两条简单路径所包含的点集不同时，被视为不同的。例如，路径 $u-v$ 与路径 $v-u$ 被视为相同的，因为它们均包含点 $u$ 与点 $v$ 。
$\hspace{15pt}$ 一棵深度为 $h$ 的满二叉树 $^{\texttt{[1]}}$ 由恰好 $2^h-1$ 个节点组成，每一个节点要么是叶子节点，要么有 $2$ 个儿子，并且全部叶子节点的深度均为 $h$ 。
$\hspace{15pt}$ 简单路径 $^{\texttt{[2]}}$ 是指这样一条路径，其经过的顶点和边互不相同。

考虑简单路径的中点，发现除了根节点意外的所有非叶子节点都可以连出3条路，即答案为 $1 3\times (2^{n-1}-2)$

// C++

const int mod = 1e9 + 7;
int quick_power(int a,int b,int mod){
    int ans=1;
    while(b){
        if(b%2==1) ans=ans*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return ans;
}
void solve(){
    int n;
    std :: cin >> n;
    int ans = 3 * (quick_power(2 , n - 1, mod) - 2);
    ans = (ans + 1) % mod;
    if(n == 1) std :: cout << 0 << endl;
    else std :: cout << ans << endl;
}

D.小红的质数寻找

$\hspace{15pt}$ 小红拿到了一个正整数 $x$ ，她希望你在 $[x, 2 \times x]$ 区间内找到一个正整数，满足该正整数所有数位之和为一个质数，你能帮帮她吗？

发现这道题的数据范围足足有 $1^{100000}$ ,那就完全不用考虑计算了，这是一道构造题

我们假设 $x=a*10^n C$ 其中a为第一位数字,C为后续部分，很显然答案的第一位可以取到 $[a 1,2a]$ 的所有情况,对9种数字分析发现无论如何这个范围里都包含数位和为素数的数，那么只要随便输出一个范围内的素数然后跟上n-1个0即可

// C++

void solve(){
    std :: string s;
    std :: cin >> s;
    int l = s[0] - '0' + 1 , r = (l - 1) * 2;
    for(int i = l;i <= r;i ++){
        if(i == 2 || i == 3 || i == 5 || i == 7 || i == 11){
            std :: cout << i;
            break;
        }
    }
    for(int i = 1;i < num.size();i ++)std :: cout << 0;// 补0
    std :: cout << endl;
}

E.小红的好排列

$\hspace{15pt}$ 小红认为一个偶数长度为 $n$ 的排列 $\{a_1,a_2,\dots,a_n\}$ 是好排列，当且仅当恰好有一半的 $i$ 使得 $a_i \times i$ 是 $3$ 的倍数。
$\hspace{15pt}$ 小红想知道，全部长度为 $n$ 的排列***有多少个好排列？由于答案可能很大，请将答案对 $(10^9 7)$ 取模后输出。
$\hspace{15pt}$ 长度为 $n$ 的排列是由 $1 \sim n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

假设所 $i\operatorname{mod}3==0$ 和所有 $a_i\operatorname{mod}3==0$ 都错开，那就可以得到 $2\times \left \lfloor \frac {n} {3} \right \rfloor$ 个题目要求的数，所以只要这个数不足一半就都是无解的

我们设 $d=2\times \left \lfloor \frac {n} {3} \right \rfloor - \frac{n}{2}$ ，我们需要有d个位置同时满足 $i\operatorname{mod}3==0$ 和 $a_i\operatorname{mod}3==0$ ,这样才能把数量减少到 $\frac{n}{2}$ ,此时有 $C^d_{\frac{n}{3}}$ 个方案，再把3的倍数填进去有 $A^d_{\frac{n}{3}}$ 个方案，把剩余的3的倍数位置用非3的倍数填满有 $A^{\frac{n}{3}-d}_{n-\frac{n}{3}}$ 种方案，剩余的数随机填入剩余位置有 $A^{n-\frac{n}{3}}_{n-\frac{n}{3}}$ 种方案，全部乘起来即可

// C++
const int mod = 1e9 + 7;
// 排列组合类
struct Comb {
  const int P = 13331;
  int qmi(int a, int b) {
    int ans = 1;
    while (b) {
      if (b & 1)
        ans = ans * a % mod;
      a = a * a % mod;
      b >>= 1;
    }
    return ans;
  };
  void init(int M) {
    fac.resize(M + 10, 1);
    inv.resize(M + 10, 1);
    finv.resize(M + 10, 1);
    for (int i = 2; i <= M; i++)
      fac[i] = fac[i - 1] * i % mod;
    finv[M]=qmi(fac[M],mod-2);
    for(int i=M-1;i>=0;i--){
      finv[i]=finv[i+1]*(i+1)%mod;
    }
    inv[1] = qmi(P, mod - 2);
    for (int i = 2; i <= M; i++) {
      inv[i] = inv[i - 1] * P % mod;
 
    }
  };
  int C(int n, int m) {
    assert(n>=0 && m>=0 && n<=m);
    if (n == 0 || m == 0)
      return 1ll;
    int c = fac[m - n] * fac[n] % mod;
    return fac[m] *finv[n]% mod * finv[m-n] % mod;
  };
  int A(int n, int m) { return fac[n] * C(n, m) % mod; }
  std :: vector<int> fac, inv,finv;
};
void solve(){
    Comb T;
    int n;
    std :: cin >> n;
    T.init(1000000);
    if(n / 3 * 2 < n / 2){
        std :: cout << 0 << endl;
        return;
    }
    int d = n / 3 * 2 - n / 2;
    int ans = 1;
    ans = ans * T.C(d , n / 3) % mod;
    ans = ans * T.A(d , n / 3) % mod;
    ans = ans * T.A(n / 3 - d , n - n / 3) % mod;
    ans = ans * T.A(n - n / 3 , n - n / 3) % mod;
    std :: cout << ans << endl;
}

F.小红的小球染色期望

$\hspace{15pt}$ 有 $n$ 个白色小球排成一排。小红每次将随机选择两个相邻的白色小球，将它们染成红色。小红将持续这个操作直到无法操作，请你计算小红操作次数的期望。

这是一道动态规划，定义 $dp_i$ 表示长度为i的期望,我们先考虑第一次操作，枚举第一次操作的左端点，发现一共有 $i-1$ 种可能,每种可能的概率都为 $\frac{1}{i-1}$

此时我们发现小球被第一次操作分成了左右两个部分，左部的长度范围是0到n-2，右部的长度范围是n-2到0,而他们各自的期望在动态规划的过程中已经被求出来了，所以期望操作数为:

dp_i=\frac{2}{i-1} \times \sum ^{i-2}_{j=1}dp_j 1

// C++

const int mod = 1e9 + 7;
int quick_power(int a,int b,int mod){
    int ans=1;
    while(b){
        if(b%2==1) ans=ans*a%mod;
        a = a * a % mod;
        b /=2;
    }
    return ans;
}
void solve(){
    int n;
    std :: cin >> n;
    std :: vector<int> dp(n + 1);
    std :: vector<int> pre(n + 1);
    dp[2] = 1;
    pre[2] = 1;
    for(int i = 3;i <= n;i ++){
        int p = quick_power(i - 1 , mod - 2 , mod);//求出分母逆元
        dp[i] = (pre[i - 2] * 2 % mod * p % mod + 1) %mod;
        pre[i] = (pre[i - 1] + dp[i]) % mod;
    }
    std :: cout << dp[n] << endl;
}