PAROVI

QwQ__ · 2022-08-24 13:57:21 · 题解

题意

给定一个正整数 n ,表示你每次可以从1到N这些自然数中取两个互质且不同的数出来构成一个数对，例如：n＝5 时，你可以取 {{1，2}，{3，4}，{2，5}，{3，5}} 等，且数对不能重复。如果存在一个数X（2<=X<=N）,使得每个数对均满足a,b<X 或a,b>=X，则你的取法不合法。例如：你的数对如下 {{1，2}{3，4}}，则X等于3时，这两个数对均满足以上条件，所以方案不合法。计算有多少种合法的取法，答案对 1000000000 取余。

题解

对于一个点对(a,b)，我们将他视为覆盖区间[a,b] 那么问题就转化成了覆盖[1,n]的方案数。