P13685 题解：

(本蒟蒻的第一篇题解，各位大佬不喜轻喷)
赛时被这题给创飞了，居然没发现规律。
其实规律比较好找，(~~打个暴力就行~~) 暴力程序相信各位巨老都会，就不放代码了。(~~懒得放~~)

但当我们提交这份程序时就会喜提子任务2、3的TLE。
回头看一看此题的数据范围：

\sum n\le10^6,a_i<2^{64}

这么大的数据范围肯定要找规律。

看到样例最大给到

n=13

,那么将样例增大一点到

14

，输出结果：
居然是0！
再不停增大

n

的大小，发现无论 $n$ 为多大，当 $n>13$ 时，结果总是为0

于是给程序加个特判就能轻松AC此题～

考虑更严谨的证明：(参考这里)

在二进制下，如果所有的数中0的个数超过64个，那么与

2^{64}

模完之后就会是0。
设此

n

个数中最低位有a个0、b个1，那么至少会有

\frac{a(a-1)}{2}+\frac{b(b-1)}{2}

个0。(可以枚举一些较小的数试试)
因此我们在

n

小时暴力、

n

大时输出

0

即可。

Code:

CPP

//码风较为诡异 见谅
#include<bits/stdc++.h>//本人偏向于用万能头
using namespace std;
typedef unsigned long long ll;//数字较大，保险一点用ull装
const int N=1e6+7;
int t;
int n;
ll a[N];
int mian(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        if(n<17){   
            //ll mod=pow(2,64);    模数，不加也没有影响
            ll ans=0;//暴力统计答案
            for(int i=1;i<=n;i++){
                for(int j=i+1;j<=n;j++){
                    if(i==1&&j==i+1) ans=a[i]^a[j];
                    else ans*=(a[i]^a[j]);
                    ans%=mod;
                    //其实也可以在ans==0时跳出循环，乘0 ans还是0
                }
            }
            cout<<ans<<"\n";        
        }else{
            cout<<0<<"\n";
        }
    }
    return 0;
}

(求过!求过!求过!)

题解：P13685 【MX-X16-T3】「DLESS-3」XOR and Impossible Problem

文章操作

P13685 题解：

考虑更严谨的证明：(参考这里)

Code:

相关推荐

评论

题解：P13685 【MX-X16-T3】「DLESS-3」XOR and Impossible Problem