Problem 3531 --字符串修改

3531: 字符串修改

上一题 正确率: $16.67\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $120$ 正确数量 $20$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 数学 统计

Description

给定两个由0与1组成的长度均为N的序列S和T，通过不断改变S[i]的值的操作（0改为1或者1改为0），使得序列S与序列T相同。

    定义改变S[i]的值的花费为D*C[i]，其中D是在此操作之前，序列中满足S[j]≠T[j]的j的个数（1<=j<=N）。C[i]表示对i位置进行变换的代价。

    对于一个固定长度N，共有2^N*2^N对由01组成的序列（S,T），计算所有f(S,T)的总和，并输出它对10^9+7取模的结果。f（S,T）是某个序列（S,T）经过操作后所需要的最少的花费。


数据范围：1<N<=2*10^5,1<=C[i]<=10^9

Input

输入第一行为一个整数N，表示S与T的长度，第二行共N个整数，C[1],C[2],C[3],…,C[N]。

Sample Input复制

1
1000000000

Sample Output复制

999999993

提示

样例1：S可取0、1，T可取0、1，共有f(0,0)，f(0,1)，f(1,0)，f(1,1)四种情况f(0,0)=0,f(1,1)=0,f(1,0)=f(0,1)=10^9，故最终结果为2*10^9, 取模可得999999993。 样例2：针对S=(0,1),T=(1,0)这个序列对，首先将S1改为1，所需花费为5*2=10。再将S2改为0，造成的花费为8*1=8，故f(S,T)=18。

推荐代码 查看3531 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$74 $ms] YKgsmUDq 760658 2021-07-12 19:06:28
内存最少[$6152 $KB] YKgsmUDq 760658 2021-07-12 19:06:28
第一AC Karlis 629704 2020-10-20 14:28:01
第一挑战 Karlis 629704 2020-10-20 14:28:01

赛题来源/所属竞赛 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