列表

详情


NC236627. 生日

描述

共有 n 个人,分别编号为 ,每一个人都有一个属性值,其中第 i 个人的属性值为 a_i。如果有两个编号为 i,j 的人在同一天过生日,则他们两个人会产生 的快乐值,其中 是位运算中的异或运算符。同理,若三个人或更多人在同一天过生日,则这些人产生的快乐值是所有在这一天过生日的人的异或值。若某一个人单独过生日,则不产生任何快乐值。
为了使得公历生日不同的鸡尾酒和玥玥也可以在同一天过生日,鸡尾酒规定每个人有两个生日,一个公历生日,一个农历生日,且可以在这两天中任选一天进行“过生日”活动。现在我们假设第 i 个人的公历生日为第 i 天,农历生日为第 天(其中 表示对 x 向下取整)。那么这 n 个人会有很多种不同的过生日方案,现在鸡尾酒想问你所有过生日方案的所有快乐值之和是多少?
两种过生日方案不同当且仅当存在某一个人 i 在两种方案中选择了不同的一天进行过生日。
由于答案可能很大,请输出答案对 取模后的结果。

输入描述

输入第一行包含一个正整数 ,表示总人数。

接下来包含 n 个数字 ,表示每一个人的属性值。

输出描述

输出一行一个整数表示答案对  取模后的结果。

示例1

输入:

3
1 3 4

输出:

20

说明:

共有三个人,第 i 个人的生日是第 i 天或第 \lfloor \frac{i}{2} \rfloor 天。即第一个人的生日是第 0/1 天,第二个人的生日是第 1/2 天,第三个人的生日是第 1/3 天
用 [1,2,3] 表示第一个人在第一天过生日,第二个人在第二天过生日,第三个人在第三天过生日。此时没有任何两个人一起过生日,所以快乐值为 0。
[1,1,1] 表示三个人都在第一天过生日,此时产生的快乐值为 6(1、3、4 三个数字的异或值)
[0,1,1] 快乐值为 7。
[1,1,3] 快乐值为 2。
[1,2,1] 快乐值为 5。
其余过生日方案的快乐值都为 0,因为这些方案中没有任何两个人在同一天过生日。
求和得到 20。

示例2

输入:

4
1 2 3 4

输出:

36

说明:

[1,2,1,2] 表示第一个人和第三个人在第一天过生日,产生的快乐值为 1 \oplus 3=2;第二个和第四个人都在第二天过生日,产生的快乐值为 2 \oplus 4=6,所以这一种方案共产生快乐值为 6 + 2 = 8。
[1,2,3,2]、[0,2,3,2]、[0,2,1,2] 这三种方案都只有第二个和第四个人一起过生日,产生快乐值都为 6,三种方案快乐值共计 6*3=18。
[1,2,1,4] 产生快乐值为 2。
[1,1,1,4]、[1,1,1,2] 这两种方案是前三个人一起过生日,但是 1 \oplus 2 \oplus 3 = 0,所以这三种方案产生的快乐值为 0。
[0,1,1,4]、[0,1,1,2] 的快乐值均为 1,两种方案共计 2*1=2。
[1,1,3,4]、[1,1,3,2] 的快乐值均为 3,两种方案共计 3*2=6。
其余方案的快乐值为 0,以上所有方案快乐值之和为 8+18+2+2+6=36

原站题解

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

C++(g++ 7.5.0) 解法, 执行用时: 40ms, 内存消耗: 1976K, 提交时间: 2023-05-31 22:35:36

#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=1e9+7,N=1e5+10;
ll a[N],n,p[N];
ll ans=0;
int main()
{
    cin>>n;
    p[0]=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        p[i]=(2ll*p[i-1]%mod)%mod;
    }
    for(int i=1;i<=n;i++){
        if(i*2>n) break;
        else if(i*2+1>n){
            ans=(ans+p[n-2]*(a[i]^a[i*2])%mod)%mod;
        }
        else{
            ans=(ans+p[n-3]*((a[i]^a[i*2])+(a[i]^a[i*2+1])+(a[i*2]^a[i*2+1])+(a[i]^a[i*2]^a[i*2+1])))%mod;
        }
    }
    cout<<ans;
}

C 解法, 执行用时: 19ms, 内存消耗: 1072K, 提交时间: 2022-05-21 22:30:38

#include <stdio.h>
#define M 1000000007

int main() {
    int n;
    long long s[100005];
    long long sum=0;
    long long pow=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&s[i]);
    for(int i=1;2*i<n;i++)
        sum=sum+(s[i]^s[i*2])+(s[i]^s[2*i+1])+(s[i*2]^s[i*2+1])+(s[i]^s[i*2]^s[i*2+1]);
    for(int i=1;i<=n-3;i++)
        pow=pow*2%M;
    sum=sum%M;
    sum=sum*pow%M;
    if(n%2==0)
        sum=(sum+(s[n/2]^s[n])*pow*2)%M;
    printf("%lld",sum);
}

C++(clang++ 11.0.1) 解法, 执行用时: 37ms, 内存消耗: 1176K, 提交时间: 2023-01-05 15:06:42

#include<iostream>
using namespace std;
int a[100005];
int f[100005];
const int m=1e9+7;
int main(){
	int n;
	cin>>n;
	f[0]=1;
	long long ans=0;
	for(int i=1;i<=n;i++)f[i]=2*f[i-1]%m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++){
		if(2*i+1<=n){
			ans=ans+f[n-3]*((a[i]^a[2*i])+(a[i]^a[2*i+1])+(a[2*i]^a[2*i+1])+(a[i]^a[2*i]^a[2*i+1]));
			ans=ans%m;
		}else{
			if(2*i<=n)ans=ans+f[n-2]*(a[i]^a[2*i]);
			ans=ans%m;
		}

	}
	cout<<ans<<endl;
	return 0;
}

上一题