题解：CF1764D Doremy's Pegging Game

· · 题解

题目

考虑连续移除多少个红色钉子会使橡皮筋碰到蓝色钉子。

我们把第一个红色钉子（A），最后一个红色钉子（B）与蓝色钉子（O），顺序连边，形成三角形（不会成一条线的）（A 与 B 作为端点并没有移除）。

就这样子连边（移除 A 和 B 之间的钉子）。

我们发现当 \angle AOB>180^\circ 时橡皮筋会碰到蓝色钉子，设一共移除了 m 个钉子（n\neq m）。

\angle AOB= \frac{m+1}{n} \times 360^\circ>180^\circ\\ \therefore m\ge \lfloor \frac{n}{2}\rfloor

于是设在结束时有连续 x 个钉子被移除（\lfloor \frac{n}{2}\rfloor\le x\le n-2）, 设我们在剩下的钉子中移除了 y 个钉子（0\le y\le n-x-2），显然两边（交界处）不能移除。

可以发现最后一个移除的钉子只有 \lfloor \frac{n}{2}\rfloor+\lfloor \frac{n}{2}\rfloor-x 种选法。

最后统计一下贡献 n\times (\lfloor \frac{n}{2}\rfloor+\lfloor \frac{n}{2}\rfloor-x)\times \binom{n-x-2}{y}\times (x+y-1)!（注意最后一个点被固定了，第一个点有 n 种可能）。

但是当 n 为偶数时，会出现最后只剩下一个红钉子的情况，于是要再加上 n(n-2)!。

最后时间复杂度 O(N^2)。

:::success[code]

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)

const int N=5005;
int n,mod;
ll fac[N],inv[N],C[N][N];
ll pom(ll a,ll b){ll res=1;for(;b;b>>=1,a=a*a%mod) if(b&1)res=res*a%mod;}
void solve(){
    cin>>n>>mod;
    fac[0]=1;
    rep(i,1,n) fac[i]=fac[i-1]*i%mod;
    rep(i,0,n){C[i][0]=1,C[i][i]=1;rep(j,1,i-1) C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;}
    int m=n>>1;
    ll ans=0;
    rep(x,m,n-2)
        rep(y,0,n-x-2)
            ans=(ans+n*fac[x+y-1]*(m+m-x)%mod*C[n-x-2][y]%mod)%mod;
    if(n%2==0) ans=(ans+n*fac[n-2])%mod;
    cout<<ans<<'\n';
}
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    solve();
}

:::