异或路径题解

yingshi1119 · 2024-07-12 19:41:10 · 个人记录

观察题面，第一眼是一个非常裸的dfs，但是我们发现有一个 n,m\le20 的巨大的数据范围，所以考虑优化。

重新理解题面，发现在节点 (x,y) 下一步有两种状态 (x+1,y) 和 (x,y+1) 这与 Meet in the Middle 非常相似，所以我们尝试将一维的分段搜索拓展到二维。

首先，将一维中“一半”的定义改为二维路径长度的一半，但这时，中间相交的部分过多，所以将第二段的起点从中间变为 (n,m) ,然后就可以照搬了。

注意开 long long 并特判 n=m=1 的情况。

时间复杂度 \sqrt {2^{n+ m}}

AC代码：

#include<bits/stdc++.h>
using namespace std;
unordered_map<long long,long long> m[41][41];
unordered_map<long long,long long> m2[41][41];
long long a[41][41];
long long n,mm,k;
void dfs(int x,int y,long long len,long long sum)
{
    if(len==1)
    {
        m[x][y][sum^a[x][y]]++;
        return ;
    }
    else if(x==n)
    {
        dfs(x,y+1,len-1,sum^a[x][y]);
    }
    else if(y==mm)
    {
        dfs(x+1,y,len-1,sum^a[x][y]);
    }
    else 
    {
        dfs(x,y+1,len-1,sum^a[x][y]);
        dfs(x+1,y,len-1,sum^a[x][y]);
    }
    return;
}
void dfs1(int x,int y,long long len,long long sum)
{
    if(len==1)
    {
        m2[x][y][sum^a[x][y]]++;
        //cout<<(sum^a[x][y])<<endl;
        return ;
    }
    else if(x==1)
    {
        dfs1(x,y-1,len-1,sum^a[x][y]);
    }
    else if(y==1)
    {
        dfs1(x-1,y,len-1,sum^a[x][y]);
    }
    else 
    {
        dfs1(x,y-1,len-1,sum^a[x][y]);
        dfs1(x-1,y,len-1,sum^a[x][y]);
    }
    return;
}
int main()
{
    cin>>n>>mm>>k;
    if(n==1&&mm==1)
    {
        long long a;
        cin>>a;
        cout<<(a==k);
        return 0;   
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=mm;j++) cin>>a[i][j];
    long long len=(n+mm-1)/2;
    //cout<<len<<endl;
    dfs(1,1,len,0);
    if(len*2<n+mm-1)
    {
        len++;
    }
    dfs1(n,mm,len,0);
    len=(n+mm-1)/2;
    unsigned long long ans=0;
    for(int i=1;i<=min(len+1,n);i++)
    {
        for(int j=1;j<=min(len-i+1,mm);j++)
        {
            if(i+j!=len+1) continue;
            else
            {
                //cout<<i<<" "<<j<<endl;
                if(i==n)
                {
                    unordered_map<long long,long long>::iterator it;
                    for(it=m[i][j].begin();it!=m[i][j].end();it++)
                    {
                        long long p=it->first;
                        long long d=k^p;
                        if(m2[i][j+1][d]!=0)
                        {
                            ans+=(it->second)*m2[i][j+1][d];
                        }
                    }
                }
                else if(j==mm)
                {
                    unordered_map<long long,long long>::iterator it;
                    for(it=m[i][j].begin();it!=m[i][j].end();it++)
                    {
                        long long p=it->first;
                        long long d=k^p;
                        if(m2[i+1][j][d]!=0)
                        {
                            ans+=(it->second)*m2[i+1][j][d];
                        }
                    }
                }
                else
                {
                    unordered_map<long long,long long>::iterator it;
                    for(it=m[i][j].begin();it!=m[i][j].end();it++)
                    {
                        long long p=it->first;
                        long long d=k^p;
                        if(m2[i+1][j][d]!=0)
                        {
                            ans+=(it->second)*m2[i+1][j][d];
                        }
                    }
                    //unordered_map<long long,long long>::iterator it;
                    for(it=m[i][j].begin();it!=m[i][j].end();it++)
                    {
                        long long p=it->first;
                        long long d=k^p;
                        if(m2[i][j+1][d]!=0)
                        {
                            ans+=(it->second)*m2[i][j+1][d];
                        }
                    }
                }
            }
        }
    }
    cout<<ans;
    return 0;
}