OI - CSP2019模拟赛 Day2 B

怎么又是一道容斥……


Part1. 题面

有一个正 n 边形(n 是奇数),你要在上面选择 m 个不同顶点,使得这 m 个点围成的凸多边形 恰好 包含 k 个锐角。

给出 n,m,k;问有多少种不同的选择方案,两个方案被认为不同当且仅当两个方案所选取的顶点集合不同。

请注意,你需要回答 q 组询问(每组询问给出 n,m,k)。

数据规模:$1\le q\le10^5,3\le m\le n\le10^6,0\le k\le m$。


Part2. 解析

众所周知,正多边形的所有顶点共圆,而且“等弦对等角”。

Part2/1. 形成锐角的充要条件

那么可以直观地看出:在圆上依次选取 3 个点 $A,B,C$,要使 $\angle ABC<90^\circ$,充要条件 是 $\frac{l}{2}< \overset{\frown}{AB}+\overset{\frown} {BC}$

那么反映在正多边形上,定义 $x_i$ 表示选取的凸多边形的第 i 个顶点与第 i+1 个顶点之间隔了多少条正 n 边形的边。要使第 i 个角是锐角,则需要满足 $x_{i-1}+x_i>\frac n2$,又因为 $n$ 是奇数,可以得到 $x_{i-1}+x_i\ge\frac{n+1}2$ 。为了表示方便,设 $p=\frac{n+1}2$

png1

比如上图(加粗的点是选取的 m 个顶点,设 1 是选取的第一个点,然后顺时针选点),则 $x_1=x_2=x_4=2,x_3=1$。那么 $\angle1<90^\circ$ 因为 $x_0+x_1\ge p$,$\angle5\not<90^\circ$ 因为 $x_2+x_3<p$ 。

也正因为这一点,选取的 m 边形最多只有 3 个锐角 ,且当且仅当 m=3(三角形)时,可以同时存在 3 个锐角。

Part2/2. 容斥原理

这种题目,一般来说直接计算“恰好”是非常困难的,因此要么采用“正难则反”,要么就用更加复杂的容斥原理。而显然这道题是用 容斥

我们发现下面这些值是可以计算的:

  • $ans_0$:任意选取 m 个点构成凸多边形的方案数;

  • $ans_1$:对于每个角,有多少种选取 m 个点的方案中它是锐角,即
    $\sum_{i=1}^n(有多少种\angle i是锐角)$;

  • $ans_2$:类似于 $ans_1$,只是变成了两个角而已
    $ans_2=\sum_{(i,j)}(有多少种方案中\angle i和\angle j都是锐角)$;

  • $ans_3$:仍然是这样的定义
    $ans_3=\sum_{(i,j,k)}(多少种方案中\angle i,\angle j,\angle k都是锐角)$

设我们要求的答案 $ans_i’$ 表示 恰好有 $i$ 个角是锐角的方案数。那么有:

  • $ans_0=ans_0’+ans_1’+ans_2’+ans_3’$
    根据 $ans_0$ 的定义可知。

  • $ans_1=ans_1’+2\times ans_2’+3\times ans_3’$

    因为只有两个锐角的方案中,假设这两个锐角分别是 $\angle i\angle j$ ,那么计算 $\angle i$ 为锐角的方案数时,这个方案被统计了一次,计算 $\angle j$ 为锐角的方案数时,这个方案又被统计了一次。总计所有恰好有两个锐角的方案被统计了两次。

    三个锐角的方案被统计了三次,同理。

  • $ans_2=ans_2’+3\times ans_3’$

    对于一个恰好有三个角的方案,假设三个锐角分别 $\angle i\angle j\angle k$,那么计算 $\angle j\angle j$ 为锐角时,这个方案算了一次,$\angle i\angle k$ 为锐角时,这个方案又算了一次,计算 $\angle j\angle k$ 为锐角时,这个方案还会被算一次。总计被算了 3 次。

  • $ans_3=ans_3’$ 显然。

然后配一配容斥系数:

  • $ans_0’=ans_0-ans_1+ans_2-ans_3$
  • $ans_1’=ans_1-2\times ans_2+3\times ans_3$
  • $ans_2’=ans_2-3\times ans_3$
  • $ans_3’=ans_3$

Part2/3. 计算

根据 $x_i$ 的定义,可以得到下面这个方程:

这个方程的解的个数就是 $ans_0$,用隔板法即可: $ans_0=C_{n-1}^{m-1}$。

