有一个长度为 nn 的括号串,仅包含左括号(和右括号),求括号串内子串()出现次数的期望,答案对 10000000071000000007 取模。 如果你不知道什么是期望,可以理解为长度为 nn 的所有仅包含(和)的字符串中子串()出现次数的总和除以 2n2n 的商。c++
时间: 2024-09-17 10:04:25 浏览: 22
这个问题是一个组合数学和概率统计的问题,涉及到二项式分布。在一个长度为 nn 的括号串中,每个位置上都有独立的概率为 1/21/2 是开括号,也是闭括号。我们需要计算的是恰好形成子串 () 的情况,即两个连续的括号,其概率为 (1/2)^2 = 1/41/4。
对于每一个位置,它形成子串 () 的概率是独立的,所以总的期望次数 E 是 n * (1/4)n * (1/4),因为有 n 个位置可以成为第一个开放括号,然后紧跟着一个关闭括号。
为了找到最终的答案,我们将这个乘积除以总的括号串数目,即 2^n2^n,并取模 10000000071000000007。这是一个无穷级数,可以用等比数列的公式来计算:
E ≈ (n * (1/4)) / (2^n) % 1000000007
这里的除法实际上是整数除法,因为分母总是2的幂次,结果会是一个分数形式。然后我们取余数得到期望值。
如果你需要编写C++代码来解决这个问题,可以考虑使用循环和取模运算:
```cpp
#include <iostream>
using namespace std;
const long long MOD = 1000000007LL;
long long power(long long base, long long exponent) {
if (exponent == 0) return 1;
long long half = power(base, exponent / 2);
half %= MOD;
if (exponent % 2 == 0) return (half * half) % MOD;
else return ((base * half) % MOD * half) % MOD;
}
long long expectedOccurrences(int n) {
return (n * (1LL << 2) % MOD) / (power(2, n) % MOD);
}
int main() {
int n;
cin >> n;
cout << expectedOccurrences(n) << endl;
return 0;
}
```
注意:这个程序计算了整个序列的期望值,而不是单次随机选择后的期望,因为它基于整个序列的结构。