A 小红的合数寻找

\hspace{15pt} 小红拿到了一个正整数 $x$，她希望你在 $[x,2\times x]$ 区间内找到一个合数，你能帮帮她吗？

\hspace{15pt} 一个数为合数，当且仅当这个数是大于 $1$ 的整数，并且不是质数。

解题思路

因为范围比较小，所以可以暴力枚举答案。
但其实会发现除了2以外的任何偶数都是合数，所以只要 $2\times x$ 不是偶数 $2$ 也就是 $x$ 不为 $1$ 的情况下任何的 $x$ 都有答案 $2\times x$。

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 2e5 + 10;void solve(){int x;cin >> x;if(x != 1){cout << 2 * x << "\n";return;}cout << "-1\n";}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;
//	cin >> t;while(t --){solve();}
}

B 小红的小球染色

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

解题思路

首先最大值很显然是 $n/2$ 个，最小值贪心的去取的话会发现肯定是隔一个染色两个这种，也就耗费三个小球操作一次，但是需要注意如果最后还剩下两个白色小球的话也可以染色，所以最小值其实就是 $(n+1)/3$个。

如下图：7、8小球要被染色成红色。

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 2e5 + 10;void solve(){int n;cin >> n;cout << (n + 1) / 3 << " " << n / 2 << "\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;
//	cin >> t;while(t --){solve();}
}

C 小红的二叉树

\hspace{15pt} 小红想知道，深度为 $n$ 的满二叉树${}^{\text{[1]}}$有多少条长度为 $2$ 的简单路径${}^{\text{[2]}}$？由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。
\hspace{15pt} 在本题中，两条简单路径所包含的点集不同时，被视为不同的。例如，路径 $u-v$ 与路径 $v-u$ 被视为相同的，因为它们均包含点 $u$ 与点 $v$。

\hspace{15pt} 一棵深度为 $h$ 的满二叉树${}^{\text{[1]}}$由恰好 $2^h-1$ 个节点组成，每一个节点要么是叶子节点，要么有 $2$ 个儿子，并且全部叶子节点的深度均为 $h$。
\hspace{15pt} 简单路径${}^{\text{[2]}}$是指这样一条路径，其经过的顶点和边互不相同。

解题思路

首先稍微观察一下这棵树能发现每个鸡爪（蓝色部分）都是都是一条简单路径，而且每层的鸡爪数量从上往下每层是上一层的 $2$ 倍。这里 $n$ 大于等于 $2$ 才会计算这部分的简单路径。

其次，红、蓝、紫、绿圈的每个部分也都是一条简单路径，并且从上往下也是每层是上一层的 $2$倍。这里 $n$ 大于 $2$ 才会计算这部分的简单路径。

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
i64 qm(i64 x,i64 y){i64 res = 1;while(y){if(y & 1){res = res * x % mod;}x = x * x % mod;y >>= 1;}return res;
}
void solve(){int n;cin >> n;int ans = 0;for(int i = 2;i <= n;i ++){ans = ans + qm(2,i - 2);ans %= mod;}for(int i = 3;i <= n;i ++){ans = ans + qm(2,i - 1);ans %= mod;}cout << ans << "\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;
//	cin >> t;while(t --){solve();}
}

D 小红的“质数”寻找

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

解题思路

首先这题的数据范围 $x\left(1\leqq x\leqq 10^{100000}\right)$超大，直接输入不可行，用字符串来输入，这么大的数据就算 $O(N)$ 都无法得到答案，那么我们思考观察是不是一个特性或者结论类的题。那么好，确实通过观察，我们其实只需要判断第一个字符就可以得出答案，且无论如何都有满足条件的质数。

看代码应该就能理解了。

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
void solve(){string s;cin >> s;int x = s[0] - '0';int ans = -1;if(x == 1){ans = 2;}if(x == 2){ans = 3;}if(x == 3){ans = 5;}if(x == 4 || x == 5 || x == 6){ans = 7;}if(x == 7 || x == 8 || x == 9){ans = 11;}cout << ans;for(int i = 1;i < s.size();i ++){cout << "0";}cout << "\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;cin >> t;while(t --){solve();}
}

E 小红的好排列

\hspace{15pt} 小红认为一个偶数长度为 $n$ 的排列 { a 1 , a 2 , … , a n } \{a_1,a_2,\dots,a_n\} {a1​,a2​,…,an​} 是好排列，当且仅当恰好有一半的 $i$ 使得 $a_i\times i$ 是 $3$ 的倍数。
\hspace{15pt} 小红想知道，全部长度为 $n$ 的排列中，共有多少个好排列？由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。

\hspace{15pt} 长度为 $n$ 的排列是由 $1\sim n$ 这 $n$ 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如， { 2 , 3 , 1 , 5 , 4 } \{2,3,1,5,4\} {2,3,1,5,4} 是一个长度为 $5$ 的排列，而 { 1 , 2 , 2 } \{1,2,2\} {1,2,2} 和 { 1 , 3 , 4 } \{1,3,4\} {1,3,4} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

解题思路

排列组合。题目要求恰好有一半的 $i$ 使得 $a_i\times i$ 是 $3$ 的倍数。
首先一个长度为 $n$ 的排列中有 $n/3$个数是 $3$ 的倍数，我们暂且记为 $a$，其次我们把一半的数也就是 $n/2$ 记为 $b$ 。且 $a$ 还是排列中下标 $i$ 为 $3$ 的倍数的个数。也就是说无论如何都一定最少有 $a$ 个满足 $a_i\ast i$ 的数。那么我们只需要考虑 $a$ 个数选 $b-a$ 个在下标不是 $3$ 的倍数的下标中如何排列即可。我们先把 $b-a$ 记为 $c$ 。

