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; }
Comments NOTHING