题解：CF1045B Space Isaac

· · 题解

前言

何意味题。

Description

给定 m，定义全集 U=\{0,1,2,\ldots,m-1\}。

给定大小为 n 的集合 A，定义其关于 U 的补集为 B。

对于集合 \{(x+y)\bmod m\mid x\in A,y\in B\}，求其关于 U 的补集。

Solution

以下所有运算及说明均在模 m 意义下进行。

考虑一个数 x 什么时候会成为答案，当且仅当存在 p+q=x 且 p\in A,q\in B。

也就是对于 x 的所有分解方案 x=p+q，要么 p 和 q 都在 A 中，要么都不在。

现在考虑一个平凡的 i。

若我们取 x=a_1+a_i，固定了这个 x，那么又因为 a_2 在 A 中，所以 x-a_2 也应当在 A 中。

而这个 x-a_2 能对应哪个数？显然是 a_{i-1}。

这样一直匹配下去，如果每个数都能匹配上，则这个 x 在前 i 个数的范围内合法。

而 i 后面也有数，此时 a_{i+1} 显然应该匹配 a_n，因为和为 x 只有两种情况：x 和 x+m。

前 i 个数两两匹配，和显然不可能为 x+m；自然后 n-i 个数两两匹配的和就为 x+m 了。

如何刻画这个条件？

我们做一个差分，发现两端匹配和相等等价于差分数组上是回文的。

所以枚举断点，使用哈希或 manacher 判断当前的 i 是否合法即可。

Code

:::info[代码]

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;

template<const unsigned long long mod> class modint{
    private:
        unsigned long long x;

    public:
        inline modint():x(0){}
        inline modint(const unsigned long long _x):x(_x%mod){}
        inline modint(const signed long long _x):x(_x>=0?_x:(mod-(-_x)%mod)%mod){}
        inline modint(const signed int _x){*this=modint((signed long long)_x);}
        inline modint(const unsigned int _x){*this=modint((unsigned long long)_x);}

        friend modint operator-(const modint a){return modint(-a.x+mod);}
        friend modint operator+(const modint a,const modint b){return modint(a.x+b.x);}
        friend modint operator-(const modint a,const modint b){return a+(-b);}
        friend modint operator*(const modint a,const modint b){return modint(a.x*b.x);}
        friend modint operator/(const modint a,const modint b){return a*b.getinv();}

        inline modint &operator+=(const modint b){return *this=*this+b;}
        inline modint &operator-=(const modint b){return *this=*this-b;}
        inline modint &operator*=(const modint b){return *this=*this*b;}
        inline modint &operator/=(const modint b){return *this=*this/b;}

        inline modint operator++(){*this=*this+1;return *this;}
        inline modint operator--(){*this=*this-1;return *this;}
        inline modint operator++(int){modint tmp=*this;*this=*this+1;return tmp;}
        inline modint operator--(int){modint tmp=*this;*this=*this-1;return tmp;}

        friend bool operator<(const modint &a,const modint &b){return a.x<b.x;}
        friend bool operator>(const modint &a,const modint &b){return a.x>b.x;}
        friend bool operator<=(const modint &a,const modint &b){return a.x<=b.x;}
        friend bool operator>=(const modint &a,const modint &b){return a.x>=b.x;}
        friend bool operator==(const modint &a,const modint &b){return a.x==b.x;}
        friend bool operator!=(const modint &a,const modint &b){return a.x!=b.x;}

        inline friend istream &operator>>(istream &in,modint &d){in>>d.x;d.x%=mod;return in;}
        inline friend ostream &operator<<(ostream &out,modint d){out<<d.x;return out;}

        inline const modint qpow(long long a)const{
            modint res=1,_x=*this;
            while(a){if(a&1) res*=_x;_x*=_x,a>>=1;}
            return res;
        }
        inline const modint getinv()const{return this->qpow(mod-2);}
};

int n,m;
int a[200010],b[200010];

const unsigned long long mod1=998244353,P1=131;
const unsigned long long mod2=998244853,P2=171;

modint<mod1> pw1[200010],pre1[200010],suf1[200010];
modint<mod2> pw2[200010],pre2[200010],suf2[200010];

modint<mod1> getprehash1(int l,int r){return pre1[r]-pre1[l-1]*pw1[r-l+1];}
modint<mod2> getprehash2(int l,int r){return pre2[r]-pre2[l-1]*pw2[r-l+1];}

modint<mod1> getsufhash1(int l,int r){return suf1[l]-suf1[r+1]*pw1[r-l+1];}
modint<mod2> getsufhash2(int l,int r){return suf2[l]-suf2[r+1]*pw2[r-l+1];}

bool check(int l,int r){
    if(l>=r) return true;
    return getprehash1(l+1,r)==getsufhash1(l+1,r)&&getprehash2(l+1,r)==getsufhash2(l+1,r);
}

int main(){
    cin.tie(0)->sync_with_stdio(false);

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];

    pw1[0]=1;
    pw2[0]=1;
    for(int i=1;i<=n;i++) pw1[i]=pw1[i-1]*P1;
    for(int i=1;i<=n;i++) pw2[i]=pw2[i-1]*P2;

    for(int i=1;i<=n;i++){
        pre1[i]=pre1[i-1]*P1+b[i];
        pre2[i]=pre2[i-1]*P2+b[i];
    }

    for(int i=n;i>=1;i--){
        suf1[i]=suf1[i+1]*P1+b[i];
        suf2[i]=suf2[i+1]*P2+b[i];
    }

    set<int> ans;
    for(int i=1;i<n;i++) if((a[1]+a[i])%m==(a[i+1]+a[n])%m&&check(1,i)&&check(i+1,n)) ans.insert((a[1]+a[i])%m);
    if(check(1,n)) ans.insert((a[1]+a[n])%m);

    cout<<ans.size()<<"\n";
    for(int x:ans) cout<<x<<" ";

    # ifdef TakanashiHoshino
    cerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";
    # endif
    return 0;
}

:::