我们来举个例子：假设 $n$ 为 6。
然后我们把下标为 $3$ 的倍数的放一堆，不是倍数的放一堆，然后再考虑 $1$ 到 $n$ 的数如何去放。

其中，排列 $A_n^k$ 的公式为：

$A_n^k=\frac{n!}{(n-k)!}$

组合 $C_n^k$ 的公式为：

$C_n^k=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!(n-k)!}$

除法转化为乘法逆元。

参考代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
int fac[N];
void init(int n){fac[0] = 1;for(int i = 1;i <= n;i ++){fac[i] = fac[i - 1] * i % mod;} 
}
int qm(int x,int y){int res = 1;while(y){if(y & 1){res = res * x % mod;}x = x * x % mod;y >>= 1;}return res;
}
int C1(int x,int y){return fac[x] * qm(fac[x - y],mod - 2) % mod; 
}
int C2(int x,int y){return fac[x] * qm(fac[x - y],mod - 2) % mod * qm(fac[y],mod - 2) % mod; 
}
void solve(){int n;cin >> n;init(n);int a = n / 3;int b = n / 2;int c = b - a;int ans = 1;ans = C1(n - a,c) * C1(a,a - c) % mod * C1(n - a,n - a) % mod * C2(a,c) % mod;cout << ans << "\n";}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;
//	cin >> t;while(t --){solve();}
}

F 小红的小球染色期望

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

解题思路

概率期望题。
当 $n$ 等于 $2$ 时，期望为：
$EX=1\times (1+0+0)$

当 $n$ 等于 $3$ 时，期望为：
$EX=\frac{1}{2}\times (1+0+0)+\frac{1}{2}\times (1+0+0)=1$

当 $n$ 等于 $4$ 时，期望为：
$EX=\frac{1}{3}\times (1+0+1)+\frac{1}{3}\times (1+0+0)+\frac{1}{3}\times (1+1+0)=5/3。$

然后我们来看个 $n=6$ 的推导情况再看上面式子会更清晰。

下面我们来计算每对小球的期望：
红色的一对小球也就是第 $1、2$ 个小球被选择的概率为 $\frac{1}{5}$，所以期望为：
$f(红色)=(1+f(0)+f(4))$
其中 $f(0)$ 为这对小球左边 $0$ 个小球的期望， $f(4)$ 为这对小球右边 $4$ 个小球的期望

其他的也是同样的道理。

所以我们可以大概推导到这么期望计算式子：
$f(n)=\frac{1}{n-1}\times (1+f(x)+f(y))$，其中取值区间为 $[1,n)$ （左闭右开）。
这里的 $x$ 为 当前这对小球的左边小球有的小球个数， $y$ 为 当前这对小球的右边边小球有的小球个数
稍微推导一下就是：
$f(n)=\frac{1}{n-1}\times (1+f(x)+f(y))$
   = ${\sum }_{i=1}^{n-1}\frac{1}{n-1}\times (1+f(i)+f(n-(i+1)))$
   = $\frac{1}{n-1}\times {\sum }_{i=1}^{n-1}(1+f(i)+f(n-(i+1)))$
   = $\frac{1}{n-1}\times {\sum }_{i=1}^{n-1}1+\frac{1}{n-1}\times {\sum }_{i=1}^{n-1}f(i-1)+\frac{1}{n-1}\times {\sum }_{i=1}^{n-1}f(n-(i+1))$
   = $\frac{1}{n-1}\times (n-1)+\frac{1}{n-1}\times {\sum }_{i=1}^{n-1}f(i-1)+\frac{1}{n-1}\times {\sum }_{i=1}^{n-1}f(n-(i+1))$
   = $1+\frac{1}{n-1}\times {\sum }_{i=1}^{n-1}f(i-1)+\frac{1}{n-1}\times {\sum }_{i=1}^{n-1}f(n-(i+1))$

此时，令 $j=i-1$，带入得到：

   = $1+\frac{1}{n-1}\times {\sum }_{j=0}^{n-2}f(j)+\frac{1}{n-1}\times {\sum }_{i=1}^{n-1}f(n-(i+1))$

再令 $j=n-(i+1)$，代入得到：

   = $1+\frac{1}{n-1}\times {\sum }_{j=0}^{n-2}f(j)+\frac{1}{n-1}\times {\sum }_{j=n-2}^{0}f(j)$
   = $1+\frac{1}{n-1}\times {\sum }_{j=0}^{n-2}f(j)+\frac{1}{n-1}\times {\sum }_{j=0}^{n-2}f(j)$
   = $1+\frac{2}{n-1}\times {\sum }_{j=0}^{n-2}f(j)$

然后我们把 ${\sum }_{j=0}^{n-2}f(j)$ 用前缀和计算，即 $sum[i]=sum[i-1]+f[i]$，所以 $n$ 个小球的期望就是：
$f(n)=1+\frac{2}{n-1}\times sum[i-2]$
需要稍微注意初始化 $f[0]=f[1]=0,f[2]=1，sum[2]=1$
最后套公式除法变为乘法逆元就可以了。

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
i64 qm(i64 x,i64 y){i64 res = 1;while(y){if(y & 1){res = res * x % mod;}x = x * x % mod;y >>= 1;}return res;
}
void solve(){int n;cin >> n;vector<i64> f(n + 1),sum(n + 1);f[2] = 1,sum[2] = 1;for(int i = 3;i <= n;i ++){f[i] = 1 + 2 * qm(i - 1,mod - 2) * sum[i - 2] % mod;sum[i] = sum[i - 1] + f[i] % mod;}cout << f[n] << "\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t = 1;
//	cin >> t;while(t --){solve();}
}