رمزنگاری

موضوع امنیت در اینترنت یکی از مهم‌ترین موضوع‌های مورد مطالعه‌ی سال‌های اخیر است. یکی از روش‌های امنیت، رمزنگاری داده‌ها است. الگوریتم «پفکی» یکی از پرکاربردترین روش‌ها برای رمزنگاری است. این الگوریتم برای رمزنگاری داده‌ها، از دو دنباله‌ی $a_0,a_1,\cdots,a_{n-1}$ و $b_0,b_1,\cdots,b_{n-1}$ استفاده می‌کند. میزان امنیت الگوریتم «پفکی» با استفاده از روش زیر قابل محاسبه است:

«جدولی با $n$ سطر و $32 \times m$ ستون در نظر بگیرید که در خانه‌ی $(i,j)$ $(0 \leq i \leq n-1 , \, 0 \leq j \leq 32 \times m-1)$ از آن $getBit(a_i \bigoplus b_{\lfloor \frac{j}{32} \rfloor}, j \, mod \, 32)$ نوشته شده است. در این‌جا تابع $getBit(x,p)$ بیت $p$ام از عدد $x$ را برمی‌گرداند، برای مثال $getBit(6,0) = 0$ و $getBit(6,1) = 1$ و $getBit(6,2) = 1$ هستند. تمام جدول‌هایی که از جدول ساخته شده با جابه‌جایی ستون‌ها می‌توان ساخت را در نظر بگیرید(حداکثر $32m!$ جدول متفاوت) و به ازای هر کدام از این جدول‌ها اندازه‌ي بزرگترین زیر جدولی (بزرگترین از لحاظ تعداد خانه‌های تشکیل دهنده) که تمام خانه‌هایش ۱ است را محاسبه کنید. بیشینه اعداد محاسبه شده برابر با میزان امنیت الگوریتم پفکی به ازای ورودی‌های $a_0,a_1,\cdots,a_{n-1}$ و $b_0,b_1,\cdots,b_{n-1}$ است. دقت کنید که تنها جابه‌جایی ستون‌ها مجاز است و جابه‌جایی سطر‌ها مجاز نیست.»

شما باید برنامه‌ای بنویسید که باتوجه به ورودی‌های الگوریتم پفکی، میزان امنیت آن را مشخص کند.

علامت $\bigoplus$ نشان‌دهنده عملگر $xor$ است. عبارت $a\, mod\, b$ نیز نشان‌دهنده باقی مانده عدد $a$ بر $b$ است.

ورودی🔗

در سطر اول ورودی به ترتیب دو عدد طبیعی $n$ و $m$ آمده است.

در سطر دوم $n$ عدد صحیح آمده است که عدد $i$ام $(1\leq i \leq n)$ آن نشان‌دهنده‌ي $a_{i-1}$ است.

در سطر سوم $m$ عدد صحیح آمده است که عدد $i$ام $(1 \leq i \leq m)$ آن نشان‌دهنده‌ی $b_{i-1}$ است.

خروجی🔗

در تنها سطر خروجی میزان امنیت روش پفکی را به ازای دنباله‌هایی که در ورودی آمده است، چاپ کنید.

محدودیت‌ها🔗

• $1 \leq n,m \leq 10^6$
• $0 \leq a_i,b_i \leq 2^{30}$

مثال🔗

ورودی نمونه ۱

2 2
1 2
1 2

خروجی نمونه ۱

2

ورودی نمونه ۲

4 4
1 3 2 10
4 1 7 15

خروجی نمونه ۲

16

۲۵امین دوره المپیاد کامپیوتر - آزمون نهایی اول - ۱۳۹۴/۶/۱۸