题目链接：Problem - D - Codeforces

Problem

给定一个正整数\(n\)和素数\(p\)，表示有一个由\(n\)个点的钉子组成的正\(n\)边形，外围套着一根有韧性的绳子，现在开始一个一个取钉子，问有多少种取钉子的方案可以使得绳子“越过中心点”， 答案对\(p\)取模。

Analyse

首先定义合法：“绳子没有越过中心点”。

结束：“绳子越过中心点”。

首先从小样本开始。

\(n = 3\)时，当有连续的\(1\)个钉子被取走，结束。

\(n = 4\)时，当有连续的\(2\)个钉子被取走，或留下了对角的两个钉子后再取一个，结束。

\(n = 5\)时，当有连续的\(2\)个钉子被取走，结束。

\(n = 6\)时，当有连续的\(3\)个钉子被取走，或留下了对角的两个钉子（此时依然是合法的）后再取一个，结束。

当\(n\)为奇数的时候，中心点不在任意一条对角线上，所以不会出现“对角的两个钉子使得局面合法”的情况出现，不难发现当有\(m = \lfloor \frac{n}{2} \rfloor\)个连续的钉子被取走的时候，局面一定结束，此时结束的局面中点的个数一定是\(>=2\)的。

当\(n\)为偶数的时候，除了上面说的情况，还要特殊考虑“最后一个合法局面是对角”的情况，此时结束的钉子的个数是\(1\)，这种情况是不会包含于上面的情况之中的。不难算出这种情况的方案数为\(n * (n - 2)!\)。\(n - 2\)个位置随便放，最后消除的点有\(n\)种可能。

现在将整个环想象成以任意点开始的一个链，且第一位是\(1\)，我们用一个数组（\(0\)删，\(1\)留）来表示局面（状态），那么某个结束局面的方案数就是从全\(1\)到当前结束局面的不同路径总数。那么只需要枚举所有结束局面，并计算贡献即可。

先考虑\(n\)为奇数的时候，如何构造出“最后一个合法局面”呢？我们需要使得当前局面在删除第一位上的1之后就结束。而每个点都是有对称性的所以最后的答案会乘\(n\)，这个留着先不管。将问题简化一下：我们枚举第二位向右的连续\(0\)的个数为\(i\)，从最后一位往前的连续的\(0\)的个数为\(j\)。\(i, j\)的取值都是从\(0\)到\(m\)。还需要保证一个条件，就是\(i + j + 1 >= m\)，也就是删除第一位上的1，局面就结束。

所以我们构造出的序列长这样\([1, 0, 0, 0, 1, x, x, x, 1, 0]\)，当\(i, j\)确定后，那么序列中就只有\(x\)是不确定。首先不难发现因为有\(i + j + 1 >= m\)，所以\(x\)的总个数\(n - i - j - 3 < m\)就算全\(0\)都合法，且删除第一位会结束。

现在问题再次转化：对于一个\(i, j\)都确定的序列，求出所有可能的局面，算贡献。

比如上面这个序列\([1, 0, 0, 0, 1, x, x, x, 1, 0]\)的可能局面就是\([1, 0, 0, 0, 1, 1, 0, 1, 1, 0]\)，那么对答案的贡献是零的个数的阶乘\( = 5!\)。

所以我们可以分析出最后的表达式（其中\(k\)为中间部分\(1\)的个数）：

$$ans = \sum\limits_{i = 0}^{m}\sum\limits_{j=0}^{m}[i + j + 1 \ge m][n - i - j- 3 \ge 0]\sum\limits_{k = 0}^{n - i - j - 3}C_{n - i - j - 3}^{k}(n - 3 - k)!$$

嗯。。。有三重循环，但是不难发现，这个第三层循环也就是\(k\)这一层是可以优化掉的。他的表达式则值只取决于求和上界，所以我们可以用一个函数来表示最后一层循环，\(f(t) = \sum\limits_{k=1}^{t}C_{t}^{k}(n-3-k)!\)，那么我们就可以\(O(n^2)\)来预处理出第三层循环，从而使得总算法复杂度是\(O(n^2)\)。

算完之后乘上\(n\)。

当\(n\)为偶数，再加上\(n *(n - 2) !\)。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5009;
int fac[maxn], invfac[maxn], f[maxn];
int n, p;

int qmi(int a, int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)res = res * a % p;
		a = a * a % p, b >>= 1;
	}	
	return res;
}
int inv(int x){return qmi(x, p - 2);}
int mo(int x){return (x % p + p) % p;}

int C(int n, int m)
{
	if(n < m || n < 0 || m < 0)return 0;
	return fac[n] * invfac[n - m] % p * invfac[m] % p;
}

signed main()
{
	scanf("%lld %lld", &n, &p);
	fac[0] = 1;
	for(int i = 1;i <= n; ++ i)fac[i] = fac[i - 1] * i % p;
	invfac[n] = inv(fac[n]);
	for(int i = n - 1;i >= 0; -- i)invfac[i] = invfac[i + 1] * (i + 1) % p;
	for(int t = 0;t <= n; ++ t)
	{
		for(int k = 0;k <= t; ++ k)
		{
			if(n - 3 - k >= 0)f[t] = (f[t] + C(t, k) * fac[n - 3 - k] % p) % p;
		}
	}
	int ans = 1;
	int sum = 0;
	for(int i = 0;i < n / 2; ++ i)
	{
		for(int j = 0;j < n / 2; ++ j)
		{
			int y = n - 3 - i  - j;
			if(i + j + 1 >= n / 2 && y >= 0)sum = (sum + f[y]) % p;
		}
	}
	
	ans = n * sum % p;
	if(n % 2 == 0)
	{
		ans = (ans + n * fac[n - 2] % p) % p;
	}
	
	printf("%lld\n", ans);
	
	
	return 0;
}