题解：P17400 [ICPC 2018 Shenyang R] Distance Between Sweethearts

· · 题解

复杂度 O(T V^2)，严肃爆掉 FWT。

假期望转计数即可，下文中令男的限制为 a_{i,0}，女的限制为 a_{i,1}，M 为 \max_{i} |a_{i,0}-a_{i,1}|，X 为 \bigoplus_{i,j} a_{i,j}。

看到异或先拆位：答案表示为 \sum_k 2^k M_k \oplus X_k。也就是说当 X_k 为 0 时 M_k 为 1 有贡献，反之同理。

注意到 M_k 为 1 时 M 的取值是连续的，为区间 [(2p+1)2^k,(2p+2)2^k)。这样的区间共有 \frac{V}{2^k} 个，那么所有位区间个数之和为 \sum_k \frac{V}{2^k} = O(V) 个。

怎么计数这个区间贡献？c_{d,p_d,t} 表示在第 d 个限制是 p_d 时（p 为 0 \sim 3 的状态，第一位是第 k 位女的限制，第二位是男的），|a_{i,0}-a_{i,1}| \le t 的方案数。则区间 [L,R] 的方案数为 \prod_d c_{d,p_d,R}-\prod_d c_{d,p_d,L-1}。

算 c 是简单的，预处理女的限制满足的个数的前缀和，然后枚举男的满足限制的 x，贡献为在 [x-t,x+t] 中的限制满足的女的个数。对于一个 t，算出 c 的复杂度是 O(V)。

之后枚举 2^6 种 a_k，按 X_k 加上对应 M_k 的贡献即可。

总复杂度 O(TV^2)。

下面的代码 signed long long 过了，没卡，卡了踢我。

另附 #define int __int128 的提交：Link。

:::info[Code]{open}

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int N=2e3+5;
array<int,N> pre;
array<array<int,4>,3> all;
array<array<array<int,N>,4>,3> c;
array<array<int,2>,3> a;
signed Main(int Tc){
    int ans=0,n=0;
    for(int j=0;j<2;j++)
        for(int i=0;i<3;i++)
            cin>>a[i][j],n=max(n,(int)a[i][j]);
    for(int k=0,bit=2;k<11;k++,bit<<=1){
        vector<pair<int,int> > v;
        vector<int> q;
        for(int p=0;;p++){
            int l=(2*p+1)<<k,r=((2*p+2)<<k)-1;
            if(l>n) break;
            if(r>n) r=n;
            v.push_back(make_pair(l-1,r));
            q.push_back(l-1);
            q.push_back(r);
        }
        sort(q.begin(),q.end());
        q.erase(unique(q.begin(),q.end()),q.end());
        int m=q.size();
        for(int d=0;d<3;d++){
            for(int p=0;p<4;p++){
                int pb=p>>1,pg=p&1;
                pre[0]=0;
                for(int i=0;i<=a[d][1];i++)
                    if(((i>>k)&1)==pg)  pre[i+1]=pre[i]+1;
                    else    pre[i+1]=pre[i];
                vector<int> X;
                for(int i=0;i<=a[d][0];i++)
                    if(((i>>k)&1)==pb)
                        X.push_back(i);
                all[d][p]=pre[a[d][1]+1]*X.size();
                for(int i=0;i<q.size();i++){
                    int t=q[i],res=0;
                    for(int x:X){
                        int l=max((int)0,x-t),r=min((int)a[d][1],x+t);
                        if(l<=r)    res+=pre[r+1]-pre[l];
                    }
                    c[d][p][i]=res;
                }
            }
        }
        int res=0;array<int,3> p;
        for(p[0]=0;p[0]<4;p[0]++)
            for(p[1]=0;p[1]<4;p[1]++)
                for(p[2]=0;p[2]<4;p[2]++){
                    int x=p[0]^p[1]^p[2];
                    x=(x&1)^(x>>1);
                    int tot=1;
                    for(int d=0;d<3;d++)
                        tot*=all[d][p[d]];
                    int cnt=0;
                    for(auto seg:v){
                        int l=seg.first,r=seg.second;
                        l=lower_bound(q.begin(),q.end(),l)-q.begin();
                        r=lower_bound(q.begin(),q.end(),r)-q.begin();
                        int L=1,R=1;
                        for(int d=0;d<3;d++){
                            L*=c[d][p[d]][l];
                            R*=c[d][p[d]][r];
                        }
                        cnt+=R-L;
                    }
                    if(x)   ans+=(tot-cnt)<<k;
                    else    ans+=cnt<<k;
                }
    }
    cout<<"Case #"<<(signed)(Tc)<<": "<<(ull)(ans)<<endl;
    return 0;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
    clock_t Start=clock();
    signed T;
    cin>>T;
    for(int Tc=1;Tc<=T;Tc++)
        Main(Tc);
    cerr<<(double)(clock()-Start)/CLOCKS_PER_SEC;
    return 0;
}
/*
10
2000 2000 2000 2000 2000 2000
2000 2000 2000 2000 2000 2000
2000 2000 2000 2000 2000 2000
2000 2000 2000 2000 2000 2000
2000 2000 2000 2000 2000 2000
2000 2000 2000 2000 2000 2000
2000 2000 2000 2000 2000 2000
2000 2000 2000 2000 2000 2000
2000 2000 2000 2000 2000 2000
2000 2000 2000 2000 2000 2000
0.34797 s
*/

:::