【二进制】鑫鑫的算术

题目描述

AK掉五校联考的题目后，鑫鑫在研究二进制在数论中的应用。

鑫鑫给了你n个数，每次你可以从这其中选择两个数a和b，将它们的值分别赋为a and b和a or b（均为二进制位运算）。这样的操作，你可以执行任意多次。鑫鑫希望最终这些数的平方和尽量的大，你能帮他求出这个最大值吗？

输入

第一行一个正整数n，表示数的数量。
第二行n个非负整数，表示鑫鑫给你的n个数。（2≤n≤100000,0≤ai≤108）

输出

一行一个非负整数，表示答案。由于答案太大，你只需要输出答案对998244353（=7×17×223+1，一个质数）取模后的结果。

样例输入

复制样例数据

5
1 2 3 4 5

样例输出

99

 

思路

这题我首先是发现任意两个数进行题意的操作后，所得的结果a'和b'，a'^2+b'^2>=a^2+b^2。那么什么时候是大于呢，就是把a和b拆分成二进制，比如1和2吧，二进制为10和01，那么操作之后什么样呢，显然11和00啊，
就是尽可能的将二进制的1转移到一个或多个数上。那怎么是多个呢，就比如样例吧，两个7和一个1，因为最大就是三位二进制啊，111就是七啊，然后粘代码

代码如下：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+50;
const int mod = 998244353;
int a[maxn];
int bit[50];
int n,mlen=0;
inline int read()                                //读入优化
{
    int x=0,f=1;
    char c=getchar();
    while (!isdigit(c))
        f=c=='-'?-1:1,c=getchar();
    while (isdigit(c))
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
void solvebit()
{
    for(register int i=1;i<=n;i++)
    {
        int cnt=0;
        while(a[i])
        {
            bit[++cnt]+=a[i]%2;
            a[i]/=2;
        }
        mlen=max(mlen,cnt);
    }
//    for(register int i=1;i<=3;i++)
//        cout << bit[i] << endl;
}
int main()
{
    n=read();
    for(register int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    solvebit();
    ll all=0;
    for(register int i=1;i<=n;i++)
    {
        ll base=1;
        ll temp=0;
        for(register int j=1;j<=mlen;j++)
        {
            if(bit[j])
            {
                temp=(temp+base)%mod;
                bit[j]--;
            }
            base*=2;
        }
        //cout << temp << endl;
        all=(all+temp*temp%mod)%mod;
    }
    cout << all << endl;
    //cout << "Hello world!" << endl;
    return 0;
}