2021.11.6-测试
T1
给定有n个数的数列，将其随机打乱，求得到升序的期望值，并对\(10^9+7\)取模
今天又看到了一个新的函数
if（is_sorted(a+1,a+n+1)）
题解：
总情况为\(n!\)，当序列中没有重复时得到升序序列的情况为1； 当有两个重复时，情况为2； 三个重复，则为6； . . . 那么就用一个数组记录序列中重复出现的数 即升序情况共有
\[\prod_{i=1}^k{c_i} \]
那么得到升序序列的概率为
\[p=\frac {\prod\limits_{i=1}^k{c_i}}{n!} \]
设期望值为\(E\)，那么有
\[E=p+(1-p)(E+1) \]
解出
\[E=\frac {1}{p}=\frac {n!}{\prod \limits_{i=1}^k{c_i}} \]
因为要取模，所以要用到逆元，由费马小定理可知 \(a^{(p-1)}\equiv 1 \pmod p\) \(a*a^{(p-2)}\equiv 1 \pmod p\) 可知\(a^{(p-2)}\)为\(a\)的逆元
注意原本就是升序需要特判！！！
快速幂代码：
const int MOD=1e9+7;
#define ll long long
ll qp(ll a,ll b){
ll x=1;
a%=MOD;
while(b){
if(b&1) x=x*a%MOD;
a=a*a%MOD;
b>>=1;
}
return x;
}
总代码：
#include
using namespace std;
const int MOD=1e9+7;
#define ll long long
int n,ans;
int a[100005],c[1234567];
ll qp(ll a,ll b){
ll x=1;
a%=MOD;
while(b){
if(b&1) x=x*a%MOD;
a=a*a%MOD;
b>>=1;
}
return x;
}
int main(){
cin>>n;
ll x=1,y=1;
for(int i=1;
i<=n;
i++){
scanf("%d",&a[i]);
x=x*i%MOD;
y=y*(++c[a[i]])%MOD;
}
if(is_sorted(a+1,a+1+n)) x=0;
cout<<(x*qp(y,MOD-2)%MOD+MOD)%MOD< T3 n个砝码，给定其重量\(a_1到a_n\)，然后给你一个字符串S，长度为n，下面开始操作，当\(S_i\)为L时，需要放砝码使天平左边更大，R则使右边更大，输出一项方案
由题目可知，因为要满足每一步条件，那么当\(s[i]=s[i-1]\)时，统计相同的次数m； 将原来的序列排序再分成\(a_1,a_2,...a_m；a_{m+1},...,a_n\)两个序列,那么对于\(s[i]=s[i-1]\)，就将小的序列中的放在与\(s[i]\)相对的位置上去，因为这样可以使得每一次操作后两边可以相对均衡，在下一次操作时更好，如果不等，就将大序列中的较小值放在\(s[i]\)
#include
using namespace std;
int n,a[100005],b[100005];
//b[i]表示放的顺序
int c[100005];
int main(){
cin>>n;
for(int i=0;
i>a[i];
sort(a,a+n);
string s;
cin>>s;
int r=-1,l;
for(int i=0;
i 谢谢观看
PS.
文章图片
【2021.11.6-测试】
推荐阅读
- 喂，你结婚我给你随了个红包
- 成交的种子咖啡冥想
- 一百二十三夜，请嫁给我
- 每日一话（49）——一位清华教授在朋友圈给大学生的9条建议
- 历史教学书籍
- 写给陈羡
- 给予孩子心理平衡的机会
- 请给时间一点时间
- 写给我20岁时爱过的那个男孩
- 别墅庭院设计，不同的别墅庭院设计也给人视觉上完全不一样的！