Random Elections
题意翻译
## 题目描述
总统选举将于明年在Bearland举行!每个人都为此感到非常兴奋!
到目前为止,有三位候选人,A,B和C。
Bearland有n个公民。选举结果将对Bearland所有公民的生活产生很大的影响。由于这一重大责任,每个公民都会随机选择A,B和C之间的六个优先顺序(ABC,ACB,BCA,BAC,CBA,CAB)中的一个。如果该顺序为ABC,表示该选民最支持A,其次是B,最不支持C。
考虑到选民的偏好,Bearland政府已经设计了一个用来确定选举结果的函数$f$。
更具体地说,这个函数需要输入一个长度为$2^n$的01串$x$,并返回一个bool。数据保证$f$满足
$f(1-x_1,1-x_2,\ldots,1-x_n)=1-f(x_1,x_2,\ldots,x_n)$
政府将进行3次比赛:A和B、B和C、C和A
在每一次比赛中(假设是候选人A和B之间的),如果第i个人更支持A,则$x_{i}=1$,否则$x_{i}=0$。假设函数f返回的值是1,则A胜,否则B胜
定义$p$为有一个候选人赢了两场的概率,你需要输出$p\times6^n$模1e9+7的值
## 输入输出格式
##### **输入格式:**
第一行输入一个整数n,表示共有$n$个选民($1\le n\le20$)
第二行输入一个长度为$2^n$的01串。它的第i位表示f(i)的值。例如当第45(101101)位为1时,$f(1,0,1,1,0,1)=1$。
##### 输出格式:
在第一行输出一个整数:$p\times6^n$模1e9+7的值
题目描述
The presidential election is coming in Bearland next year! Everybody is so excited about this!
So far, there are three candidates, Alice, Bob, and Charlie.
There are $ n $ citizens in Bearland. The election result will determine the life of all citizens of Bearland for many years. Because of this great responsibility, each of $ n $ citizens will choose one of six orders of preference between Alice, Bob and Charlie uniformly at random, independently from other voters.
The government of Bearland has devised a function to help determine the outcome of the election given the voters preferences. More specifically, the function is ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF850E/16a9f21887879d53c83c8ee7da474a1c6eb7735a.png) (takes $ n $ boolean numbers and returns a boolean number). The function also obeys the following property: $ f(1-x_{1},1-x_{2},...,1-x_{n})=1-f(x_{1},x_{2},...,x_{n}) $ .
Three rounds will be run between each pair of candidates: Alice and Bob, Bob and Charlie, Charlie and Alice. In each round, $ x_{i} $ will be equal to $ 1 $ , if $ i $ -th citizen prefers the first candidate to second in this round, and $ 0 $ otherwise. After this, $ y=f(x_{1},x_{2},...,x_{n}) $ will be calculated. If $ y=1 $ , the first candidate will be declared as winner in this round. If $ y=0 $ , the second will be the winner, respectively.
Define the probability that there is a candidate who won two rounds as $ p $ . $ p·6^{n} $ is always an integer. Print the value of this integer modulo $ 10^{9}+7=1\ 000\ 000\ 007 $ .
输入输出格式
输入格式
The first line contains one integer $ n $ ( $ 1<=n<=20 $ ).
The next line contains a string of length $ 2^{n} $ of zeros and ones, representing function $ f $ . Let $ b_{k}(x) $ the $ k $ -th bit in binary representation of $ x $ , $ i $ -th (0-based) digit of this string shows the return value of $ f(b_{1}(i),b_{2}(i),...,b_{n}(i)) $ .
It is guaranteed that $ f(1-x_{1},1-x_{2},...,1-x_{n})=1-f(x_{1},x_{2},...,x_{n}) $ for any values of $ x_{1},x_{2},ldots,x_{n} $ .
输出格式
Output one integer — answer to the problem.
输入输出样例
输入样例 #1
3
01010101
输出样例 #1
216
输入样例 #2
3
01101001
输出样例 #2
168
说明
In first sample, result is always fully determined by the first voter. In other words, $ f(x_{1},x_{2},x_{3})=x_{1} $ . Thus, any no matter what happens, there will be a candidate who won two rounds (more specifically, the candidate who is at the top of voter 1's preference list), so $ p=1 $ , and we print $ 1·6^{3}=216 $ .