n=1时，输出a[1]，初学者也能骗到20分。

n≤20时，我们可以暴力枚举选不选这个a[i]，时间复杂度O(2^n)，40分。

接下来我们对于第二问考虑DP，DP[i][j]表示以a[i]为最后一个数（且选了a[i]），第j个二进制位上为1的情况数。

初始状态DP[1][j]=a[i]的第j位。若a[i]的第j位为0，DP[i][j]=Σk≤i-1 DP[k][j]。若a[i]的第j位为1，DP[i][j]=2^i-Σk≤i-1 DP[k][j]-1

时间复杂度O(n^2)。

对于第二问考虑改变状态的含义。DP[i][j]重新定义为看到第i位（不一定选a[i]），第j个二进制位上为1的情况数。

初始状态同样。若a[i]的第j位为0，DP[i][j]=DP[i-1][j]×2。若a[i]的第j位为1，DP[i][j]=2^(i-1)。

对于第一问，可以用类似的DP解决。当然，你也会发现DP[i][j]仅依赖于一个量：DP[i-1][j]，所以我们可以在空间复杂度为O(log a[i])甚至O(1)来解决这个问题。

最终时间复杂度O(nlog a[i]+nlog a[i])，空间复杂度O(nlog a[i]+nlog a[i])。（尝试在时间复杂度O(nlog a[i]+log a[i])空间复杂度O(1)内解决问题！）

Tags:bitmasks,dp,math Difficulty:1700