We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
for(i=0;i<n;i++)
{
cin>>v[i];
m[v[i]]++;
}
dp[0][0]=1;
int flag=1;
for(i=0;i<n;i++)
{
for(j=0;j<8192;j++)
{
//i.e the element occurs even times.., the result will the same as the including just the previous elements.
ll excluded = (((m[v[i]]/2)+1)*(dp[flag^1][j]))%mod;
//i.e the element occurs odd times.., the result will number of ways to find the sum (j^a[i]) with the //help of i-1 elements... since a^b=j(wanted)..to find b a^b^a=j^a--> b=j^a
ll included = (((m[v[i]]+1)/2)*(dp[flag^1][j^v[i]]))%mod;
dp[flag][j]=(included+excluded)%mod;
//cout<<dp[flag][j]<<" ";
}
flag=flag^1;
}
ll ans=0;
for(i=0;i<8192;i++)
{
//cout<<dp[flag][i]<<" ";
if(prime[i])
{
//cout<<dp[i]<<" ";
ans=(ans+dp[flag^1][i])%mod;
}
}
cout<<ans;
}
int main() {
// your code goes here
ll t;
cin>>t;
sieve();
while(t--)
{
solve();
}
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Prime XOR
You are viewing a single comment's thread. Return to all comments →
what is wrong inthis code, i think everything is implemented according to the editorial..but still i am getting a wrong ans..plz help.. Thanks..
include
using namespace std;
define ll long long
define mod 1000000007
bool prime[8193]; void sieve() { ll i,j; memset(prime,true,sizeof(prime)); prime[0]=false; prime[1]=false; for(i=2;i*i<=8192;i++) { if(prime[i]) { for(j=2*i;j<=8192;j+=i) prime[j]=false; } } } void solve() { ll n,i,j; cin>>n; vectorv(n); int m[5000]={0}; int dp[2][8192]={0};
} int main() { // your code goes here ll t; cin>>t; sieve(); while(t--) { solve(); } }