然后计算 $ans_1$,不妨设 $\angle t$ 为锐角,那么 $x_{t-1}+x_t\ge p$。则存在两种情况:

  1. $x_t\ge p$:那么 $x_{t-1}$ 就没有限制,只要 $x_{t-1}\ge1$ 即可;接下来就是常规操作,将 $x_t$ 的值减去 $p-1$,那么此时 $x_t\ge1$,$\sum_{i=1}^mx_i=n-p+1$;

    再用隔板法:$C_{n-p}^{m-1}$

  2. $x_t<p$:设 $h=x_t$,那么 $x_{t-1}\ge p-h$,再进行常规操作,将 $x_{t-1}$ 的值减去 $p-h-1$,此时 $x_{t-1}\ge1$,$\sum_{i=1}^mx_i=n-p+h+1$;

    但是这个式子中,我们知道 $x_t=h$,所以我们单独把 $x_t$ 提出来,相当于:

    发现又可以用隔板法了:$C_{n-p}^{m-2}$。但是 $h$ 本身还有 $p-1$ 种取值,所以最后方案数是 $(p-1)C_{n-p}^{m-2}$

对于一个 $\angle t$ 是这么多,一共有 $m$ 个 $\angle t$,综上 $ans_1=m\times\left[C_{n-p}^{m-1}+C_{n-p}^{m-2}(p-1)\right]$

接下来是 $ans_2$,不难发现这两个锐角一定是相邻的,不妨设是 $\angle t$ 和 $\angle(t+1)$,则有 $x_{t-1}+x_t\ge p,x_t+x_{t+1}\ge p$,仍然存在两种情况:

  1. $x_t\ge p$:和 $ans_1$ 一样,先减去 $p-1$ 再隔板法:$C_{n-p}^{m-1}$;

  2. $x_t<p$:令 $h=x_t$,则 $x_{t-1}\ge p-h,x_{t+1}\ge p-h$,再给 $x_{t-1}$ 和 $x_{t+1}$ 都减去 $p-h-1$,又知道 $x_t=h$,则

    惊奇地发现等式左边还有一个未知数 $h$,但是我们知道 $p-h\ge1$,所以可以把 $(p-h)$ 整体当作一个新的未知数;

    相当于 $m$ 个未知数。用隔板法:$C_{n-p+1}^{m-1}$。但是不需要乘上 $(p-1)$,因为解出来这个方程,$h$ 的值也就知道了。

最后 $t$ 也有 $m$ 个取值,所以 $ans_2=m\times(C_{n-p+1}^{m-1}+C_{n-p}^{m-1})$

最后计算 $ans_3$,不难发现只有三角形($m=3$)可能存三个锐角,此时相当于 $ans_2$ 中 $x_t<p$ 的情况,即 $ans_3=C_{n-p+1}^{m-1}$ 。

预处理阶乘、逆元,然后 $O(1)$ 计算即可。


Part3. 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e6,MOD=998244353;

struct MODNUM{
int num;
MODNUM(){}
MODNUM(int x){num=x;}
MODNUM operator +(MODNUM B){return (num+B.num)%MOD;}
MODNUM operator -(MODNUM B){return ((num-B.num)%MOD+MOD)%MOD;}
MODNUM operator *(MODNUM B){return (1ll*num*B.num%MOD+MOD)%MOD;}
};

int cas;
MODNUM fac[N+3],inv[N+3];

MODNUM QPow(MODNUM a,int b){
MODNUM resu(1);
while(b){
if(b&1) resu=resu*a;
a=a*a;
b>>=1;
}
return resu;
}
MODNUM fC(int a,int b){
if(a>b) return 0;
return fac[b]*inv[a]*inv[b-a];
}
int main(){
fac[0]=1;for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i;
inv[N]=QPow(fac[N],MOD-2);for(int i=N-1;i>=0;i--) inv[i]=inv[i+1]*(i+1);
scanf("%d",&cas);
while(cas--){
int n,m,k;scanf("%d%d%d",&n,&m,&k);
if(k>3){
printf("0\n");
continue;
}
int p=(n+1)/2;
MODNUM ans0=fC(m-1,n-1),
ans1=(fC(m-1,n-p)+fC(m-2,n-p)*(p-1))*m,
ans2=(fC(m-1,n-p)+fC(m-1,n-p+1))*m,
ans3(0);
if(m==3) ans3=fC(m-1,n-p+1);
MODNUM ans;
switch(k){
case 0: ans=ans0-ans1+ans2-ans3;break;
case 1: ans=ans1-ans2*2+ans3*3;break;
case 2: ans=ans2-ans3*3;break;
case 3: ans=ans3;break;
}
printf("%d\n",ans*QPow(m,MOD-2)*n);
}
return 0;
}

The End

Thanks for reading!

- 说不定你是极少数看我的博客的人之一 ~

0%