题解：AT_arc227_e [ARC227E] Shift and XOR Switches

· · 题解

好牛逼的题目。

:::info[🤔1] 你考虑这个有顺序无疑是难处理的，思考这个顺序是否是可以排除的。 :::

:::success[😎1] 你观察到其实顺序是不重要的。

你考虑两个操作 a,b 的操作顺序，和一个下标 i 的操作顺序。

发现展开其实都是。

B_{i}\oplus B_{i-a}\oplus B_{i-b}\oplus B_{i-a-b}
于是我们不需要考虑操作顺序了。

:::info[🤔2] 考虑会产生重复的结果的 B 操作的 a 的是什么形式。

更具体的且简单的。

考虑两次操作 a,b 何种情况下，其不会产生贡献。

也就是说假设操作前的序列是 B1 操作完 a,b 后的是 B2 在什么情况的 a,b 下有 B1=B2 的状态。

:::success[😎2] 观察到 a=b,2a>n 时，显然会不会产生贡献，证明显然。

因为你选两个 a 等价于选择一个 2a 而 2a>n 时，显然不产生操作。此时你的问题转化成了一个新问题。

你考虑选择一个集合 S 其中两个相同的数字 a 讲会合并成 2a 问知道合并到无法合并时的集合的状态有多少种。注意，数字合并到 >n 需要丢弃。

:::info[🤔3] 对于这个新问题，你观察到仍然无法处理大量的数字，这个问题如何解决？ :::

:::success[😎3] 容易发现相同数字合并最多合并 \log 次就会被扔掉。

于是你考虑将所有数字的 2 都除掉，剩下的数字相同的，就是一组，显然的，不同组无法合并出相同的数字。

于是以组就只有 \log 个数字了。

考虑一个数字拆成了 q2^{k} 了，此时组内 q 相同，只需要考虑 k 了。

观察到相同数字合并每一次使得 k+1 于是就有一个简单动态规划做法了。

考虑 f_{i,j} 表示已经处理完了低 i 位，可能传入第 i 位的数量可能是 [0,j] 的不同集合的数量。

转移是容易的，考虑这个数字最后剩下来 0 还是 1 即可，可以用递归来实现这个过程复杂度是 O(n+m) 的。

:::success[AC😎code]

