ARC158F 题解

First Post:

Last Update:

感觉转化限制的那一步比较难，和题解想的不大一样，怎么都难以优化。

首先观察一个操作序列，显然，只有每个数位最后一次出现的位置是有用的。假设操作序列中一共出现了 种数位，那么可以设一个大小为 的排列 ， 表示数位 最后一次出现的位置排在第几名（也就是这个关键字第几个被考虑到）。

显然，一个排列能被多少个操作序列生成只与排列大小 有关，因为每一位的地位是相同的。进一步地，方案数就是 。分子是第二类斯特林数，表示将每次操作分配给一个数位，每种数位都必须出现。这个斯特林数包含了所有大小为 的排列，单个排列的方案除以阶乘即可。

接下来考虑什么样的排列 能生成序列 。我们只需让 排在 的前面，而不需要尝试保证任何 都在 前面。

考虑一对 和 ，对于每个关键字，存在一些位 满足 ，令这些位组成的集合为 。存在一些位 满足 ，令这些位组成的集合为 。那么对于任意 ，都必须存在一个 使得 比 先作为依据进行排序。另外，如果 和 在 中的出现位置是逆序，那么整个过程中也必须以 中的某个 为依据进行排序。（代码中将 出现的位置也当作一个关键字处理了）

那么，设 表示 集合中是否存在一个必须比 先作为依据排序的关键字。在处理一对 时，先将 赋值为 。再对 做一遍高维前缀或即可处理出 数组。

那么生成原来的排列 也很简单了。按照高优先级到低优先级的顺序进行 DP。设 表示当前已经以 中的关键字为依据排序过的可行排列数。转移时枚举 ，使得 为假，转移到 即可。

时间复杂度 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5,Sz = (1 << 18) | 5,P = 998244353,MxK = 20;
inline void Plus(int &a,const int &b) { a += b;if(a >= P) a -= P;}
inline int qpow(int a,int b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
typedef long long ll;
int n,m,K;
ll a[N],b[N];
bool h[MxK][Sz];
int dp[Sz];

inline int C(int n,int m) {
	if(n < 0 || m < 0 || n < m) return 0;
	int res = 1;
	for(int i = n - m + 1;i <= n;i++) res = 1ll * res * i % P;
	for(int i = 1;i <= m;i++) res = 1ll * res * qpow(i,P - 2) % P;
	return res;
}
inline int Strling(int n,int m) {
	if(n < 0 || m <= 0 || n < m) return 0;
	int res = 0;
	for(int i = 0;i <= m;i++)
		if(i & 1) Plus(res,P - 1ll * C(m,i) * qpow(m - i,n) % P);
		else Plus(res,1ll * C(m,i) * qpow(m - i,n) % P);
	return res;
}
ll Pow10[MxK];
inline int Get(ll x,int v) { return (x / Pow10[v]) % 10;} // v 从 0 开始为最低位
int f[N],g[N];
int keys[N][MxK];
map<ll,vector<int> > aps;

int main() {
	cin >> n >> m >> K;
	for(int i = 1;i <= n;i++) cin >> a[i],aps[a[i]].push_back(i);
	for(int i = 1;i <= n;i++) cin >> b[i];
	Pow10[0] = 1;
	for(int i = 1;i <= K;i++) Pow10[i] = 10ll * Pow10[i - 1];
	for(int i = n;i >= 1;i--) {
		for(int j = 0;j < K;j++)
			keys[i][j] = Get(b[i],j);
		keys[i][K] = aps[b[i]].back();
		aps[b[i]].pop_back();
	}
	for(int i = 1;i <= K;i++) {
		f[i] = Strling(m,i);
		for(int j = 1;j <= i;j++)
			f[i] = 1ll * f[i] * qpow(j,P - 2) % P;
	}
	for(int i = 1;i < n;i++) {
		int S = 0,T = 0;
		for(int j = 0;j <= K;j++) {
			if(keys[i][j] < keys[i + 1][j] && j < K) S |= (1 << j);
			if(keys[i][j] > keys[i + 1][j]) T |= (1 << j);
		}
		for(int j = 0;j <= K;j++)
			if(T >> j & 1)
				h[j][S] = 1;
	}
	auto PreSum = [&](int id) {
		for(int k = 1;k < (1 << K);k <<= 1)
			for(int j = 0;j < (1 << K);j += k + k)
				for(int t = 0;t < k;t++)
					h[id][j | t | k] |= h[id][j | t];
	};
	for(int i = 0;i <= K;i++) PreSum(i);
	dp[0] = 1;
	for(int S = 0;S < (1 << K);++S) {
		for(int i = 0;i <= K;i++) 
			if(!h[i][(1 << K) - 1 - S] && (~S >> i & 1)) {
				if(i == K) Plus(g[__builtin_popcount(S)],dp[S]);
				else Plus(dp[S | (1 << i)],dp[S]);
			}
	}
	int ans = 0;
	for(int i = 0;i <= K;i++)
		Plus(ans,1ll * f[i] * g[i] % P);
	cout << ans << endl;
	return 0;
}
≡