P13088 题解
lmh_qwq
·
·
题解
五次操作几乎什么都干不了，所以必须在预处理的时候把东西全部弄好。
现在考虑 p_{q_i} 的置换环数量怎么统计。显然只需要考虑长度 \le 2 的置换环。
计算 \{q_i\} 的逆排列 \{q'_i\}。对于 p_{q_i} 的每个长度为 1 的置换环，都有 p_i=q'_i；对于每个 p_{q_i} 长度为 2 的置换环 (i,j)，都有 (p_i,p_j)=(q'_j,q'_i)。
发现 (p_i,p_j)=(q'_j,q'_i) 不好处理，但是 \{p_i,p_j\}=\{q'_i,q'_j\} 很好处理。如果两个位置 (i,j) 满足 \{p_i,p_j\}=\{q'_i,q'_j\}，那么另外两个位置 (k,l) 也满足 \{p_k,p_l\}=\{q'_k,q'_l\}，这样又可以减少一半状态。
对于一个排列，用 16 个 bit 记录对于每个 (i,j) 是否有 p_i=j；然后记录 (0,1),(0,2),(0,3) 的 \{p_i,p_j\}——这需要 18 个 bit，总共是 34 个。
把逆排列也这样做一次，总共恰好 68 个 bit。
现在对于任意一个输入，先把 x_2 右移 34 位拿到逆排列的信息，然后和 x_1 按位与得到 x。
现在考虑每一种可能的置换环大小可重集。
$$
\begin{aligned}
\{1,1,1,1\}&:c=4+3=7,a=4\\
\{1,1,2\}&:c=2+1=3,a=3\\
\{1,3\}&:c=1,a=2\\
\{2,2\}&:c=0+1=1,a=2\\
\{4\}&:c=0,a=1
\end{aligned}
$$
显然 $a=\mathrm{popcount}(c)+1$，将 $c$ 随便按位或上一个玩意再求 $\mathrm{popcount}$ 就可以做到五步。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define ull __uint128_t
enum{NOT,AND,OR,XOR,LSH,RSH,POPC};
const uint N=1<<16;
ostream& operator <<(ostream& out,ull x){
int stk[50],top=0;
while(x){stk[++top]=x%10;x/=10;}
if (!top) top=1;
while(top) out<<stk[top--];
return out;
}
ull popc(ull x){
ull s=0;
for (int i=0;i<68;++i) s+=(x>>i)&1;
return s;
}
struct node{
int type;//NOT AND OR XOR LSH RSH POPCNT
bool fl,fr;
ull to,L,R;
void get(bool& fl,ull& x){
if (fl) cout<<"N ";cout<<x;
}
void output(){
cout<<to<<' ';
if (type==NOT) cout<<"NOT";
if (type==AND) cout<<"AND";
if (type==OR) cout<<"OR";
if (type==XOR) cout<<"XOR";
if (type==LSH) cout<<"LSH";
if (type==RSH) cout<<"RSH";
if (type==POPC) cout<<"POPCNT";
cout<<' ';get(fl,L);
if (type&&type<6){
cout<<' ';
get(fr,R);
}
cout<<'\n';
}
};
vector<node> ans;
void push(ull to,int type,bool fl,ull L,bool fr,ull R){ans.emplace_back((node){type,fl,fr,to,L,R});}
void solve(){
push(2,RSH,0,2,1,34);
push(1,AND,0,1,0,2);
push(1,POPC,0,1,0,0);
push(1,OR,0,1,1,8);
push(3,POPC,0,1,0,0);
}
uint id[4][4];
ull get(uint a[]){
ull S=0;
for (int i=0;i<3;++i) S|=(1<<i*6+id[a[i]][a[3]]);
S<<=16;
for (int i=0;i<4;++i) S|=1<<(i*4+a[i]);
return S;
}
void build(){
for (int s=0,i=0;i<4;++i) for (int j=i+1;j<4;++j) id[i][j]=id[j][i]=s++;
uint p[4],a[4];
for (int i=0;i<4;++i) p[i]=i;
for (int _=0;_<24;++_){
ull A,B;
for (int i=0;i<4;++i) a[i]=p[i];
A=get(a);
for (int i=0;i<4;++i) a[p[i]]=i;
B=get(a);
cout<<((B<<34)|A)<<'\n';
next_permutation(p,p+4);
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
build();
solve();
cout<<ans.size()<<endl;
for (auto x:ans) x.output();
return 0;
}
```