LOJ

Cave Paitings

Solution

用并查集维护连通性，并记录一下当前这个联通块的方案数。依次枚举每一行，先把一行的联通块缩起来，再把上一行的信息并上来即可

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

#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#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 = 1000;
const int MOD = 1e9 + 7;

inline void ADD (int &a, int b) { if ((a += b) >= MOD) a -= MOD; }

int N, M;
char A[MAXN + 5][MAXN + 5];

namespace DSU
{
	const int maxn = MAXN * MAXN;

	int fa[maxn + 5], ans[maxn + 5];

	inline void init (int n) { for (int i = 1; i <= n; ++i) fa[i] = i, ans[i] = 1; }

	inline int get_fa (int x) { return fa[x] == x ? x : fa[x] = get_fa (fa[x]); }

	inline int get_ans (int x) { return ans[get_fa (x)]; }

	inline void link (int x, int y) // link y to x
	{
		x = get_fa (x), y = get_fa (y);
		if (x == y) return ;
		fa[y] = x;
		ans[x] = (LL) ans[x] * ans[y] % MOD;
	}

	inline void add (int x) { ADD (ans[get_fa(x)], 1); }
}

int Id[MAXN + 5][MAXN + 5];

inline void Solve ()
{
	for (int i = 1, tot = 0; i <= N; ++i) for (int j = 1; j <= M; ++j) Id[i][j] = ++tot;
	DSU :: init (N * M);

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= M; ++j) if (A[i][j] == '.' && A[i][j - 1] == '.')
			 DSU :: link (Id[i][j], Id[i][j - 1]);

		for (int j = 1; j <= M; ++j) if (A[i][j] == '.' && A[i - 1][j] == '.')
			DSU :: link (Id[i][j], Id[i - 1][j]);

		for (int j = 1; j <= M; ++j) if (A[i][j] == '.' && DSU :: get_fa (Id[i][j]) == Id[i][j])
			DSU :: add (Id[i][j]);
	}

	int ans = 1;
	for (int i = 1; i <= N * M; ++i) if (DSU :: get_fa (i) == i) ans = (LL) ans * DSU :: get_ans (i) % MOD;

	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>(), M = read<int>();
	for (int i = N; i >= 1; --i) scanf("%s", A[i] + 1);
}

int main ()
{

	freopen("cave.in", "r", stdin);
	freopen("cave.out", "w", stdout);

	Input ();
	Solve ();

	return 0;
}

Non-Decreasing Subsequences

Solution

暴力dp是f[i][j]f[i][j]表示到ii, 最后以jj结尾的方案数。因为jj很小，所以可以线段树维护矩阵直接做，但是复杂度不够优秀

考虑优化成线性，发现就是要求区间矩阵的乘积，考虑求出矩阵的前缀积及其逆矩阵。求逆矩阵可以类似线性求ifac的方法去做，即先正着求出所有前缀积，对最后一个矩阵求逆，再依次乘回来。所以复杂度瓶颈在于求矩阵的前缀积，以及回答询问

注意到本题的初始矩阵很特殊，只有对角线和某半列上有值。所以可以直接枚举有值的位置进行转移，具体细节可见代码，这里不多赘述。复杂度可降为O(nk2)O(nk^2)

询问同理，因为要求的值的位置很少，也可以优化到O(qk2)O(qk^2)。再通过前缀和优化一次即可做到O(qk)O(qk)

总复杂度O(nk2+qk)O(nk^2 + qk)

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#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 = 5e4;
const int MAXM = 2e5;
const int MAXK = 20;
const int MOD = 1e9 + 7;


namespace MATH
{
	inline void ADD (int &a, int b) { if ((a += b) >= MOD) a -= MOD; }

	inline int Pow (int a, int b)
	{
		int ans = 1;
		for (int i = b; i; i >>= 1, a = (LL) a * a % MOD) if (i & 1) ans = (LL) ans * a % MOD;
		return ans;
	}
}

using namespace MATH;

int N, K, Q;

struct matrix
{
	int A[MAXK + 1][MAXK + 1];

	inline int* operator [] (const int &x) { return A[x]; }

	inline matrix () { memset (A, 0, sizeof A); }

} prefix[MAXN + 5], iprefix[MAXN + 5];

inline matrix get_inv (matrix A)
{
	matrix I;
	for (int i = 1; i <= K; ++i) I[i][i] = 1;

	for (int i = 1; i <= K; ++i)
	{
		for (int j = i; j <= K; ++j) if (A[i][j])
		{
			for (int k = 1; k <= K; ++k) swap (A[i][k], A[j][k]), swap (I[i][k], I[j][k]);
			break;
		}

		int res = Pow (A[i][i], MOD - 2);
		for (int j = 1; j <= K; ++j)
		{
			A[i][j] = (LL) A[i][j] * res % MOD;
			I[i][j] = (LL) I[i][j] * res % MOD;
		}

		for (int j = 1; j <= K; ++j) if (i != j)
		{
			int tmp = A[j][i];
			for (int k = i; k <= K; ++k) 
			{
				ADD (A[j][k], MOD - (LL) tmp * A[i][k] % MOD);
				ADD (I[j][k], MOD - (LL) tmp * I[i][k] % MOD);
			}
		}
	}

	return I;
}

