文章关键词:CF850E Random Elections 题解 Lin

CF850E Random Elections 题解

作者:神秘网友 发布时间:2021-10-13 07:24:06

CF850E Random Elections 题解

Link.

Codeforces
Luogu

Description.

有一个函数 \(f(S)\) 表示当状态为 \(S\) 的投票状态是 \(1\) 赢还是 \(2\) 赢。
现在每个人等概率随机一个 ABC 的排列表示三个候选人的优先级。
进行三轮大选,问存在一个人赢了两局的概率。
保证 \(f(S)=f(T\oplus S)\),\(T\) 表示全集。

Solution.

首先 A,B,C 本质相同,可以答案 \(\times 3\) 然后算 A win 的概率。
A 如果 win 了,考虑设第一次关于 A 的大选结果状态是 \(A\),第二次是 \(B\)。
则有 \(f(A)=f(B)=1\)。
考虑每位贡献,如果 \(A\) 的第 \(i\) 位和 \(B\) 的第 \(i\) 位相同,则有两种不同的选法(比如 ABCACB),否则一种。
发现是 XOR,直接 FWT 即可。

Coding.

点击查看代码
//是啊,你就是那只鬼了,所以被你碰到以后,就轮到我变成鬼了{{{
#includebits/stdc++.h
using namespace std;typedef long long ll;
templatetypename Tinline void read(T x)
{
	x=0;char c=getchar(),f=0;
	for(;c48||c57;c=getchar()) if(!(c^45)) f=1;
	for(;c=48c=57;c=getchar()) x=(x1)+(x3)+(c^48);
	fx=-x:x;
}
templatetypename T,typename...Linline void read(T x,L...l) {read(x),read(l...);}//}}}
const int N=1048577,P=1e9+7;int n,a[N];char ch[N];
inline void FWT(int n,int *a,int fg)
{
	for(int d=1;dn;d=1) for(int i=0;in;i+=(d1)) for(int j=0;jd;j++)
		{int x=a[i+j],y=a[i+j+d];a[i+j]=1ll*(x+y)*fg%P,a[i+j+d]=1ll*(x-y+P)*fg%P;}
}
inline int bit(int x) {int rs=0;for(;x;rs+=(x1),x=1);return rs;}
int main()
{
	read(n),scanf("%s",ch);
	for(int i=0;i(1n);i++) a[i]=ch[i]^48;
	FWT(1n,a,1);for(int i=0;i(1n);i++) a[i]=1ll*a[i]*a[i]%P;
	FWT(1n,a,(P+1)1);int rs=0;
	for(int i=0;i(1n);i++) rs=(rs+(1ll(n-bit(i)))*a[i])%P;
	return printf("%lld\n",rs*3ll%P),0;
}

本文章教程介绍完毕,更多请访问跳墙网其他文章教程!

