考虑限制一定是对于前缀和后缀的，并且显然相交的前后缀可以不考虑。然后还可以发现只用考虑最长的那一段的条件，即 $\lfloor\frac {n-1}{2}\rfloor$ 和 $\lfloor\frac {n-1}{2}\rfloor + 1$ 的长度。
可以将原序列分成两个部分。
如下： $$ {A A | (C) | B} $$ 我们把 $C$ 去掉，把最后一个 $A$ 提出来。
分别向前后差分分别记为数组 $a,b$ 。发现 $\sum _i (a_i + b_i) * i$ 就是除去 $A$ 的差。
即 $\text{最后一个 A 的值} > \sum _i (a_i + b_i) * i$ 。
向后的差分还对 $A$ 的最大值有影响，贡献要多一个。
并且容易发现最后的方案就是 $n - \sum (a_i + b_i)*i + \sum b_i$， 小于 $0$ 没有贡献。
然后发现有些时候方案数要多乘一个 $b_i+1$ （有一个 $C$ 在中间），这个也可以轻松统计。
代码
1#include<bits/stdc++.h> 2using namespace std; 3int mod, n; 4typedef long long ll; 5int add(int a,int b){a+=b;return a>=mod?a-mod:a;} 6int sub(int a,int b){a-=b;return a<0?a+mod:a;} 7int mul(int a,int b){return (ll)a*b%mod;} 8int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;} 9/* math */ 10const int N = 5010; 11int f[2][N],g[2][N],h1[2][N],h2[2][N]; 12 13inline void Do1(int p,int i){ 14 for(int j=0;j<=n;j++)f[i][j] = g[i][j] = h1[i][j] = h2[i][j] = 0; 15 for(int j=0;j<=n;j++){ 16 f[i][j] = add(f[i][j], f[i^1][j]); 17 if(j>=p){ 18 f[i][j] = add(f[i][j], f[i][j-p]); 19 } 20 } 21} 22inline void Do2(int p,int i){ 23 for(int j=0;j<=n;j++)f[i][j] = g[i][j] = h1[i][j] = h2[i][j] = 0; 24 for(int j=0;j<=n;j++){ 25 f[i][j] = add(f[i][j], f[i^1][j]); 26 if(j>=p){ 27 f[i][j] = add(f[i][j], f[i][j-p]); 28 } 29 } 30 for(int j=0;j<=n;j++){ 31 h1[i][j] = add(h1[i][j], 1ll*f[i^1][j]*(j/p-1)%mod); 32 if(j>=p){ 33 h1[i][j] = add(h1[i][j], h1[i][j-p]); 34 } 35 } 36 for(int j=0;j<=n;j++){ 37 f[i][j] = sub(mul(f[i][j], j/p),h1[i][j]); 38 } 39} 40 41int main() 42{ 43 cin >> n >> mod; 44 int _d = (n-1)/2; 45 bool flg=0; 46 if(n%2==0){ flg=1; } 47 int cur = 0; 48 f[cur][0] = 1; 49 for(int i=_d;i;i--){ 50 int p = i; 51 Do1(p,cur^=1); 52 if(i==_d && flg)Do2(p+1,cur^=1); 53 else Do1(p+1,cur^=1); 54 } 55 int ans = 0; 56 if(n==2){cout << 3 << endl;return 0;} 57 for(int i=0;i<=n;i++){ 58 ans = add(ans, mul(f[cur][i], n-i)); 59 } 60 cout << ans << endl; 61}