【洛谷八连测R5】whzzt-Confidence

题目描述

题目难度不一定按照题目顺序递增

请注意本题的空间限制为2333-2500KB！（前三个测试点的空间限制为2500KB）

给定两个长度相同的序列，这两个序列至多有 1 处不同。你的任务是找出这处不同。

输入输出格式

输入格式：

第一行包含一个数据组数 T 。每组数据的格式如下：
第一行一个整数 n 表示序列的长度。
接下来两行表示两个长度均为 n 的序列 A 和 B ，保证所有数字均为小于 2^32 的非负整数，这些数字可以看做是随机的。

输出格式：

输出共 T 行，每行第一个数 m≤1 表示不同的数目。接下来 m 个数表示两个序列中不同的位置。

说明

数据量较大，建议不要使用 cin / cout 输入输出。

为了防止不必要的MLE等情况出现，经过测试，下面的代码使用的空间在2300KB左右浮动。注意头文件所占用的空间也计入程序实际运行所占用的空间内。如在下面的代码中自行使用占用空间更大的数组，不能保证程序能够正常运行。

#include <stdio.h>
using namespace std;

unsigned int a[150005];
int main(){

    return 0;
}

代码

标程

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mo=998244353;
template<class T>
inline void read(T &x){
    x=0; char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
}
ll ksm(ll a,int p){
    ll res=1; for(;p;p>>=1,a=a*a%mo) if(p&1) res=res*a%mo;
    return res;
}
int T,n,m; ll a,b,x;
int main(){
    read(T);
    while(T--){
        read(n); a=b=0;
        for(int i=1;i<=n;++i){
            read(x); a=(a+x*i)%mo; b=(b+(ll)i*i%mo*x)%mo;
        }
        for(int i=1;i<=n;++i){
            read(x); a=(a-x*i)%mo; b=(b-(ll)i*i%mo*x)%mo;
        }
        if(!a) printf("0
");
        else printf("1 %lld
",(b*ksm(a,mo-2)%mo+mo)%mo);
    }
    return 0;
}
        

异或做法

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
template<class T>
inline void read(T &x){
    x=0; char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
}
int T,n; ll x,a;
int f[33],cur,last;
inline void solve(){
    for(int i=1;i<=n;++i){
        read(x); a^=x; cur=0;
        while(x){
            if(x&1) f[cur]^=i;
            ++cur; x>>=1;
        }
    }
}
int main(){
    read(T);
    while(T--){
        read(n); a=0;
        memset(f,0,sizeof(f));
        solve(); solve();
        if(!a) printf("0
");
        else {
            cur=0; printf("1 ");
            while(a){
                if(a&1){printf("%d
",f[cur]); break;}
                ++cur; a>>=1;
            }
        }
    }
    return 0;
}