Существует огромное сомнение в отношении проблемы, которая говорит о том, что нам будет дан массив размером n<10^5 и каждый 0<=a[i]<10^9.
. Нам нужно сосчитать так, чтобы n элементов сказали b[i], напримерчто каждый 0<=b[i]<=a[i] и их xor равен xor a[0]^a[1]..^a[n-1].Поэтому я написал код, который дает правильный ответ для небольших входных данных, и я определил состояния dp, чтобы теперь я мог запомнить его, но когда я увидел редакцию, к своему удивлению, решение было основано на побитовом вычислении и затем подсчете.
Итак, вот мои сомнения, даже если мы можем сделать запоминание, почему мы должны делать это по крупицам?Разве мы не можем использовать побитовые операторы и получить решение?
PS: ссылка на редакцию </p>
<pre><code>#include <bits/stdc++.h>
using namespace std;
int ans(int *a,int n,int level,int cur,int xor_val)
{
if(level==n)
{
if(cur==xor_val)
{
return 1;
}
return 0;
}
int cnt=0;
for(int i=0;i<=a[level];i++)
{
if(level==0)
{
cur=i;
cnt+=ans(a,n,level+1,cur,xor_val);
}
else
{
cnt+=ans(a,n,level+1,cur^i,xor_val);
}
}
return cnt;
}
int main()
{
int *a,n,t;
cin>>t;
while(t--)
{
cin>>n;
a=new int[n];
int xor_val;
for(int i=0;i<n;i++)
{
cin>>a[i];
if(i==0)
xor_val=a[i];
else
xor_val^=a[i];
}
int cur;
cout<<ans(a,n,0,cur,xor_val)<<"\n";
}
return 0;
}