CF850E Random Elections 题解 相关文章

  1. CF1487D Pythagorean Triples 题解

    为什么题解里面都写得这么复杂

  2. 2021.1.27训练题解(CF1017D,CF1015E2,CF1012C)

    \(2021.1.27\)训练题解\((CF1017D,\space CF1015E2,\space CF1012C)\) \(1.CodeForces\space \space CF1017D\)题解 本题目提供\(2\)种解法。 题解:解法一(我的zzt的) 在想不出来解法的时候,仔细观察题目。 我们发现\(n\le12\),而题目又是围绕\(01\)串展

  3. 【题解】 CF1495E Qingshan and Daniel 官方中文题解

    Legend Link \(textrm{to Codeforces}\)。 自我感觉是出的还行的一道题目呀。 Editorial 首先要特判掉只有一个队伍有机器人的情况。 考虑当游戏结束时,总存在至少一个队伍的所有机器人都没有手牌。设此队伍为 \(A\),另一队伍为 \(B\)。...

  4. 题解-CF1479

    不放文章里了,不讲 wood 的偷袭怪 @【数据删除】 耗子尾汁。 这题不难,但是想要介绍两种方法。 法 1 这是一个有关数颜色的问题,直接树上莫队。 在莫队上分块,对于每一个块维护可能成为答案的数的队列。 修改的时...

  5. CF1480 题解

    CF1480A Yet Another String Game Problem 给出一个字符串,两人轮流操作,每次操作可以将一个字符改为另外一个字符,当不可以不改动,先手目标是让最终字符串字典序最小,后手目标相反,求最终字符串。 Sol 贪心地模拟即可。 #define ...

  6. 题解CF054G

    题意描述 Link \(kals\)已经翻得很好了~~ Sol 设\(S_a\)为\(a\)点所在集合的集合,\(S_b\)为\(b\)点所在集合的集合,每次连边\((a,b)\) ,边权为\(S_a\)交\(S_b\)的大小,这样建出一张完全图来,跑最大生成树(\(why\)感性理解:如果我连交集...

  7. CF878D题解

    听说 WC2021 的 T2 和这题解法类似,于是就来做一发。 题意简述 初始有 \(k\) 个生物,编号分别为 \(1,2,\ldots,k\) ,每个生物有 \(n\) 个属性,第 \(i\) 个生物的第 \(j\) 个属性为 \(a_{i,j}\) 。 现在有 \(q\) 次操作,形式如下: 1 x y 表示...

  8. 题解[CF1025D]

    题意简述 给定一棵\(BST\)的点数和点权,且满足相连的点的最小公约数都不为\(1\) ,问是否能还原 这棵\(BST\)的形态。 Sol 题目给出的点权序列是有序的,而且又是一棵\(BST\) , 所以对于区间\([l,r]\)而言,这整个区间的点的父亲一...

  9. CF 1383 F 题解

    CF 1383 F 题解 转换为最小割。 /*{####################### Author ## Gary ## 2021 #######################*/#includebits/stdc++.h#define rb(a,b,c) for(int a=b;a=c;++a)#define rl(a,b,c) for(int a=b;a=c;--a)#define LL long long#define IT iterat

  10. 题解 CF392E 【Deleting Substrings】

    CF392E 【Deleting Substrings】 感谢学长对本题给予指导。 区间 \(dp\) 经典题。 Prelude 大概是一道比较显然的区间 \(dp\) 。 观察题目的几个性质。 从那个 \(\texttt{inequality}\) 可以看出题目每次删除操作只能删去一个 严格的 峰形/上升/下...

  11. CF533F Encoding 题解

    题目链接CF533F Encoding 提示1: ??\(\mathcal O(26^2*n)\) 的算法可通过。常用的几种字符串匹配算法kmp,AC自动机,哈希都可以解决该问题 (后两者可以优化到 \(\mathcal O(26*n)\) )。 提示2: ??将文本串 \(S\) 和模式串 \(T\) 中的 \(26\) 个字...

  12. 题解 CF1495A【Diamond Miner】

    概述 题号 难度 \(AC\)时间及记录 \(\texttt{CF1495A}\) \(\texttt{洛谷难度:暂无评定}\) \(\texttt{On 2021/03/12}\) 解析 这是一道简单题。 题意不难理解。 我们考虑贪心。 实际上只有两种情况: 双线交叉。 双线不交叉。 因为两边之和大于第...

  13. CF1400A String Similarity 题解

    题目传送门 题目解析 第一眼思路:暴搜。然而会T飞,所以不考虑。 我们模拟一下得到答案的过程:(这里以样例第二个点为例) 1110 11000 0000 我们发现在 \(1110000\) 这一串中,最中间的一个数字 \(0\) 在每一个数字中都出现过,...

  14. CF1481B New Colony 题解

    我们观察到一个性质:如果一块石头滚进了垃圾桶,那么它后面滚下来的石头也必定会进入垃圾桶。 这是显然的,因为这块石头没有产生任何贡献,所以不会发生改变。 这样我们就可以暴力枚举每一块石头知道结束或者进入垃...

  15. 题解 CF1492C【Maximum width】

    概述 题号 难度 \(AC\)时间及记录 \(\texttt{CF1492C}\) \(\texttt{洛谷难度:暂无评定}\) \(\texttt{On 2021/02/24}\) 解析 这是一道简单题。 题意也比较清晰。 不难想到, 众所周知, 我们可以对第二个字符串中的每一个字符从前往后扫, 再从...

  16. [题解]CF1475F Unusual Matrix

    题目大意:给定一个 \(n*n\) 的 \(01\) 矩阵,每次操作可以选择一行或者一列,整体 \(xor\) \(1\) ,求经过无限多次操作,能否变为目标矩阵 我们发现,每一行或每一列至多被操作一次,且如果某一列或某一列的操作确定,整个矩阵...

  17. 题解 CF1495F Squares

    题解 CF1495F Squares 题目链接 题意简述 给定长度为 \(n\) 的三个数组 \(a,b,p\) ,其中 \(p\) 是一个排列,构建一张 \(n+1\) 个点(点编号 \(1\sim n+1\) )的 DAG ,其中点 \(i(1\le i\le n)\) 向 \(i+1\) 连边权为 \(a_i\) 的边并且向 \(j\) ( \(j\) 是

  18. CF1393B Applejack and Storages 题解

    目录 题目翻译 题目解析 代码 题目传送门 题目翻译 你需要维护一个序列,让它满足一下操作: 插入一个数字 删除一个数字,保证这个数字是存在 在每次删除和插入之后查询这些数字是否可以组成一个正方形和矩形 题目解析 ...

  19. 【题解】CF1131C:Birthday

    【题解】CF1131C:Birthday 原题传送门 套路贪心 先排序,成为一个有序数列a1,a2,...,ana_1,a_2,...,a_na1?,a2?,...,an? 像这样子摆放,如何证明正确性呢 首先可以感性得知,如果是最优解,那么任意交换两个数的位置肯定比最优解劣 那么如...

  20. CF436E Cardboard Box 题解

    Problem CF436E Cardboard Box \(n\) 个关卡,对每个关卡,你可以花 \(a_i\) 代价得到一颗星,也可以花 \(b_i\) 代价得到两颗星,也可以不玩。问获得 \(w\) 颗星最少需要多少时间。 Sol 反悔贪心好题。 时隔半年终于落实了 我们考虑如何如...

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2021, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词