H - Hot Black Hot White（数论/取模运算）

题目

题意

给定n个整数ai，定义H(ai,aj)的值为 H(ai,aj) = concat(ai,aj) * cancat(aj,ai) + ai*aj（mod 3） 其中concat(ai,aj)表示两个数的拼接，如concat(23,14)=2314,而concat(14,23)=1423。

现要求将这n个数平均分成2组，使得不同组之间的任意两个元素，它们的H值取值不能为Z。Z可以自己定义，可以为0，1，或2。

思路

c o n c a t ( a i , a j ) = a i ∗ 1 0 k + a j concat(ai,aj) = ai * 10^k + aj concat(ai,aj)=ai∗10k+aj 而由于10 % 3 == 1，所以 c o n c a t ( a i , a j ) = a i ∗ 1 0 k + a j = a i ∗ 1 k + a j = a i + a j concat(ai,aj) = ai * 10^k + aj = ai * 1^k + aj =ai+aj concat(ai,aj)=ai∗10k+aj=ai∗1k+aj=ai+aj,(mod 3) 所以 H ( a i , a j ) = ( a i + a j ) ∗ ( a i + a j ) + a i ∗ a j = a i 2 + a j 2 + 3 ∗ a i ∗ a j = a i 2 + a j 2 H(ai,aj)=(ai+aj)*(ai+aj) + ai*aj = ai^2+aj^2+3*ai*aj=ai^2+aj^2 H(ai,aj)=(ai+aj)∗(ai+aj)+ai∗aj=ai2+aj2+3∗ai∗aj=ai2+aj2,(mod 3)

又因为 0 ∗ 0 = 0 , 1 ∗ 1 = 1 , 2 ∗ 2 = 1 0*0 = 0,1*1 =1,2*2=1 0∗0=0,1∗1=1,2∗2=1(mod 3)。 统计ai^2模3为0和非0的个数，

• 如果0的个数有一半，则取它们做为一组，此时Z取2
• 如果非0的个数有一半，则取它们做为一组，此时Z取0

代码

#include
using namespace std;
#define ll long long
const int maxn = 200010;
const int mod = 1e9 + 7;


int n, x;
int a[maxn];
vector p[2];
char s[maxn];
void solve() {
	scanf("%d", &n);
	for (int i = 0; i