int A[MAXN + 5];

inline void Init ()
{
	for (int i = 1; i <= N; ++i) prefix[0][i][i] = 1;

	for (int i = 1; i <= N; ++i) 
	{
		int x = read<int>(); A[i] = x;

		prefix[i] = prefix[i - 1];
		for (int j = 1; j <= x; ++j)
			for (int k = 1; k <= K; ++k)
				ADD (prefix[i][k][x], prefix[i - 1][k][j]);
	}

	iprefix[N] = get_inv (prefix[N]);

	for (int i = N - 1; i >= 0; --i)
	{
		int x = A[i + 1];

		iprefix[i] = iprefix[i + 1];

		for (int j = 1; j <= x; ++j)
			for (int k = 1; k <= K; ++k)
				ADD (iprefix[i][j][k], iprefix[i + 1][x][k]);
	}
}

int Sum[MAXN + 5][MAXK + 1];

inline void Solve ()
{
	Init ();

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= K; ++j)
			for (int k = 1; k <= K; ++k) 
				ADD (Sum[i][j], prefix[i][j][k]);
	}

	Q = read<int>();
	while (Q--)
	{
		int l = read<int>(), r = read<int>();

		int ans = 0;
		for (int i = 1; i <= K; ++i) ADD (ans, (LL) iprefix[l - 1][1][i] * Sum[r][i] % MOD);

		printf("%d\n", ans);
	}
}

inline void Input ()
{
	N = read<int>(), K = read<int>();
}

int main ()
{

	freopen("nondec.in", "r", stdin);
	freopen("nondec.out", "w", stdout);

	Input ();
	Solve ();

	return 0;
}

Falling Portals

Solution

solution from jambow

20-2-4-1

20-2-4-2

20-2-4-3

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#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 = 2e5;

int N, Q[MAXN + 5];
pii Ans[MAXN + 5];

int Pos[MAXN + 5];
pii A[MAXN + 5], stk[MAXN + 5];

inline int cmp1 (const pii &a, const pii &b) { return a.y == b.y ? a.x > b.x : a.y > b.y; }
inline int cmp2 (const pii &a, const pii &b) { return a.y == b.y ? a.x < b.x : a.y < b.y; }

inline pii operator - (const pii &a, const pii &b) { return mp (a.x - b.x, a.y - b.y); }

inline LL cross (pii o, pii a, pii b)
{
	a = a - o, b = b - o;
	return (LL) a.x * b.y - (LL) a.y * b.x;
}

inline void solve1 ()
{
	sort (A + 1, A + N + 1, cmp1);
	for (int i = 1; i <= N; ++i) Pos[A[i].x] = i;

	int top = 0;
	for (int i = 1; i <= N; ++i)
	{
		while (top && stk[top].x < A[i].x) --top;
/**/	while (top > 1 && cross (A[i], stk[top - 1], stk[top]) > 0) --top;
		stk[++top] = A[i];

		if (A[Pos[Q[A[i].x]]].y <= A[i].y)
		{
			pii to = mp (A[Pos[Q[A[i].x]]].x, A[Pos[Q[A[i].x]]].y);
			int l = 1, r = top, ans = 0;
			while (l <= r)
			{
				int mid = (l + r) >> 1;
				if (stk[mid].x > to.x && (mid == 1 || cross (to, stk[mid], stk[mid - 1]) >= 0)) ans = mid, l = mid + 1;
				else r = mid - 1;
			}

			if (ans) Ans[A[i].x] = stk[ans] - to;
		}
	}
}

inline void solve2 ()
{
	sort (A + 1, A + N + 1, cmp2);
	for (int i = 1; i <= N; ++i) Pos[A[i].x] = i;

	int top = 0;
	for (int i = 1; i <= N; ++i)
	{
		while (top && stk[top].x > A[i].x) --top;
		while (top > 1 && cross (A[i], stk[top - 1], stk[top]) > 0) --top;
		stk[++top] = A[i];

		if (A[Pos[Q[A[i].x]]].y > A[i].y)
		{
			pii to = mp (A[Pos[Q[A[i].x]]].x, A[Pos[Q[A[i].x]]].y);
			int l = 1, r = top, ans = 0;
			while (l <= r)
			{
				int mid = (l + r) >> 1;
				if (stk[mid].x < to.x && (mid == 1 || cross (to, stk[mid], stk[mid - 1]) >= 0)) ans = mid, l = mid + 1;
				else r = mid - 1;
			}

			if (ans) Ans[A[i].x] = to - stk[ans];
		}
	}
}

inline void Solve ()
{
	for (int i = 1; i <= N; ++i) Ans[i].x = -1;
	solve1 ();
	solve2 ();

	for (int i = 1; i <= N; ++i) 
		if (Ans[i].x == -1) puts("-1");
		else printf("%d/%d\n", Ans[i].y / __gcd (Ans[i].x, Ans[i].y), Ans[i].x / __gcd (Ans[i].x, Ans[i].y));
}

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

int main ()
{

	freopen("falling.in", "r", stdin);
	freopen("falling.out", "w", stdout);

	Input ();
	Solve ();

	return 0;
}