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;
    }
}