Link

reorder

[two pointers]

直接two pointers模拟即可

prefix

[Trie] [树状数组]

因为不存在某个单词是另一个单词的前缀，所以所有形成的字符串都是唯一的

那么可以直接按字典序重标号（用trie实现），问题就转化成了类似于康托展开的经典问题了

枚举在哪一位没卡到上限，BIT维护一下即可

monotony

太菜了，一道不是很难的题考场上没想出来。。。

Description

给出一个nn行mm列，由1∼n×m1\sim n\times m的排列构成的矩阵。你可以删去若干行、若干列，求有多少种方案满足删去后产生的新的矩阵满足每一行每一列都单调（单增或单减）

n,m≤20n, m\le 20

Solution

[动态规划] [计数] [状态压缩]

考虑先2n2^n枚举选哪些行，那么选择的列首先就必须要单调。然后问题转化为，选择若干列，使得每一行都单增

不难发现，只要确定了某一行的前两列，就确定了单调的方式（只考虑长度≥2\ge 2的情况）

设dp[i][S]dp[i][S]表示考虑到第ii列且选择第ii列，行的单调方式状态为SS的方案数。枚举前一列选了哪个，有转移：

dp[i][S]=∑j,S(dp[j][S]+1) dp[i][S] = \sum_{j, S} \big(dp[j][S] + 1\big)

看上去这个dp是O(n22n)O(n^22^n)的，但实际上枚举了jj后SS就已经确定了，所以并不需要枚举SS。因此dp的复杂度就只有O(n2)O(n^2)了

总复杂度O(n22n)O(n^22^n)

Code

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#pragma GCC optmize(2)
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 20 + 5, Maxs = (1 << 20) + 10;

int N, M;
int A[Maxn][Maxn], H[Maxn];
int State[Maxn][Maxn];
LL Dp[Maxn][Maxs];
LL ans;

inline void solve_l (int state, int len)
{
	static int Ban[Maxn];

	for (int i = 1; i <= M; ++i) Ban[i] = 0;

	for (int i = 1; i <= M; ++i)
	{
		int fg = 0;
		for (int j = 2; j <= len; ++j) if (A[H[j]][i] < A[H[j - 1]][i]) { ++fg; break; }
		for (int j = 2; j <= len; ++j) if (A[H[j]][i] > A[H[j - 1]][i]) { ++fg; break; }
		if (fg == 2) { Ban[i] = 1; continue; }

		for (int j = 1; j < i; ++j)
		{
			if (Ban[j]) continue;
			int S = state & State[i][j];
			Dp[i][S] += Dp[j][S] + 1;
			ans += Dp[j][S] + 1;
		}

		++ans;
	}

	for (int i = 2; i <= M; ++i)
		for (int j = 1; j < i; ++j)
		{
			int S = state & State[i][j];
			Dp[i][S] = 0;
		}

//	DEBUG (ans);
}

inline void dfs_h (int x, int state, int len)
{
	if (x == N + 1) 
	{ 
		if (!len) return ;
		solve_l (state, len); 
		return ; 
	}

	H[len + 1] = x;
	dfs_h (x + 1, state | (1 << (x - 1)), len + 1);
	dfs_h (x + 1, state, len);
}

inline void Init ()
{
	for (int i = 1; i <= M; ++i)
		for (int j = 1; j < i; ++j)
			for (int k = 1; k <= N; ++k) if (A[k][j] > A[k][i])
					State[i][j] |= 1 << (k - 1);
}

inline void Solve ()
{
	Init ();
	dfs_h (1, 0, 0);
	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>(), M = read<int>();
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			A[i][j] = read<int>();
}

int main()
{

#ifdef hk_cnyali
	freopen("C.in", "r", stdin);
	freopen("C.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}