给出一个三角剖分的nn边形

定义一次操作(a,c)(a, c)：若存在1≤a<b<c<d≤n1\le a < b < c < d \le n，满足(a,b),(b,c),(c,d),(a,d),(a,c)(a, b), (b, c), (c, d), (a, d), (a, c)有边，则可以删掉边(a,c)(a, c)，连上边(b,d)(b, d)

定义目标状态为不能进行任何操作的多边形，问至少需要多少次操作才能到达目标状态，并求出方案数对109+710^9 + 7取模的值

另外，还有mm次询问

每次给出一个合法的操作(a,c)(a, c)，求在初始状态先操作(a,c)(a, c)后得到的多边形的答案，询问之间互不影响

n,m≤105n, m\le 10^5

LOJ 3056

Solution

显然，最优策略每次的d=nd=n，目标状态就是全都连到nn号点上，长这样子：

19-5-8-1

因此第一问的答案就是除了边界外，两个端点均没有与nn相连的边数

考虑一开始所有与nn相连的点，将它们排序后，对于任意一对相邻的点(l,r)(l, r)，一定存在边(l,r)(l, r)

且若l+1≠rl + 1 \ne r，则在ll到rr中必然存在且仅存在一个点pp，满足(l,p)(l, p)有边，(p,r)(p, r)有边

那么操作(l,r)(l, r)的话，就能连上(p,n)(p, n)，且接下来(l,r)(l, r)就被拆分成(l,p)(l, p)和(p,r)(p, r)两个独立的部分，递归处理

19-5-8-2

不难发现，这形成了一棵树形结构，且以初始局面下所有l+1<rl+1<r的边(l,r)(l,r)作为树根，即可得到一片二叉树森林。（考场上没时间了，没想到是二叉树，以为每一层都和第一层一样可能有多个儿子）其中每个点必须在它父亲之后操作。

这样的方案数可以树形dp，通过直接计算合并两棵子树的方案数来得到

具体来说，考虑隔板法，把右子树中的点插到左子树点的序列中。这并不需要考虑左右子树内部的顺序，因为在递归到左右子树的时候已经考虑过了

对于任意一次询问，因为操作需要满足1≤a<b<c<d≤n1\le a < b < c < d \le n，发现只有两种合法情况：

  • 最优策略下操作了一步使得最优步数减1

    即将这个点（在森里中一定是根）删去，其左右儿子分别作为两棵新的二叉树的根

  • 对某个点（一定是左儿子）进行了一次rotaterotate操作，不改变最优步数

这两种情况本质都是把原来的某些边断掉，并连上新的边。用组合数和逆元算一下即可

Summary

  • 挖掘题目中隐含的更深的性质
  • 运用dp的思想来计数，把原问题拆分成若干个子问题，计算每个子问题对答案的贡献，再利用乘法原理合并

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
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

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

template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline int Chkmax (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 = 1e5 + 100;
const int Mod = 1e9 + 7;

int OP, N, M, ans_cnt;

vector <int> G[Maxn];

inline void add_edge (int x, int y) { G[x].pb (y), G[y].pb (x); }

namespace MATH
{
	int fac[Maxn], ifac[Maxn];

	inline int fpm (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;
	}
	inline int C (int n, int m) { return (LL) fac[n] * ifac[m] % Mod * ifac[n - m] % Mod; }
	inline int InvC (int n, int m) { return (LL) ifac[n] * fac[m] % Mod * fac[n - m] % Mod; }
	inline void init (int n)
	{
		fac[0] = 1;
		for (int i = 1; i <= n; ++i) fac[i] = (LL) fac[i - 1] * i % Mod;
		ifac[n] = fpm (fac[n], Mod - 2);
		for (int i = n - 1; i >= 0; --i) ifac[i] = (LL) ifac[i + 1] * (i + 1) % Mod;
	}
}

using MATH :: C;
using MATH :: InvC;

inline int Calc (int l, int r)
{
	if (l + 1 == r) return 1;
	int mid = *lower_bound (G[r].begin(), G[r].end(), l + 1);
	return (LL) C (r - l - 2, mid - l - 1) * Calc (l, mid) % Mod * Calc (mid, r) % Mod;
}

inline void Solve ()
{
	int step = 0, ans = 1;

	for (int i = 1; i < G[N].size(); ++i)
	{
		int x = G[N][i - 1], y = G[N][i], sum = y - x - 1;
		ans = (LL) ans * C (step + sum, sum) % Mod;
		ans = (LL) ans * Calc (x, y) % Mod;
		step += sum;
	}

	if (!OP) cout << step << endl;
	else cout << step << ' ' << ans << endl;

	M = read<int>();

	while (M--)
	{
		int x = read<int>(), y = read<int>(), step_now = step, ans_now = ans;

		int l = *lower_bound (G[y].begin(), G[y].end(), x + 1);
		int r = *lower_bound (G[x].begin(), G[x].end(), y + 1);
		int sum_all = y - x - 1, lsum = l - x - 1, rsum = y - l - 1;

		if (r == N)
		{
			--step_now;
			ans_now = (LL) ans_now * InvC (step, sum_all) % Mod;
			ans_now = (LL) ans_now * InvC (lsum + rsum, lsum) % Mod;
			ans_now = (LL) ans_now * C (step_now - rsum, lsum) % Mod;
			ans_now = (LL) ans_now * C (step_now, rsum) % Mod;
		}
		else
		{
			int lsum_f = y - x - 1, rsum_f = r - y - 1;
			int rsum_new = r - l - 1;
			ans_now = (LL) ans_now * InvC (lsum + rsum, lsum) % Mod;
			ans_now = (LL) ans_now * InvC (lsum_f + rsum_f, lsum_f) % Mod;
			ans_now = (LL) ans_now * C (rsum + rsum_f, rsum) % Mod;
			ans_now = (LL) ans_now * C (lsum + rsum_new, lsum) % Mod;
		}

		if (OP) printf("%d %d\n", step_now, ans_now);
		else printf("%d\n", step_now);
	}
}

inline void Input ()
{
	OP = read<int>();
	MATH :: init (N = read<int>());

	for (int i = 1; i <= N - 3; ++i)
	{
		int x = read<int>(), y = read<int>();
		add_edge (x, y);
	}
	for (int i = 1; i <= N; ++i) add_edge (i, i % N + 1);

	for (int i = 1; i <= N; ++i) sort (G[i].begin (), G[i].end ());
}

int main ()
{
#ifndef ONLINE_JUDGE
	freopen("polygon.in", "r", stdin);
	freopen("polygon.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}