专栏文章

题解：AT_arc158_f [ARC158F] Random Radix Sort

DDovish
AT_arc158_f题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miph3vvt
此快照首次捕获于
2025/12/03 11:54
3 个月前
此快照最后确认于
2025/12/03 11:54
3 个月前
查看原文
首先，我们把 bb 拆开，下文中 vali,jval_{i,j} 表示 bjb_j 的第 ii 位。
我们观察一下发现，对于每一位的每一个交换，只有最后一步是有意义的，故本质不同的操作序列只有 O(k!)O(k!) 个。
并且我们可以观察到，这个操作本质上是一种基数排序，以操作的最后一位的第一关键字，倒数第二位为第二关键字……如此类推。
先考虑暴力做法 O(k!knlog⁡n)O(k!kn\log n) 求出哪些本质不同的操作是合法的。
然后再反推多少个序列满足“每种操作的最后一次操作”的顺序是我们想要的。
我们可以直接设 fi,jf_{i,j} 表示考虑到第 ii 位，有 jj 个位置已经被钦定了不能选。
转移就是：
fi,j×(k−j)→fi+1,jfi,j→fi+1,j+1f_{i,j}\times (k-j)\to f_{i+1,j}\\ f_{i,j}\to f_{i+1,j+1}\\
最终 fm,kf_{m,k} 就是我们想要的答案。
显然可以矩阵快速幂优化。
注意，可能存在最终操作序列没有用到 kk 种元素的情况，所以对于每一个 i∈[1,k]i\in[1,k] 都要求一遍上式。
这一步的复杂度是 O(k4log⁡m)O(k^4\log m)。
继续考虑怎么求出合法的操作序列。
对于排列相关的计数，容易想到状压 DP。
我们对于本质不同操作计数：
从后往前已经考虑了的数位的集合为 xx，下一个希望插入的位置是 ii，集合 xx 中每一个数位构成的连续段的开头位置的集合的并为 SS。当且仅当 SS 和满足 vali,j≥vali,j−1val_{i,j}\ge val_{i,j-1} 的 jj 的集合的并为全集时，ii 可以接到 xx 前边。
那么我们怎么快速求一个集合 xx 能否转移到任意一个 ii 呢？正着做是困难的，考虑求不能转移的情况：一个集合 xx 不能转移到 ii，当且仅当存在一个 jj 使得上 xx 集合的每一个 ll 都满足 vall,j=vall,j−1val_{l,j}=val_{l,j-1} 且 vali,j<vali,j−1val_{i,j}<val_{i,j-1}。
于是直接分讨每一个位置即可，用一个高维前缀和求出转移矩阵。
然后DP计数就是直接按照转移矩阵去做就是简单的了。
故总复杂度 O(k4log⁡m+(2k+n)k2)O(k^4\log m+(2^k+n)k^2)。

代码

CPP
#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";
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...