//Author:kevinZ99
#include <bits/stdc++.h>
#define up(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define dn(a,b,c) for(int (a)=(b);(a)>=(c);--(a))
#define fst first
#define sed second
#define pref static inline
using namespace std;using hint=__int128;using uhint=unsigned __int128;
using us=unsigned short;using ui=unsigned int;using ll=long long;using ull=unsigned long long;
using db=double;using ldb=long double;using pii=pair<int,int>;using pll=pair<ll,ll>;
using pil=pair<int,ll>;using pli=pair<ll,int>;using vi=vector<int>;using vl=vector<ll>;
using vpi=vector<pii>;using vpl=vector<pll>;using vpil=vector<pil>;using vpli=vector<pli>;
ostream& out128(ostream&,uhint,bool);ostream& operator<<(ostream&,hint);ostream& operator<<(ostream&,uhint);
namespace mystl{
    const int SI=1<<22,SO=1<<20;pref size_t fr(void*p,size_t n){
#ifdef __linux__
        return fread_unlocked(p,1,n,stdin);
#else
        return fread(p,1,n,stdin);
#endif
    }
    unsigned char mp[1<<16];struct Init{Init(){memset(mp,255,sizeof mp);for(unsigned i=0;i<10;++i)for(unsigned j=0;j<10;++j){unsigned char s[2]={static_cast<unsigned char>('0'+i),static_cast<unsigned char>('0'+j)};uint16_t x;memcpy(&x,s,2);mp[x]=static_cast<unsigned char>(i*10+j);}}}init;
    pref unsigned pv(const char*p){uint16_t x;memcpy(&x,p,2);return mp[x];}
    struct IB:streambuf{
        char b[SI];bool eofed=false;IB(){setg(b,b,b);}
        int_type underflow()override{if(gptr()<egptr())return traits_type::to_int_type(*gptr());size_t n=fr(b,SI);if(!n)return traits_type::eof();setg(b,b,b+n);return traits_type::to_int_type(*gptr());}
        inline void commit(char*p){gbump(static_cast<int>(p-gptr()));}
        inline bool refill(char*&p,char*&e){commit(p);if(traits_type::eq_int_type(underflow(),traits_type::eof())){eofed=true;return false;}p=gptr();e=egptr();return true;}
        inline bool head(char*&p,char*&e,bool&neg){eofed=false;for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e)break;if(!refill(p,e))return false;}neg=false;if(*p=='-'||*p=='+'){neg=*p=='-';++p;if(p==e&&!refill(p,e))return false;}return true;}
        template<class T,class U>inline bool slow(T&x,bool neg,char*&p,char*&e){U y=0;bool ok=false;for(;;){while(p<e){unsigned c=static_cast<unsigned char>(*p)-static_cast<unsigned>('0');if(c>9){commit(p);if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}ok=true;y=static_cast<U>(y*10+c);++p;}if(!refill(p,e)){if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}}}
        template<class T,class U,int K>inline bool num(T&x){x=0;char*p=gptr(),*e=egptr();bool neg;if(!head(p,e,neg))return false;if(e-p<2*K+1)return slow<T,U>(x,neg,p,e);U y=0;bool ok=false;for(int i=0;i<K;++i){unsigned v=pv(p);if(v>=255)break;ok=true;y=static_cast<U>(y*100+static_cast<U>(v));p+=2;}unsigned c=static_cast<unsigned char>(*p)-static_cast<unsigned>('0');if(c<=9){ok=true;y=static_cast<U>(y*10+c);++p;}commit(p);if(!ok)return false;x=neg?static_cast<T>(U(0)-y):static_cast<T>(y);return true;}
        inline bool read(short&x){return num<short,unsigned short,5>(x);}inline bool read(us&x){return num<us,us,5>(x);}inline bool read(int&x){return num<int,unsigned,5>(x);}inline bool read(unsigned&x){return num<unsigned,unsigned,5>(x);}inline bool read(long&x){return sizeof(long)<=4?num<long,unsigned long,5>(x):num<long,unsigned long,10>(x);}inline bool read(unsigned long&x){return sizeof(unsigned long)<=4?num<unsigned long,unsigned long,5>(x):num<unsigned long,unsigned long,10>(x);}inline bool read(ll&x){return num<ll,ull,10>(x);}inline bool read(ull&x){return num<ull,ull,10>(x);}inline bool read(hint&x){return num<hint,uhint,20>(x);}inline bool read(uhint&x){return num<uhint,uhint,20>(x);}
        inline bool read(char&x){x=0;eofed=false;char*p=gptr(),*e=egptr();for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e){x=*p++;commit(p);return true;}if(!refill(p,e))return false;}}
        inline bool read(string&x){eofed=false;x.clear();char*p=gptr(),*e=egptr();for(;;){while(p<e&&static_cast<unsigned char>(*p)<=32)++p;if(p<e)break;if(!refill(p,e))return false;}for(;;){char*q=p;while(q<e&&static_cast<unsigned char>(*q)>32)++q;x.append(p,static_cast<size_t>(q-p));p=q;if(p<e){commit(p);return true;}if(!refill(p,e))return true;}}
        template<class T>inline bool fp(T&x){x=0;string s;if(!read(s))return false;return cv(s.c_str(),x);}static inline bool cv(const char*s,float&x){char*e=nullptr;x=strtof(s,&e);return e!=s&&*e==0;}static inline bool cv(const char*s,double&x){char*e=nullptr;x=strtod(s,&e);return e!=s&&*e==0;}static inline bool cv(const char*s,long double&x){char*e=nullptr;x=strtold(s,&e);return e!=s&&*e==0;}
    }ib;
    struct OB:streambuf{
        char b[SO];OB(){setp(b,b+SO);}~OB(){sync();}
        int sync()override{size_t n=static_cast<size_t>(pptr()-pbase());if(n&&fwrite(b,1,n,stdout)!=n)return -1;setp(b,b+SO);return 0;}
        int_type overflow(int_type c=traits_type::eof())override{if(sync())return traits_type::eof();if(!traits_type::eq_int_type(c,traits_type::eof()))*pptr()=traits_type::to_char_type(c),pbump(1);return traits_type::not_eof(c);}
        inline void pc(char c){if(pptr()==epptr()&&traits_type::eq_int_type(overflow(),traits_type::eof()))return;*pptr()=c;pbump(1);}inline void ps(const char*s,size_t n){while(n){size_t k=static_cast<size_t>(epptr()-pptr());if(!k){if(traits_type::eq_int_type(overflow(),traits_type::eof()))return;k=static_cast<size_t>(epptr()-pptr());}k=min(k,n);memcpy(pptr(),s,k);pbump(static_cast<int>(k));s+=k;n-=k;}}
    }ob;
    struct FastIn:istream{
        FastIn():istream(&ib){}using istream::operator>>;template<class T>inline FastIn&go(T&x){if(!ib.read(x))setstate(ib.eofed?ios::eofbit|ios::failbit:ios::failbit);else if(ib.eofed)setstate(ios::eofbit);return *this;}inline FastIn&operator>>(short&x){return go(x);}inline FastIn&operator>>(us&x){return go(x);}inline FastIn&operator>>(int&x){return go(x);}inline FastIn&operator>>(unsigned&x){return go(x);}inline FastIn&operator>>(long&x){return go(x);}inline FastIn&operator>>(unsigned long&x){return go(x);}inline FastIn&operator>>(ll&x){return go(x);}inline FastIn&operator>>(ull&x){return go(x);}inline FastIn&operator>>(hint&x){return go(x);}inline FastIn&operator>>(uhint&x){return go(x);}inline FastIn&operator>>(char&x){return go(x);}inline FastIn&operator>>(string&x){return go(x);}inline FastIn&operator>>(float&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(double&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(long double&x){if(!ib.fp(x))setstate(ios::failbit);return *this;}inline FastIn&operator>>(bool&x){int y=0;go(y);x=y!=0;return *this;}
    }fin;
    struct FastOut:ostream{
        FastOut():ostream(&ob){}using ostream::operator<<;template<class U>inline FastOut&uo(U x){char s[64];int n=0;do{s[n++]=static_cast<char>('0'+static_cast<unsigned>(x%10));x/=10;}while(x);while(n)ob.pc(s[--n]);return *this;}template<class T>inline FastOut&so(T x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}typedef typename make_unsigned<T>::type U;U y;if(x<0){ob.pc('-');y=U(0)-static_cast<U>(x);}else y=static_cast<U>(x);return uo(y);}template<class T>inline FastOut&un(T x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}return uo(x);}
        inline FastOut&operator<<(short x){return so(x);}inline FastOut&operator<<(us x){return un(x);}inline FastOut&operator<<(int x){return so(x);}inline FastOut&operator<<(unsigned x){return un(x);}inline FastOut&operator<<(long x){return so(x);}inline FastOut&operator<<(unsigned long x){return un(x);}inline FastOut&operator<<(ll x){return so(x);}inline FastOut&operator<<(ull x){return un(x);}inline FastOut&operator<<(bool x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}ob.pc(x?'1':'0');return *this;}inline FastOut&operator<<(char c){if(width()!=0){static_cast<ostream&>(*this)<<c;return *this;}ob.pc(c);return *this;}inline FastOut&operator<<(const char*s){if(width()!=0){static_cast<ostream&>(*this)<<s;return *this;}ob.ps(s,strlen(s));return *this;}inline FastOut&operator<<(const string&s){if(width()!=0){static_cast<ostream&>(*this)<<s;return *this;}ob.ps(s.data(),s.size());return *this;}inline FastOut&operator<<(float x){static_cast<ostream&>(*this)<<x;return *this;}inline FastOut&operator<<(double x){static_cast<ostream&>(*this)<<x;return *this;}inline FastOut&operator<<(long double x){static_cast<ostream&>(*this)<<x;return *this;}
        inline FastOut&operator<<(hint x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}uhint y;if(x<0){ob.pc('-');y=uhint(0)-static_cast<uhint>(x);}else y=static_cast<uhint>(x);return uo(y);}inline FastOut&operator<<(uhint x){if(width()!=0){static_cast<ostream&>(*this)<<x;return *this;}return uo(x);}FastOut&operator<<(ios_base&(*f)(ios_base&)){f(*this);return *this;}FastOut&operator<<(ostream&(*f)(ostream&)){f(*this);return *this;}FastOut&operator<<(ios&(*f)(ios&)){f(*this);return *this;}
    }fout;
}
ostream& out128(ostream&out,uhint x,bool neg){char s[48];int n=0;do{s[n++]=static_cast<char>('0'+static_cast<unsigned>(x%10));x/=10;}while(x);streamsize w=out.width(0),k=max<streamsize>(0,w-n-neg);char f=out.fill();ios::fmtflags a=out.flags()&ios::adjustfield;if(a==ios::left){if(neg)out.put('-');while(n)out.put(s[--n]);while(k--)out.put(f);}else if(a==ios::internal&&neg){out.put('-');while(k--)out.put(f);while(n)out.put(s[--n]);}else{while(k--)out.put(f);if(neg)out.put('-');while(n)out.put(s[--n]);}return out;}
ostream& operator<<(ostream&out,hint x){bool neg=x<0;return out128(out,neg?uhint(0)-static_cast<uhint>(x):static_cast<uhint>(x),neg);}ostream& operator<<(ostream&out,uhint x){return out128(out,x,false);}
#define cin mystl::fin
#define cout mystl::fout
namespace my{
    const int N=2e5+5,inf=1000000000;template<typename T>pref T Min(T x,T y){return x<y?x:y;}template<typename T>pref T Max(T x,T y){return x>y?x:y;}template<typename T>pref T Abs(T x){return x<0?-x:x;}
    const int P=998244353;
    int n,m,a[N];
    bool vis[N];
    int dfs(int x,int t){
        if(x>=n)return 1;
        vis[x]=true,t+=a[x];
        int ret=dfs(x<<1,t/2);
        if(t>0)ret=(ret+dfs(x<<1,(t-1)/2))%P;
        return ret;
    }
    pref void SOLVE(){
        cin>>n>>m;
        up(i,1,m){
            int x;cin>>x;
            a[x]++;
        }
        int ans=1;
        up(i,1,n-1){
            if(vis[i])continue;
            ans=(1ll*ans*dfs(i,0))%P;
        }cout<<ans<<'\n';
    }
}
int main(){my::SOLVE();return 0;}

:::