Codeforces Round #714 AND Sequences 数学

题意：

给你一个长度为$n$的数组$a$。如果对于任意的$1\leq{i}\leq{n-1}$有$a_1\ \&\ a_2\ \&\ ...\ \&\ a_i=a_{i+1}\ \&\ a_{i+2}\ \&\ ...\ \&\ a_n$，那么称这个数组是美的。问在$a$的所有排列中，美的排列有多少种？

题解：

首先注意到这样的性质：$x\ \&\ y\leq{x}$。

考察$i=1$的情况，$a_1=a_2\ \&\ a_3\ \&\ ... \ \&\ a_n$。再考察$i=2$的情况可知，$a_1\ \&\ a_2=a_3\ \&\ a_4\ \&\ ... \ \&\ a_n$。且有$a_1\geq{a_1\ \&\ a_2}=a_3\ \&\ a_4\ \&\ ... \ \&\ a_n\geq{a_3\ \&\ a_4\ \&\ ... \ \&\ a_n}=a_1$

于是立刻可知$a_1\ \&\ a_2=a_3\ \&\ a_4\ \&\ ... \ \&\ a_n=a_1$。

于是立刻可知，对于任意的$i$，$a_1\ \&\ a_2\ \&\ ...\ \&\ a_i=a_{i+1}\ \&\ a_{i+2}\ \&\ ...\ \&\ a_n=a_1$。其中最特殊的是$a_n$，当$i=n-1$有$a_n=a_1$。

于是我们只需要把所有数字都$\&$起来（假设结果为$sum$），我们只需找出$a$中等于$sum$的个数（假设有$count$个），把这些数排列到一头一尾，剩下的随便排列就行。也就是$A_{count}^2 * A_{n-2}^(n-2)$。

需要注意的是，$A_{n-2}^(n-2)$不要每次都暴力求。提前把预处理的结果存起来。

代码：