P13086 题解

· · 题解

1-index 比较没法做，使用 0-index。

直接求排列复合看上去就不太能压进 49 次操作，需要尝试不一样的做法。

现在考虑 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\} 很好处理。

现在需要做两件事：首先，根据输入求出 a_i=[p_i=q'_i] 和 b=[\exists (i,j)\ \text{s.t.}\ \{p_i,p_j\}=\{q'_i,q'_j\}]（可以枚举所有情况证明只需要这几个东西就能唯一确定置换环个数）；然后，用这五个输入求出最终的答案。

首先需要一个编码系统把 p_i 和 p'_i 一起压进 16 个二进制位里面（用位运算求逆排列比较困难），那只能用两个二进制位记录一个数，最终变成 \overline{p_3p_2p_1p_0p'_3p'_2p'_1p'_0p'_3p'_2p'_1p'_0p_3p_2p_1p_0} 的形式。

这里一个数的两个二进制位被拆开了。代码中，p_i 高位在前低位在后，p'_i 低位在前高位在后（这个应该不重要）。编码方式非常反直觉，但是为了最优化操作次数需要这么做。

现在对排列 p，记 P_0=\{i\mid p_i\bmod 2\equiv 1\},P_1=\{i\mid p_i\ge 2\}。对于 q，记 Q_0=\{i\mid q'_i\bmod 2\equiv 1\},Q_1=\{i\mid q'_i\ge 2\}。

显然这四个东西在那个 16 位二进制数中对应的都是除以 4 余数相同的四个二进制位，因而都能用位运算快速求出，需要 7 次操作（四次按位与，三次右移操作把它们对齐）。

实际上，通过精细实现可以只用一个按位与操作。这需要用右移操作消掉没有用的二进制位。

下面计算 a_i。易得

\begin{aligned} a_0&=|(\overline{P_0}\cap \overline{Q_0})\cap(\overline{P_1}\cap \overline{Q_1})|\\ a_1&=|(P_0\cap Q_0)\cap(\overline{P_1}\cap \overline{Q_1})|\\ a_2&=|(\overline{P_0}\cap \overline{Q_0})\cap(P_1\cap Q_1)|\\ a_3&=|(P_0\cap Q_0)\cap(P_1\cap Q_1)| \end{aligned}

由于排列的性质，求交之后的结果至多只有一个位为 1；并且，如果几个 a_i 都非零，那它们对应集合的 1 的位置互不相同。

发现四个集合的并可以写成

\overline{(P_0\ \Delta\ Q_0)\cup(P_1\ \Delta\ Q_1)}

其中 \Delta 为对称差运算，可以理解为“按位”异或。这样就可以简单求解了。

现在需要求出 b。将 b 分成三部分，分别判断 (1,3),(2,3),(1,2) 是否合法，设这三个值为 b_0,b_1,b_2。

发现 b_0=[|P_0\cap Q_0|\ge 2],b_1=[|P_1\cap Q_1|\ge 2]，这个很简单。

最复杂的情况是 b_2，它等于 [|(P_0\ \Delta\ P_1)\cap(Q_0\ \Delta\ Q_1)|\ge 2]。

将三个 b_i 按位或即可得到 b。注意这里不要急着判断集合大小是否 \ge 2，可以按位或（类似取 \max）以后判断。

最后发现答案为 \frac{\sum a_i+b+3}{2}，直接计算即可。注意这里算加法的方式是把数分拆到不同的二进制位里面按位或，然后求 \mathrm{popcount}。

如果实现足够精细，可以做到 24 次。

当然，因为使用右移操作对齐，所以算出来的 a_i 在最低的几个二进制位上，需要一次额外的操作左移。这一步显然是可以省下来的，进而做到 23 次。

接着卡常可以做到 22 次。

这里只给出 24 次操作的代码。（这份代码也可以通过 P13087——双倍经验！！！）

#include<bits/stdc++.h>
using namespace std;
#define uint unsigned int
enum{NOT,AND,OR,XOR,LSH,RSH,POPC};
const uint N=1<<16,K=15;
struct node{
    int type;//NOT AND OR XOR LSH RSH POPCNT
    bool fl,fr;
    uint to,L,R;
    void get(bool& fl,uint& 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(uint to,int type,bool fl,uint L,bool fr,uint R){ans.emplace_back((node){type,fl,fr,to,L,R});}
void build(){
    int p[4]={0,1,2,3},iv[4];
    for (int i=0;i<24;++i){
        uint s=0,t=0;
        for (int j=0;j<4;++j){s|=p[j]<<(j*4);iv[p[j]]=j;}
        for (int j=0;j<4;++j) s|=iv[j]<<(j*4+2);
        t=s;s=0;
        for (int o=0;o<4;++o) for (int p=0;p<4;++p) if ((t>>o*4+p)&1) s|=1<<o+p*4;
        t=s;s=0;
        for (int i=0;i<16;++i) if ((t>>i)&1){
            if (i&4) s|=1<<(i^8);
            else s|=1<<i;
        }
        cout<<s<<'\n';
        next_permutation(p,p+4);
    }
}
uint x[4]={4,5,6,7},y[4]={8,9,10,11},a[4]={12,13,14,15},b[6]={16,17,18,19,20,21},c[4]={22,23,24,25},A4=a[0],A2=a[1],A1=a[3],A0=a[2],A=1,B=27,C=26,D=2,A21=b[0],A20=8,A11=b[1],A10=9,P=28,Q=29;
void solve(){
    push(B,RSH,0,D,1,8);
    push(D,RSH,0,D,1,4);
    push(C,RSH,0,A,1,12);
    push(A,AND,0,A,1,K);

    push(99,XOR,0,A,0,C);
    push(100,XOR,0,B,0,D);
    push(b[2],AND,0,99,0,100);
    push(a[0],XOR,0,C,0,D);
    push(a[1],XOR,0,A,0,B);
    push(A21,AND,0,C,0,D);
    push(A11,AND,0,A,0,B);
    for (int i=0;i<3;++i) push(b[i],POPC,0,b[i],0,0);
}
void calc(){
    push(3,OR,0,a[0],0,a[1]);
    push(3,XOR,0,3,1,K);
    push(3,AND,0,3,1,K);
    push(3,LSH,0,3,1,4);
    for (int i=0;i<3;++i) push(3,OR,0,3,0,b[i]);
    push(3,OR,0,3,1,13);
    push(3,POPC,0,3,0,0);
    push(3,RSH,0,3,1,1);
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    build();
    solve();
    calc();
    cout<<ans.size()<<endl;
    for (auto x:ans) x.output();
    return 0;
}