In this HackerEarth Bob and Beauty of the Array problem solution, Bob is having an array of A of N elements. Bob wants to determine the beauty of the array and the beauty of the array is defined as:-
Determine Bitwise OR of maximum and minimum elements of every subset of size greater than or equal to 2 and add them. As the answer can be quite large, you have to report it by taking modulo with 1000000007.
HackerEarth Bob and Beauty of the Array problem solution.
#include<bits/stdc++.h>
using namespace std ;
#define pb push_back
#define mp make_pair
#define infile() freopen("in04.txt","r",stdin);
#define output() freopen("out04.txt","w",stdout);
#define ll long long
#define sc(t); scanf("%d",&t);
#define scl(t); scanf("%lld",&t);
#define sc2(n,m); scanf("%d%d",&n,&m);
#define scl2(n,m); scanf("%lld%lld",&n,&m);
#define debug(); printf("tushar\n");
#define N 200005
#define mod 1000000007
#define printi(n) printf("%d",n);
#define inf ((1<<29)-1)
#define linf ((1LL<<60)-1)
const double eps = 1e-9;
set < ll > s ;
set < int > si ;
set < ll > :: iterator it ;
vector < ll > v ;
vector < int > vi ;
int n,m,q,k ;
int a[N] ;
ll p2[N] = {0} ;
ll ans = 0LL ;
int hs[1002] = {0} ;
ll power(ll x, ll y)
{
ll res = 1;
x = x % mod;
while (y > 0)
{
if (y & 1)
res = (res*x) % mod;
y = y>>1;
x = (x*x) % mod;
}
return res;
}
void func(int c1 , int cc , int con , ll val )
{
int x = con;
int y = con + cc - 1 ;
ll tmp ;
if(x == 0)
tmp = p2[y] ;
else
tmp = (p2[y]-p2[x-1]+mod)%mod ;
tmp = (ll)(tmp*p2[c1-1])%mod ;
tmp = (ll)(tmp*val)%mod ;
ans = (ll)(ans + tmp)%mod ;
return ;
}
int main()
{
infile() ;
output() ;
int i , j , t ;
p2[0]=1LL;
for(i=1;i<=200000;i++)
{
p2[i]=p2[i-1]*2LL;
p2[i]%=mod ;
}
for(i=1;i<=200000;i++)
{
p2[i]=p2[i]+p2[i-1];
p2[i]%=mod ;
}
sc(n) ;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]) ;
hs[a[i]]++ ;
}
for(ll i=1LL;i<=1000;i++)
{
if(hs[i])
{
int cntuptonow = 0 ;
// to get the contribution of all subsets having one unique element only.
if(hs[i] >= 2)
{
ll tmp = power(2,hs[i]) ;
tmp = (tmp - (hs[i]+1) + mod)%mod ;
ans = (ll)(ans + tmp*i)%mod ;
ans%=mod ;
}
for(j=i-1;j>=1;j--)
{
if(hs[j])
{
func(hs[i],hs[j],cntuptonow,(i|j)) ;
cntuptonow = cntuptonow + hs[j] ;
}
//printf("i = %d j = %d ans = %lld\n",i,j,ans) ;
}
}
}
printf("%lld\n",ans) ;
return 0 ;
}
Second solution
#include <bits/stdc++.h>
using namespace std;
#include<limits>
#define ll long long
#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define debugdec int deb=1;
#define debug() cout<<"real_flash>> "<<(deb++)
#define pb push_back
#define mk make_pair
#define MEM(a,b) memset(a,(b),sizeof(a))
#define TEST int test; cin >> test;while(test--)
#define si(x) scanf("%d",&x)
#define author real_flash
#define rep(p,q,r) for(int p=q;p<r;p++)
#define repr(p,q,r) for(int p=q;p>=r;p--)
#define repit(it, a) for(__typeof(a.begin()) it = a.begin();it != a.end(); ++it)
#define si2(x,y) scanf("%d %d",&x,&y)
#define si3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define FIND(x,y) x.find(y)==x.end()
#define sl(x) scanf("%lld",&x)
#define prl(x) printf("%lld\n",x)
#define ff first
#define ss second
#define BE(a) a.begin(), a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define INF 111111111111111LL
#define mo 1000000007
#define PI 3.141592653589793
typedef pair<int, int > pii;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<ll, ll> pll;
template<class T> inline T gcd(T a, T b) { while(b) b ^= a ^= b ^= a %= b; return a;}
//std::cout << std::setprecision(3) << std::fixed;
int MAX=numeric_limits<int>::max();
const int N=1e6+5;
//ios_base::sync_with_stdio(0);cin.tie(0);
int n,B=15;
ll a[N],po2[N],sp2[N],ans;
ll dig[20];
int mark[20];
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
//freopen("D:/progs/output.txt", "w", stdout);
#endif
po2[0]=1;
rep(i,1,N)
po2[i]=(po2[i-1]*2LL)%mo;
sp2[0]=1;
rep(i,1,N)
sp2[i]=(sp2[i-1]+po2[i])%mo;
si(n);
assert(n>=1&&n<=2e5);
rep(i,0,n)
{
sl(a[i]);
assert(a[i]>=1&&a[i]<=1000);
}
sort(a,a+n);
rep(i,0,B)
{
if((a[0]>>i)&1)
{
dig[i]=1;
}
}
rep(i,1,n)
{
MEM(mark,0);
rep(j,0,B)
{
if((a[i]>>j)&1)
{
ans=(ans+po2[j]*sp2[i-1])%mo;
mark[j]=1;
}
else
{
ans=(ans+po2[j]*dig[j])%mo;
}
}
rep(j,0,B)
{
dig[j]=(dig[j]*2LL)%mo;
}
rep(j,0,B)
if(mark[j]==1)
dig[j]=(dig[j]+1LL)%mo;
}
cout<<ans<<"\n";
}
0 Comments