法力无边

NC238811. 法力无边

描述

牛世界有 $n$ 个大魔法师，第 $i$ 个魔法师的法力值为 $a_i$ 。
牛牛把他们按照编号排成了一队，他定义第 $l$ 名法师到第 $r$ 名法师的共同法力值 $M_{l,r}=a_l \odot a_{l+1} \odot ... \odot a_r$ ，特别地，当 $l=r$ 时，规定 $M_{l,r}=a_l$ 。
其中 $\odot$ 表示按位同或操作。其按位真值表如下：

$a$	$b$	$a\odot b$
0	0	1
0	1	0
1	0	0
1	1	1

注意：按位同或的操作需要指定位数 $m$ ，不足 $m$ 位的数在最高位补 $0$ ，数据保证 $a_i$ 的位数不会超过 $m$ 。
例如，当 $m=4$ 时， $12=(1100)_2$ ， $9=(1001)_2$ ，则 $12\odot 9=(1100)_2\odot(1001)_2=(1010)_2=10$ 。
而当 $m=5$ 时， $12=(01100)_2$ ， $9=(01001)_2$ ，则 $12\odot 9=(01100)_2\odot(01001)_2=(11010)_2=26$ 。
牛牛想知道 $\sum\limits_{i=1}^n{\sum\limits_{j=i}^n{M_{i,j}}}$ 的值是多少。

输入描述

输入共两行。
第一行  个整数  ，含义如题。
第二行  个自然数，第  个数为  ，含义如题。

输出描述

输出共一行，为所求值。

示例1

输入:

2 1
1 1

输出:

说明:

指定位数为 $1$ 时， $1\odot 1=(1)_2\odot(1)_2=(1)_2=1$ ，故 $M_{1,2}=1$

示例2

输入:

2 2
1 1

输出:

说明:

指定位数为 $2$ 时， $1\odot 1=(01)_2\odot(01)_2=(11)_2=3$ ，故 $M_{1,2}=3$

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

C++(g++ 7.5.0) 解法, 执行用时: 31ms, 内存消耗: 956K, 提交时间: 2022-10-05 21:27:52

                  #include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;

ll n,m,x,ans;
ll sum[1000020][2];

int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&x);
		for(int j=0;j<m;j++)
		{
			if((x>>j)&1)
				sum[j][1]++;
			else
			{
				swap(sum[j][1],sum[j][0]);
				sum[j][0]++;
			}
			ans+=sum[j][1]*(1<<j); 
		}
	}
	printf("%lld",ans);
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 34ms, 内存消耗: 420K, 提交时间: 2022-10-03 11:18:39

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,x,ans,sum[100009][2];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&x);
		for(int j=0;j<m;j++)
		{
			if((x>>j)&1)  sum[j][1]++;
			else
			{
				swap(sum[j][1],sum[j][0]);
				sum[j][0]++;
			}
			ans+=sum[j][1]*(1<<j);
		}
	}
	cout<<ans;
	return 0;
}