Codeforces 482C Game with Strings

제목 설명
You play the game with your friend. The description of this game is listed below.
Your friend creates n distinct strings of the same length m and tells you all the strings. Then he randomly chooses one of them. He chooses strings equiprobably, i.e. the probability of choosing each of the n strings equals . You want to guess which string was chosen by your friend.
In order to guess what string your friend has chosen, you are allowed to ask him questions. Each question has the following form: «What character stands on position pos in the string you have chosen?» A string is considered guessed when the answers to the given questions uniquely identify the string. After the string is guessed, you stop asking questions.
You do not have a particular strategy, so as each question you equiprobably ask about a position that hasn’t been yet mentioned. Your task is to determine the expected number of questions needed to guess the string chosen by your friend.
Input The first line contains a single integer n (1 ≤ n ≤ 50) — the number of strings your friend came up with.
The next n lines contain the strings that your friend has created. It is guaranteed that all the strings are distinct and only consist of large and small English letters. Besides, the lengths of all strings are the same and are between 1 to 20 inclusive.
Output Print the single number — the expected value. Your answer will be considered correct if its absolute or relative error doesn’t exceed 10 - 9.
제목의 뜻
n개의 문자열을 드리겠습니다. 그 중 하나는 정답입니다. i번째 위치의 알파벳이 무엇인지 물어볼 때마다 마지막으로 정답을 맞히는 기대의 걸음수를 물어볼 수 있습니다.
사고의 방향
d[i] (m위 2진법으로 j 자모가 맞혔는지 여부를 표시함) 은 맞힌 문자의 위치가 i인 상태에서 맞출 수 없는 문자열을 나타낸다. (N위 2진법으로 k번째 문자열이 맞혔는지 여부를 표시한다)
분명히 다음과 같다.
d[mask ^ (1 << i)] |= d[mask];
이 식에 근거하여 d수 그룹을 구할 수 있다
그 다음은 계수입니다.
모브스 단계에서 새로 맞힌 문자열의 개수를 구하고 싶다면 현재 상태의 mask를 열거한 다음 마지막으로 맞힌 위치 i를 열거하십시오. 그러면:
res = d[mask] ^ d[mask ^ (1 << i)];
마지막 요구 사항:
매 걸음걸이 i, 답안에 대한 공헌은:
totalGuessed[i]/C(m,i)/n
정부측 문제풀이.
Let’s handle all string pairs and calculate the mask mask, which will have 1-bits only in positions in which that strings have the same characters. In other words, we could not distinguish these strings using positions with submask of mask mask, then we must add in d[mask] 1-bits in positions i и j. This way in d[mask] we store mask of strings, which we could not distinguish using only positions given in mask mask. Using information described above, we can easily calculate this dynamics. Now, when we have array d calculated, it is not hard to calculate the answer. Let’s handle some mask mask. Now we should try to make one more question in position pos, which is equal to adding one more 1-bit in mask in position pos. After that we may guess some strings, they are 1-bits in mask s = d[mask] ^ d[mask | (1 << pos)]. Then you have to calculate number of bits in s quickly and update the answer.
코드

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int N = 20;
const int M = 150;
int n;
char s[M][N + 10];

typedef long long li;
typedef long double ld;

li d[(1 << N)];

inline bool has(li mask, int pos) {
    return (mask >> pos) & 1;
}

ld prob[N + 10];
ld totalGuessed[N + 10];

int main() {
    int n;
    scanf("%d", &n);

    for(int i = 0; i < n; i++) {

        scanf("%s", s[i]);
    }

  int m = strlen(s[0]);

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if (i == j) continue;

            int same = 0;

            for(int k = 0; k < m; k++) {
                if (s[i][k] == s[j][k]) same |= (1 << k);
            }

            d[same] |= (1LL << i);
        }
    }

    for(int mask = (1 << m) - 1; mask; mask--) {
        for(int i = 0; i < m; i++) {
            if (has(mask, i)) {
                d[mask ^ (1 << i)] |= d[mask];
            }   
        }
    }

    long double ans = 0;

    for(int mask = 0; mask < (1 << m); mask++) {
        int moves = __builtin_popcount(mask) + 1;
        for(int i = 0; i < m; i++) {
            if (!has(mask, i)) {
                li res = d[mask] ^ d[mask ^ (1 << i)];
                if (res == 0) continue;

                int cntGuessed = __builtin_popcountll(res);

                totalGuessed[moves] += cntGuessed;
            }
        }
    }

    for(int i = 1; i <= m; i++) {
        ld val = totalGuessed[i] * i;

        for(int j = 0; j < i - 1; j++) 
            val *= ld(i - 1 - j) / ld(m - j);

        ans += val / ld(m - i + 1);
    }

    ans /= ld(n);
    cerr << clock() << endl;
    cout << fixed << setprecision(15) << ans << endl;
}