(2022 Niu Ke Duo School IV) N-Particle Arts (Thinking)

Title:

Sample input:

51 2 3 4 5

Sample output:

54/5

Title:

n particles, each with an energy ai.For a random collision of two pairs, if the energies of the two examples are a and b, respectively, then the energies of the two particles in one collision become a&b, a|b respectively.Find the variance of all particle energies after they have stabilized.

We analyze the results of the collision of two particles and we can find that for the binary bits of a and b, if the i-th bit is both 1, then the i-th bit of the energy of the two particles formed after the collision is both 1,If the i-th bit is both 0, then the i-th bit of the energy of the two particles formed after the collision is 0. If the i-th bit of the a-particle and b-particle energy before the collision is 1 and the other is 0, then the collision is formed.The i-th bit of the particle is also a 1 and a 0, but the 1 is on the particle after the OR operation, so it is easy to find that each collision will make the energy of a particle larger (or may remain unchanged), and the binary bit after the collisionThe number of 1s remains unchanged, but it is possible to transfer from 1 particle to another particle. Due to countless collisions, the 1s on the binary must be concentrated as much as possible on a few, The final stable state is that for any i and j, there are (ai|aj,ai&aj)=(ai,aj) or (ai|aj,ai&aj)=(aj,ai) .So we only need to count the number of occurrences of 1 in each of the n numbers given at the beginning.Assign n numbers, try to assign 1 to a number every time, and finally ask for the expectation.

One point to note is that because the number is relatively large, it may explode long long, so it is recommended to use __int128 for calculation directly.

Here is the code:

#include#include#include#include#include