【二进制推式子】2021 CCPC新疆省赛 H-xor

比眉伴天荒 2024-03-24 17:52 35阅读 0赞

**感觉这种题写不了一点**

[H-Problem H. xor\_2021 CCPC 新疆省赛 (nowcoder.com)][H-Problem H. xor_2021 CCPC _ _nowcoder.com]

题意：

![eaed73bb977a48a499c6ebf4b730743d.png][]

思路：

因为直接枚举两个指针肯定超时，因此考虑枚举别的东西来降低复杂度

本来想着枚举每一个位，统计每个位的贡献，但是发现很难计算

因此需要考虑推柿子：

![47970d6054ec4563879f8e18571654bb.png][]

化简之后，发现只需要枚举两个30的指针，然后哈希统计一下每两位的状态的方案数就好了

Code：

#include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    
    int n;
    int a[mxn],F[33][33][2][2],p[mxn];
    void solve(){
    	cin>>n;
    	p[0]=1ll;
    	for(int i=1;i<=63;i++) p[i]=(p[i-1]*2ll)%mod;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	for(int i=1;i<=n;i++){
    		for(int j=0;j<=30;j++){
    			for(int k=0;k<=30;k++){
    				F[j][k][(a[i]>>j)&1][(a[i]>>k)&1]++;
    			}
    		}
    	}
    	int ans=0;
    	for(int i=0;i<=30;i++){
    		for(int j=0;j<=30;j++){
    			for(int k=0;k<=1;k++){
    				for(int z=0;z<=1;z++){
    					ans=(ans+(((p[i+j]%mod)*F[i][j][k][z]%mod)*F[i][j][k^1][z^1])%mod)%mod;
    				}
    			}
    		}
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[H-Problem H. xor_2021 CCPC _ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/22754/H
[eaed73bb977a48a499c6ebf4b730743d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/782b1f338efd4354b24b2f3c841b8246.png
[47970d6054ec4563879f8e18571654bb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/935ac7d9ec1d4e4a80fe0014a50451bb.png