题解：AT_arc158_f [ARC158F] Random Radix Sort

· · 题解

首先，我们把 b 拆开，下文中 val_{i,j} 表示 b_j 的第 i 位。

我们观察一下发现，对于每一位的每一个交换，只有最后一步是有意义的，故本质不同的操作序列只有 O(k!) 个。

并且我们可以观察到，这个操作本质上是一种基数排序，以操作的最后一位的第一关键字，倒数第二位为第二关键字……如此类推。

先考虑暴力做法 O(k!kn\log n) 求出哪些本质不同的操作是合法的。

然后再反推多少个序列满足“每种操作的最后一次操作”的顺序是我们想要的。

我们可以直接设 f_{i,j} 表示考虑到第 i 位，有 j 个位置已经被钦定了不能选。

转移就是：

f_{i,j}\times (k-j)\to f_{i+1,j}\\ f_{i,j}\to f_{i+1,j+1}\\

最终 f_{m,k} 就是我们想要的答案。

显然可以矩阵快速幂优化。

注意，可能存在最终操作序列没有用到 k 种元素的情况，所以对于每一个 i\in[1,k] 都要求一遍上式。

这一步的复杂度是 O(k^4\log m)。

继续考虑怎么求出合法的操作序列。

对于排列相关的计数，容易想到状压 DP。

我们对于本质不同操作计数：

从后往前已经考虑了的数位的集合为 x，下一个希望插入的位置是 i，集合 x 中每一个数位构成的连续段的开头位置的集合的并为 S。当且仅当 S 和满足 val_{i,j}\ge val_{i,j-1} 的 j 的集合的并为全集时，i 可以接到 x 前边。

那么我们怎么快速求一个集合 x 能否转移到任意一个 i 呢？正着做是困难的，考虑求不能转移的情况：一个集合 x 不能转移到 i，当且仅当存在一个 j 使得上 x 集合的每一个 l 都满足 val_{l,j}=val_{l,j-1} 且 val_{i,j}<val_{i,j-1}。

于是直接分讨每一个位置即可，用一个高维前缀和求出转移矩阵。

然后DP计数就是直接按照转移矩阵去做就是简单的了。

故总复杂度 O(k^4\log m+(2^k+n)k^2)。

代码

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define per(i,a,b) for(register int i=(a);i>=(b);--i)
#define edge(i,u) for(int i=head[u];i;i=e[i].next)
#define lc (u<<1)
#define rc (u<<1|1)
#define pii pair<int,int>
#define pdd pair<double,double>
#define mp make_pair
#define pb push_back
#define fst first
#define sed second
using namespace std;
const int N=2e5+10,M=1e6+10,inf=1e9,mod=998244353;
int qpow(int a,int b){int res=1;while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}return res;}
int inv(int a){return qpow(a,mod-2);}
void Mul(int&a,int b){a=1ll*a*b%mod;}
void Add(int&a,int b){a+=b;if(a>=mod)a-=mod;}
void Dec(int&a,int b){a-=b;if(a<0)a+=mod;}
int mul(int a,int b){return 1ll*a*b%mod;}
int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
int dec(int a,int b){return a-b<0?a-b+mod:a-b;}
struct matrix
{
    int f[19][19];
    matrix(){memset(f,0,sizeof f);}
    void init(){memset(f,0,sizeof f);}
    int*operator[](int x){return f[x];}
    matrix operator*(const matrix&b)const
    {
        matrix c;
        rep(i,0,18)
        rep(k,0,18)
        {
            int val=f[i][k];
            rep(j,0,18)
            Add(c.f[i][j],mul(val,b.f[k][j]));
        }
        return c;
    }
};
bool MS;int used;
int n,m,k;
int a[N],b[N];
bitset<N>g[19],h[19];
int val[N][19];
int base[19];
int f[N][19];
bool tr[(1<<18)][19];//i状态转移到j的可行性 (0为可行!1为不行!)
int dp[(1<<18)];
void init()
{
    rep(w,1,k)
    {
        matrix res,trans;
        res[0][0]=1;
        trans[0][0]=w;
        rep(i,1,w)
        {
            trans[i-1][i]=1;
            trans[i][i]=w-i;
        }
        int b=m;
        while(b)
        {
            if(b&1)res=res*trans;
            trans=trans*trans;
            b>>=1;
        }
        base[w]=res[0][w];
    }
}
map<int,queue<int>>pos;
int ans;
bool MT;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    init();
    rep(i,1,n)
    {
        cin>>a[i];
        pos[a[i]].push(i);
    }
    rep(i,1,n)
    {
        cin>>b[i];
        int now=b[i];
        if(!pos[b[i]].size())
        return cout<<0,0;
        val[i][k]=pos[b[i]].front();
        pos[b[i]].pop();
        rep(j,0,k-1)
        {
            val[i][j]=now%10;
            now/=10;
        }
    }
    rep(j,0,k)
    rep(i,1,n)
    {
        g[j][i]=(val[i][j]>=val[i-1][j]);
        h[j][i]=(val[i][j]!=val[i-1][j]);//每一段的开头 
    }
    rep(j,0,k)
    rep(i,1,n)
    if(!g[j][i])
    {
        int base=0;
        rep(l,0,k-1)
        if(!h[l][i])base|=(1<<l);
        tr[base][j]=1;
    }
    rep(j,0,k)
    {
        per(i,(1<<k)-1,0)
        if(tr[i][j])
        {
            rep(l,0,k-1)
            if((1<<l)&i)
            tr[i^(1<<l)][j]=1;
        }
    }
    dp[0]=1;
    rep(i,0,(1<<k)-1)
    {
        rep(j,0,k-1)
        if((tr[i][j]^1)&&!(i&(1<<j)))
        dp[i|(1<<j)]+=dp[i];
        if(tr[i][k]^1)//可以转移到初始状态，即是合法状态
        ans+=dp[i]%mod*base[__builtin_popcount(i)]%mod;
    }
    cout<<ans%mod<<'\n';
    cerr<<"Memory:"<<(&MS-&MT)/1048576.0<<"MB Time:"<<clock()/1000.0<<"s\n";
}