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$

比如上图（加粗的点是选取的 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$ 的定义，可以得到下面这个方程：

$$\begin{cases} \sum_{i=1}^mx_i=n\\ \forall _ix_i\ge 1 \end{cases}$$

这个方程的解的个数就是 $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$ 提出来，相当于：

   $$\begin {align} \sum_{i=1}^{m-1}x_i+x_t&=n-p+h+1\\ \sum_{i=1}^{m-1}x_i&=n-p+1 \end{align}$$

   发现又可以用隔板法了：$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$，则

   $$\begin{align} \sum_{i=1}^{m-1}x_i+h&=n-2p+2h+2\\ \sum_{i=1}^{m-1}x_i&=n-2p+h+2 \end{align}$$

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

   $$\sum_{i=1}^{m-1}x_i+(p-h)=n-p+2$$

   相当于 $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. 源代码

/*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!

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