题解：P11431 [COCI 2024/2025 #2] 差异 / Različitost

· · 题解

有趣的题。

思路

看到异或就想到拆位，也只有拆位后才能快速计算。

由于 k 很大，考虑从每个值照成贡献下手，先假设 n > m，如果不是就把两个数组调换一下就好了，容易发现，b 数组可以分解为若干循环节，每个循环节会是若干个 a_i 要用到的，只不过不同的 a_i 所在的循环节开始位置不同。

循环节是很好找的，具体的从左到右枚举，找到一个还没有被分配到一个循环的点，从它开始循环直到回到它就结束，这样就得到一个新的循环，这里面所有值 \le n 的就是 a 数组中需要这个循环的点和位置。

知道后，我们搞一个前缀和数组，然后稍微盘一下边界情况后好了，具体实现的话就看代码吧。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define getchar() (p1 == p2 && (p2 = (p1 = buf1) + fread(buf1, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf1[1 << 23], *p1 = buf1, *p2 = buf1, ubuf[1 << 23], *u = ubuf;
namespace IO
{
    template<typename T>
    void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}
    template<typename T,typename... Args>
    void read(T &_x,Args&...others){Read(_x);Read(others...);}
    const int BUF=20000000;char buf[BUF],to,stk[32];int plen;
    #define pc(x) buf[plen++]=x
    #define flush(); fwrite(buf,1,plen,stdout),plen=0;
    template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++to]=48+x%10;while(to) pc(stk[to--]);}
}
using namespace IO;
const int N = 2e5+10,mod = 1e9+7;
int n,m,k,a[N],b[N],sum[N],sum1[N],v[N],v1[N],st[N],cnt1,st1[N],st2[N],cnt,o,ans,o1;
inline int solve(int x,int y)
{
    int o1 = 1+(k-y)/n;//这个数出现多少次
    //从x开始，k已经进行了y次，接下来每n个多出现一次 
    int ans = sum[cnt]*((o1/cnt)%mod)%mod;//>cnt的直接先算了 
    if(o1%cnt <= cnt-x+1) ans = (ans+sum[x+o1%cnt-1]-sum[x-1])%mod;//它的位置在x，往后延o1%cnt个，分讨一下 
    else ans = (ans+sum[cnt]-sum[x-1]+sum[o1%cnt-(cnt-x+1)])%mod;
    return ans;
}
inline int solve1(int x,int y)
{
    int o1 = 1+(k-y)/n;
    int ans = sum1[cnt]*((o1/cnt)%mod)%mod;
    if(o1%cnt <= cnt-x+1) ans = (ans+sum1[x+o1%cnt-1]-sum1[x-1])%mod;
    else ans = (ans+sum1[cnt]-sum1[x-1]+sum1[o1%cnt-(cnt-x+1)])%mod;
    return ans;
}
signed main()
{
    read(n),read(m),read(k);
    for(int i = 1;i <= n;i++) read(a[i]);
    for(int i = 1;i <= m;i++) read(b[i]);
    if(n > m)//我们需要钦定n<m 
    {
        for(int i = 1;i <= n;i++) swap(a[i],b[i]);
        swap(n,m);
    }
    for(int j = 0;j <= 63;j++)//枚举每一位 
    {
        for(int i = 1;i <= m;i++) v[i] = v1[i] = 0;
        for(int i = 1;i <= n;i++)
            if(!v1[i])
            {
                o = i,cnt = 0; cnt1 = 0;
                while(!v1[o])
                {
                    v1[o] = 1,st[++cnt] = o;
                    if(o <= n) st1[++cnt1] = o,st2[cnt1] = cnt;
                    o = (o+n-1)%m+1;//直接去找，最多m次，复杂度可以保证 
                }
                for(int i = 1;i <= cnt;i++) 
                {
                    sum[i] = sum[i-1]+((b[st[i]]&(1ll<<j))!=0);//1的 
                    sum1[i] = sum1[i-1]+((b[st[i]]&(1ll<<j))==0);//0的 
                }
                for(int i = 1;i <= cnt1;i++)
                {
                    o = st1[i];
                    if((a[o]&(1ll<<j))) ans = (ans+solve1(st2[i],st1[i])*((1ll<<j)%mod)%mod)%mod;
                    else ans = (ans+solve(st2[i],st1[i])*((1ll<<j)%mod)%mod)%mod;//计算贡献 
                }
            }
    }
    print(ans); flush();
    return 0;
}
/*
3 2 10
5 2
101 010
1 6 4
001 110 100
为了加速必须拆位，这个很显然
先假设n<m
考虑每个a_i异或的那些点第j位为0/1的分别是多少，前缀和统计一下 

1 2 1 2 1 2 1
1 2 3 1 2 3 1
*/