Codeforces Round #714 AND Sequences - Math

Solution:

First notice this property: $x\ \&\ y\leq{x}$.

Let's see if $i=1$, then we get $a_1=a_2\ \&\ a_3\ \&\ ... \ \&\ a_n$。If $i=2$, then $a_1\ \&\ a_2=a_3\ \&\ a_4\ \&\ ... \ \&\ a_n$。

Now we have $a_1\geq{a_1\ \&\ a_2}=a_3\ \&\ a_4\ \&\ ... \ \&\ a_n\geq{a_3\ \&\ a_4\ \&\ ... \ \&\ a_n}=a_1$

So it's very clear to know that: $a_1\ \&\ a_2=a_3\ \&\ a_4\ \&\ ... \ \&\ a_n=a_1$。

So for any of $i$, $a_1\ \&\ a_2\ \&\ ...\ \&\ a_i=a_{i+1}\ \&\ a_{i+2}\ \&\ ...\ \&\ a_n=a_1$. The most special one is $a_n$, when $i=n-1$, we have $a_n=a_1$。

So we only need to get $\&$ sum to all the numbers (Let's say $sum=\&_{i=1}^{n}a_i$). And the number of $a_i$ equals to $sum$ is $count$.

Then we only need arrange two numbers which equal to $sum$ into the first and last element. And do full arrangement for the remains. So the result is: $A_{count}^2 * A_{n-2}^(n-2)$.

It should be noted that don't calculate $A_{n-2}^(n-2)$ by brute force every time. Save the results of preprocessing in advance.

Code:

Submission #112713653 - Codeforces
Codeforces. Programming competitions and contests, programming community
Show Comments
DigitalOcean Referral Badge