题目传送门

思路：

首先观察对排列的三种操作，发现总共就 $8$ 种状态，所以考虑打表预处理。

由于反转与取反的代价形如 $N(t)=n+1-t$。而求逆不增加新形式，所以对于代价 $s_n$ 有：

$$s_0:(y,x)\longrightarrow \sum i^{p_i}$$ $$s_1:(y,N(x))\longrightarrow \sum (n+1-i)^{p_i}$$ $$s_2:(N(y),x)\longrightarrow \sum i^{n+1-p_i}$$ $$s_3:(N(y),N(x))\longrightarrow \sum (n+1-i)^{n+1-p_i}$$$$s_4:(x,y)\longrightarrow \sum p_i^i$$ $$s_5:(N(x),y)\longrightarrow \sum p_i^{n+1-i}$$ $$s_6:(x,N(y))\longrightarrow \sum (n+1-p_i)^{i}$$ $$s_7:(N(x),N(y))\longrightarrow \sum (n+1-p_i)^{n+1-i}$$

然后对于状态转移 $tra$ 也只有 $8$ 种，继续打表就好啦：

$$tra_0 \longrightarrow \{1,2,4\}$$ $$tra_1 \longrightarrow \{0,3,5\}$$ $$tra_2 \longrightarrow \{3,0,6\}$$ $$tra_3 \longrightarrow \{2,1,7\}$$ $$tra_4 \longrightarrow \{6,5,0\}$$ $$tra_5 \longrightarrow \{7,4,1\}$$ $$tra_6 \longrightarrow \{4,7,2\}$$ $$tra_7 \longrightarrow \{5,6,3\}$$

最后处理就简单啦。

std：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MOD=998244353;

int cal(ll base, int exp)
{
    ll res=1;
    base%=MOD;
    while(exp>0)
    {
        if(exp&1) res=(res*base)%MOD;
        base=(base*base)%MOD;
        exp>>=1;
    }
    return (int)res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<int> p(n);
    for(int i=0;i<n;i++) cin>>p[i];
    vector<ll> s(8,0);
    for(int i=1;i<=n;i++)
    {
        int x=i;
        int y=p[i-1];
        int nx=n+1-x;
        int ny=n+1-y;
        ll v0=cal(y,x);
        ll v1=cal(y,nx);
        ll v2=cal(ny,x);
        ll v3=cal(ny,nx);
        ll v4=cal(x,y);
        ll v5=cal(nx,y);
        ll v6=cal(x,ny);
        ll v7=cal(nx,ny);
        s[0]=(s[0]+v0)%MOD;
        s[1]=(s[1]+v1)%MOD;
        s[2]=(s[2]+v2)%MOD;
        s[3]=(s[3]+v3)%MOD;
        s[4]=(s[4]+v4)%MOD;
        s[5]=(s[5]+v5)%MOD;
        s[6]=(s[6]+v6)%MOD;
        s[7]=(s[7]+v7)%MOD;
    }
    int tra[8][3]={
        {1,2,4},
        {0,3,5},
        {3,0,6},
        {2,1,7},
        {6,5,0},
        {7,4,1},
        {4,7,2},
        {5,6,3}
    };
    int cur=0;
    for(int i=0;i<q;i++)
    {
        int op;
        cin>>op;
        cur=tra[cur][op-1];
        cout<<s[cur]<<" ";
    }
    return 0;
}

作者的话：

求过求赞，打表很累的qwq。