====== Xor ======
به شما ‎$n$‎ عدد ‎$a_1$‎ تا ‎$a_n$‎ داده شده است، شما باید زیرمجموعه ای از آن را بیابید که اعداد هیچ 
زیرمجموعه‌ی ناتهی آن برابر با ‎0‎ نشود و جمع اعداد آن بیشینه باشد.

===== ورودی =====

در سطر اول ورودی عدد ‎$1 \leq n \leq 100$‎ آمده است، در سطر بعدی ‎$n$‎ عدد ‎$a_1$‎ تا ‎$a_n$‎ آمده است.

===== خروجی=====

در تنها سطر خروجی اعداد زیر مجموعه را به ترتیب صعودی چاپ نمایید. در صورتی که چند جواب برای سؤال وجود دارد، یکی از آن‌ها را چاپ نمایید.
===== محدودیت‌ها =====


  * محدودیت زمان: ۲ ثانیه
  * محدودیت حافظه: ۲۵۶ مگابایت

‎‎
===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|‎3 \\ ‎1 2 3 |‎2 3 |

</WRAP>
<پاسخ>
ابتدا توجه کنید که اگر یک مجموعه از اعداد هیچ زیر مجموعه‌ی ناتهی نداشته باشد که XOR اعضای آن صفر شود، معادل این است که هیچ یک از اعضای آن را نتوان برحسب ‎XOR‎ بقیه‌ی اعضا نوشت. چون اگر یک عضو را بتوان برحسب بقیه‌ی اعضا نوشت XOR‎ این عضو با بقیه‌ی اعضا صفر می‌شود. اگر هم ‎XOR‎ یک زیر مجموعه صفر شد ‎XOR‎ هر یک از اعضا باید برابر با XOR‎ بقیه شود‎.‎

برای حل این مسئله از الگریتم حریصانه استفاده می‌کنیم. یعنی اعداد را ابتدا به ترتیب نزولی مرتب می‌کنیم. سپس به ترتیب اعداد را پیمایش می‌کنیم و هر عددی که اجتماعش با اعداد انتخاب شده‌ی قبلی تولید زیرمجموعه‌ای نمی‌کرد که XOR‎ آن صفر شود را انتخاب می‌کنیم. فرض کنید در این الگریتم اعداد ‎$x_1$‎ تا  ‎$x_k$‎انتخاب شده باشند. (که اینها به ترتیب نزولی هستند) اگر این مجموعه تشکیل یک جواب بهینه بدهند که مسئله حل است. در غیر این صورت یک جواب بهینه به صورت ‎$y_1$‎ تا ‎$y_k'$‎ در نظر بگیرید. ‎$i$‎ را کوچک‌ترین اندیس بگیرید که ‎$x_i \neq y_i$‎ است. مطمئنا هیچ یک از ‎$y_1$‎ تا ‎$y_k'$‎ ها نباید مساوی با ‎$x_i$‎ باشند و چون ‎$y_1$‎ تا ‎$y_k'$‎ تشکیل یک جواب بهینه می‌دهند پس اجتماع آنها با ‎$x_i$‎ یک زیرمجموعه دارد که ‎XOR‎ اعضایش صفر هستند. ‎$x_i$‎ باید عضو این زیر‌مجوعه باشد. پس ‎$x_i$‎ را می‌توان برحسب XOR $y_1$‎ تا ‎$y_{k'}$‎ نوشت. فرض کنید این اعضا ‎$z_1$‎ تا  ‎$z_m$‎ باشند. پس داریم‎:‎
‎$$ x_i=z_1\oplus \cdots \oplus z_m $$‎
همه‌ی ‎$z_1$‎ تا  ‎$z_m$‎ ‌ها نمی‌توانند از ‎$x_i$‎ بزرگ‌تر باشند چون با توجه به اینکه اعضای بزرگ‌تر از ‎$x_i$‎ در ‎$x_1$‎ تا  ‎$x_k$‎ با ‎$y_1$‎ تا ‎$y_k'$‎ برابرند در این صورت زیر مجموعه‌ی ‎$x_1$‎ تا  ‎$x_i-1$‎ می‌شوند. پس ‎$z_j$‎ موجود است که ‎$z_j<x_i$‎حالا اگر در مجموعه‌ی ‎$y_1$‎ تا ‎$y_k'$‎ به جای ‎$z_j$‎ ،$x_i$‎ را بگذاریم ادعا می‌کنیم که هنوز زیرمجموعه‌ای وجود ندارد که ‎XOR‎ آن صفر شود‎.‎

فرض کنید این اتفاق بیافتد. در این صورت این زیرمجموعه باید شامل ‎$x_i$‎ باشد پس ‎$x_i$‎ را می‌توان برحسب اعضا‌ی ‎$y_1$‎ تا ‎$y_k'$‎ نوشت. از طرفی ‎$x_i$‎ برابر با ‎XOR $z_1$‎ تا ‎$z_m$‎ می‌شد. حالا اگر ‎XOR‎ این دو زیرمجموعه را برابر قرار دهیم یک زیرمجموعه به‌دست می‌آید که ‎XOR آن صفراست(با توجه به اینکه ‎$z_j$‎ در یک طرف آمده و در طرف دیگری نیامده است) ‎XOR‎ آن صفر شود‎.‎

پس درستی الگریتم ثابت شد. در مورد زمان اجرای این الگریتم کافی است نشان دهیم بررسی کردن اینکه یک عدد را می‌توان برحسب XOR‎ اعضای یک مجموعه نوشت در زمان خوب امکان‌پذیر است. متغییر دودویی ‎$s_i$‎را این طور تعریف می‌کنیم که آیاازعضو ‎$i$‎‌ام این مجموعه استفاده می‌کنیم یا نه. در این صورت به ازای هر بیت از عددمان به یک معادله می رسیم. اگر فرض کنیم بیت مورد نظر در عدد ‎$j$‎ ام ‎$b_j$‎ باشد. و در عدد اصلی مان ‎$h$‎ باشد آنگاه باید داشته باشیم‎:‎
‎$$ s_1 \times b_1+\cdots+s_r \times b_r=h $$
پس ما به یک دستگاه معادلات می رسیم که باید آنرا حل کنیم و ببینیم آیا جوابی دارد یا نه.(این دستگاه در مبنای ‎$2$‎ است و باید ضرب و جمع این مبنا را در نظر گرفت) این کار هم در زمان ‎$O(r^2 n)$‎ امکان‌پذیر است. که ‎$r$‎  تعداد بیت‌ها است‎.‎
پس چون ما به ازای هر عدد یک دستگاه معادلات حل می‌کنیم در کل زمان اجرا ‎$O(r^2 \times n^2)$‎ است. که با توجه به اینکه ‎$n<100$‎ این الگوریتم بهینه است.
</پاسخ>

  * [[سوال ۵۲|سوال بعد]]
  * [[سوال ۵۰|سوال قبل]]