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)$不要每次都暴力求。提前把预处理的结果存起来。

代码:

Submission #112713653 - Codeforces
Codeforces. Programming competitions and contests, programming community