COMPFEST 14 - Preliminary H.Hot Black Hot White 数论｜构造

题目链接：H. Hot Black Hot White

题意：

给你$n$个数，你需要平均分成两份，分别有$\frac{n}{2}$个，如果两个数满足下面等式，则会发生冲突，那么就需要在同一类才不会发生冲突：

$$
{\rm concat}(A_i,A_j)\times {\rm concat}(A_j,A_i)+A_iA_j \equiv Z \quad {\rm mod} \ 3
$$

思路：

举个例子${\rm concat}(123,456)=123456$，那么其实就是$123\times 10^3+456$，那么这个跟幂有关系，但是有一个很重要的$10\equiv 1\quad ({\rm mod}\ 3)$，所以有：

$$
10^p\equiv 1\quad ({\rm mod}\ 3)
$$

那么有

$$
{\rm concat}(A_i,A_j)=\overline{A_iA_j}=A_i+A_j\equiv Z\quad {\rm mod}\ 3
$$

所以最后化简可以为：

然后来看看$A_i$在模$3$意义下的关系：

那么现在可以分成两种情况：

• 1）$val=0$的个数res大于等于$\frac{n}{2}$
  这个时候只需要令$Z=2$，res中输出$\frac{n}{2}$个$0$，其他输出$1$即可不发生碰撞

• 2）$val=0$的个数res小于$\frac{n}{2}$
  这些res个肯定需要输出$0$，其他的找$\frac{n}{2}-\rm res$出来即可。

代码：

inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        if (a[i]%3==0) cnt++;
    }
    if (cnt>=n/2)
    {
        cout<<2<<endl;
        int res = n/2;
        for (int i=1;i<=n;i++)
            if (a[i]%3==0&&res) cout<<0,res--;
            else cout<<1;
    }
    else
    {
        cout<<0<<endl;
        int res = n/2-cnt;
        for (int i=1;i<=n;i++)
            if (a[i]%3==0) cout<<0;
            else if (res) cout<<0,res--;
            else cout<<1;
    }
}