| Online Judge | Online Exercise | Online Teaching | Online Contests | Exercise Author |
|
F.A.Q Hand In Hand Online Acmers |
Best Coder beta VIP | STD Contests DIY | Web-DIY beta |
Mr.Panda and Survey
Time Limit: 60000/30000 MS (Java/Others) Memory Limit: 100000/100000 K (Java/Others)Total Submission(s): 105 Accepted Submission(s): 32
Problem Description
Mr.Panda did a survey among N candidates.
In the survey, each candidate was given a questionnaire which contains M yes/no questions. It is guaranteed that each question was answered with a ¡°Yes¡± or a ¡°No¡± by each candidate.
Mr.Panda likes variety. He considers a question as a good question if there are at least one candidate answered ¡°Yes¡± and at least one candidate answered ¡°No¡± for that question.
Now Mr.Panda has collected all the questionnaires. He wants to do some statistical analysis based on the survey result.
Because Mr.Panda is super lazy, he wants to randomly pick some of the questionnaires as a sample.
For each possible subset of questions (excluding empty set), Mr.Panda wants to know the probability that all questions in the subset are good questions, assuming that questionnaires in the sample are chosen randomly so that sample can be any subset (including full set and empty set) of questionnaires with equal probability.
Could you help Mr.Panda solve this problem?
To simplify the problem, you are only required to calculate ( $P_1 ¡¤ 2^N$ mod 1000000007) ¨’ ( $P_2 ¡¤ 2^N$ mod 1000000007) ¨’ ¡¤ ¡¤ ¡¤ ¨’ ( $P_{2^M-1}$¡¤ $2^N$ mod 1000000007)
where $P_i$ means the probability of i th subset of questions to be good questions. It is obvious that $P_i ¡¤ 2^N$ is always an integer.
¡°¨’¡± which is known as ¡°bitwise exclusive or¡± corresponds to operator ¡°^¡±in both C/C++ and Java.
¡° mod ¡± which is known as ¡°modulo¡± corresponds to operator ¡°%¡± in both C/C++ and Java.
In the survey, each candidate was given a questionnaire which contains M yes/no questions. It is guaranteed that each question was answered with a ¡°Yes¡± or a ¡°No¡± by each candidate.
Mr.Panda likes variety. He considers a question as a good question if there are at least one candidate answered ¡°Yes¡± and at least one candidate answered ¡°No¡± for that question.
Now Mr.Panda has collected all the questionnaires. He wants to do some statistical analysis based on the survey result.
Because Mr.Panda is super lazy, he wants to randomly pick some of the questionnaires as a sample.
For each possible subset of questions (excluding empty set), Mr.Panda wants to know the probability that all questions in the subset are good questions, assuming that questionnaires in the sample are chosen randomly so that sample can be any subset (including full set and empty set) of questionnaires with equal probability.
Could you help Mr.Panda solve this problem?
To simplify the problem, you are only required to calculate ( $P_1 ¡¤ 2^N$ mod 1000000007) ¨’ ( $P_2 ¡¤ 2^N$ mod 1000000007) ¨’ ¡¤ ¡¤ ¡¤ ¨’ ( $P_{2^M-1}$¡¤ $2^N$ mod 1000000007)
where $P_i$ means the probability of i th subset of questions to be good questions. It is obvious that $P_i ¡¤ 2^N$ is always an integer.
¡°¨’¡± which is known as ¡°bitwise exclusive or¡± corresponds to operator ¡°^¡±in both C/C++ and Java.
¡° mod ¡± which is known as ¡°modulo¡± corresponds to operator ¡°%¡± in both C/C++ and Java.
Input
The first line of the input gives the number of test cases, T.
T test cases follow. Each test case consists of two lines. The first line contains two integers N, the number of questionnaires, and M, the number of questions.
The second line contains N strings $Q_1, Q_2, ... , Q_N$ representing the answers in each questionnaire.
Each questionnaire $Q_i$ is given in the form of exact M charecters where each character can be either ¡°Y¡± standing for ¡°Yes¡± or ¡°N¡± standing for ¡°No¡±.
T test cases follow. Each test case consists of two lines. The first line contains two integers N, the number of questionnaires, and M, the number of questions.
The second line contains N strings $Q_1, Q_2, ... , Q_N$ representing the answers in each questionnaire.
Each questionnaire $Q_i$ is given in the form of exact M charecters where each character can be either ¡°Y¡± standing for ¡°Yes¡± or ¡°N¡± standing for ¡°No¡±.
Output
For each test case, output one line containing ¡°Case #x: y¡±, where x is the test case number(starting from 1) and y is the xor sum of the weighted probabilities.
$\bullet 1 ¡Ü T ¡Ü 20.$
$\bullet 1 ¡Ü N ¡Ü 10^5.$
$\bullet 1 ¡Ü M ¡Ü 15.$
limits
$\bullet 1 ¡Ü T ¡Ü 20.$
$\bullet 1 ¡Ü N ¡Ü 10^5.$
$\bullet 1 ¡Ü M ¡Ü 15.$
Sample Input
2 2 2 NY YN 4 2 NN NY YN YY
Sample Output
Case #1: 1 Case #2: 7
Hint
Source
| Home | Top |
Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-11-22 18:31:30, Gzip enabled |
Administration |