排列组合之王

NC219178. 排列组合之王

描述

根据peko预言书说明，沉睡了数千年的魔王要复活了，为了能够应对魔王的随时复活，人类国度每年都会挑选出各色各样的有才能的人作为勇者，如超魔王级的侦探，超魔王级的大胃王等等，而你！正是超魔王级的排列组合之王。为了配合你的能力，国王给了你N个随从去任意使用，你可以从里面挑选任意个不同的随从组成小队，小队的战力等于所有随从战力值的异或和（异或是指把数字转成二进制后，同位上的数字相同则异或后该位为0，不相同则异或后该位为1，如1^2=3, 3^2=1, 7^9=14），假设你选择了4个随从，分别战力为1，2，2，4，则组成的小队战力=1^2^2^4=5。寻找最大的战力队伍对你来说实在是太简单了不值一提，你现在想要知道你用这些随从可以组成的所有不同种类的队伍的战力和，（两个队伍被视为不同代表两队里面的人数不同或者至少存在一个随从不一样）

输入描述

第一行输入一个N(1<=N<=200000);
第二行输入N个整数，第 i 个整数代表第 i 个随从的战力，0<=随从的战力<2000000;

输出描述

输出一个整数，代表所有不同种类的队伍的战力和，输出结果可能很大，请输出对1000000007取模后的值

示例1

输入:

3
1 2 3

输出:

说明:

你可以选择的随从的集合为{1}=1,｛2}=2 , {3}=3，｛1,2}=3, {2,3}=1, {1,3}=2, {1,2,3}=0，总和为12.

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 66ms, 内存消耗: 500K, 提交时间: 2021-03-08 16:16:30

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll mod=1e9+7;

ll ksm(ll a, ll b) {
  int res=1;
  while(b) {
    if(b&1) res=res*a%mod;
    a=a*a%mod;
    b>>=1;
  }
  return res;
}

int main() {
  ll n,m=0; cin>>n;
  for(int i=1;i<=n;i++) {
    ll x; cin>>x;
    m|=x;
  }
  printf("%lld",ksm(2,n-1)*m%mod);
}

C(clang11) 解法, 执行用时: 33ms, 内存消耗: 392K, 提交时间: 2021-03-07 23:04:57

#include<stdio.h>
#define ll long long
ll res,mod=1e9+7;
ll ksm(ll x,ll p)
{
	if(p<0) return 0;
	ll ans=1;
	while(p){
		if(p&1) ans=ans*x%mod;
		x=x*x%mod;
		p>>=1;
	}
	return ans;
}
int main()
{
	int n,m,k=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&m);
		k|=m;
	}
	res=k*ksm(2,n-1)%mod;
	printf("%lld",res);
}

Python3 解法, 执行用时: 137ms, 内存消耗: 20160K, 提交时间: 2022-05-15 13:16:10

n = int(input())
data = input().split(' ')
m = 0
for i in data:
    m = m|int(i)
t = 2**(n-1)
print(m*t%1000000007)