CF1764D Doremy’s Pegging Game

题目大意

墙上有nnn个红色的钉子，有一根橡皮筋围在钉子上，形成了⼀个正边形。在正边形的中⼼处有⼀个蓝⾊的钉⼦，蓝⾊钉⼦的直径⽐红⾊钉⼦⼩。现在你拔掉若⼲钉⼦，当橡⽪筋最终碰到了蓝⾊钉⼦，游戏结束。问你有多少种有序的拔掉红⾊钉⼦的⽅案。答案模⼀个质数ppp。

3≤n≤50003\leq n\leq 50003≤n≤5000，108≤p≤10910^8\leq p\leq 10^9108≤p≤109

题解

设t=⌊n2⌋t=\lfloor\dfrac n2\rfloort=⌊2n​⌋，则去掉连续的i(i≥t)i(i\geq t)i(i≥t)个红钉子之后，游戏结束。因为是正nnn边形，所以从哪个点开始取走一段都可以，不妨设从第一个点开始取走一段，最后再乘上nnn。

我们可以枚举iii，在这iii个点中，总有一个点要在最后去掉。它与最后一个点之间的点的个数不能超过ttt，所以前i−ti-ti−t个点不能选；它与第一个点之间的点的个数不能超过ttt，所以后i−ti-ti−t个点不能选，所以它能选择的点为i−2(i−t)=t−ii-2(i-t)=t-ii−2(i−t)=t−i个点。

剩下能选的点有n−2−in-2-in−2−i个。枚举选的点j(j≤n−2−i)j(j\leq n-2-i)j(j≤n−2−i)，则这些点有Cn−2−ijC_{n-2-i}^jCn−2−ij​种选择。

最后一个点必须最后取，选其余点的顺序任意，所以还要乘上(j+i−1)!(j+i-1)!(j+i−1)!。

方案数为

∑i=tn−2(2∗t−i)×n×∑j=0n−2−iCn−2−ij×(j+i−1)!\sum\limits_{i=t}^{n-2}(2*t-i)\times n\times \sum\limits_{j=0}^{n-2-i}C_{n-2-i}^j\times (j+i-1)!i=t∑n−2​(2∗t−i)×n×j=0∑n−2−i​Cn−2−ij​×(j+i−1)!。

一些特判：
当i=n−1i=n-1i=n−1时

• 如果nnn为奇数，则因为如果只剩两个点，游戏一定结束，所以不可能能够删到只剩一个点，此时贡献为000
• 如果nnn为偶数，因为n−i−2=−1n-i-2=-1n−i−2=−1，出现了负数，所以要特判。这种情况下的贡献为(i−1)!(i-1)!(i−1)!

时间复杂度为O(n2)O(n^2)O(n2)。

code

#include
using namespace std;
int n;
long long p,ans,jc[5005],ny[5005];
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%p;if(v&1) re=re*t%p;return re;
}
long long C(int x,int y){return jc[x]*ny[y]%p*ny[x-y]%p;
}
int main()
{scanf("%d%lld",&n,&p);jc[0]=1;for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%p;ny[n]=mi(jc[n],p-2);for(int i=n-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%p;for(int i=n/2;iif((n&1)&&i==n-1) break;long long tmp=0;int v=n-i-2;if(i==n-1) tmp=jc[i-1];else{for(int j=0;j<=v;j++){tmp=(tmp+C(v,j)*jc[j+i-1]%p)%p;}}ans=(ans+((n/2)*2-i)*tmp%p)%p;}ans=n*ans%p;printf("%lld",ans);return 0;
}