CF1764D Doremy's Pegging Game
你怎么连简单题也不会？
考虑满足条件当且仅当有连续的n/2向下取整段被删除。
考虑最终状态一定是一次删除联通了两个连续段，然后结束。
我们枚举这个连续段的长度 i 。
最后一个删除的位置有 n/2下取整*2-i 种方案，设另外删除了 j 种，则另外删除的方案数是 C(j,n-2-i) 种，（i+J-1）！ 除了最后一个以外的都可以排列。
还有一种情况是n为偶数，i可以等于 n-1 需要特判。
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
/*想想你要干什么？
* 思考你的效率，可以倒计时。
* 正难则反
* 明确数组定义
* 写下可能的思路
* 特殊情况 （ n == 1 ）？
* 查看溢出，数组越界
* 做事而不是原地规划
* 不要在一个方面卡死
* 多想性质！
*
*/
const int maxn=1e4+10;
int ans=0;
int fac[maxn];
int c[5005][5005];
signed main(){
int n=read(),p=read();
fac[1]=1;
for(int i=2;i<=n;i++){
fac[i]=fac[i-1]*i%p;
}
for(int i=0;i<=n;i++) c[i][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
}
}
for(int i=n/2;i<=n-2;i++){
for(int j=0;j<=n-2-i;j++){
ans=(ans+c[n-2-i][j]*fac[i+j-1]%p*(n/2*2-i)%p*n)%p;
// cout<<ans<<endl;
}
}
if(n%2?0:1){
ans=(ans+n*fac[(n-2)]%p)%p;
}
cout<<ans<<endl;
}