NC236627. 生日
描述
输入描述
输入第一行包含一个正整数 ,表示总人数。
接下来包含 个数字 ,表示每一个人的属性值。
输出描述
输出一行一个整数表示答案对 取模后的结果。
示例1
输入:
3 1 3 4
输出:
20
说明:
共有三个人,第 个人的生日是第 天或第 天。即第一个人的生日是第 0/1 天,第二个人的生日是第 1/2 天,第三个人的生日是第 1/3 天示例2
输入:
4 1 2 3 4
输出:
36
说明:
[1,2,1,2] 表示第一个人和第三个人在第一天过生日,产生的快乐值为 ;第二个和第四个人都在第二天过生日,产生的快乐值为 ,所以这一种方案共产生快乐值为 6 + 2 = 8。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; }