考虑限制一定是对于前缀和后缀的, 并且显然相交的前后缀可以不考虑. 然后还可以发现只用考虑最长的那一段的条件, 即 \(\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\) 在中间), 这个也可以轻松统计.
代码
- #include<bits/stdc++.h>
- using namespace std;
- int mod, n;
- typedef long long ll;
- int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
- int sub(int a,int b){a-=b;return a<0?a+mod:a;}
- int mul(int a,int b){return (ll)a*b%mod;}
- int 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;}
- /* math */
- const int N = 5010;
- int f[2][N],g[2][N],h1[2][N],h2[2][N];
- inline void Do1(int p,int i){
- for(int j=0;j<=n;j++)f[i][j] = g[i][j] = h1[i][j] = h2[i][j] = 0;
- for(int j=0;j<=n;j++){
- f[i][j] = add(f[i][j], f[i^1][j]);
- if(j>=p){
- f[i][j] = add(f[i][j], f[i][j-p]);
- }
- }
- }
- inline void Do2(int p,int i){
- for(int j=0;j<=n;j++)f[i][j] = g[i][j] = h1[i][j] = h2[i][j] = 0;
- for(int j=0;j<=n;j++){
- f[i][j] = add(f[i][j], f[i^1][j]);
- if(j>=p){
- f[i][j] = add(f[i][j], f[i][j-p]);
- }
- }
- for(int j=0;j<=n;j++){
- h1[i][j] = add(h1[i][j], 1ll*f[i^1][j]*(j/p-1)%mod);
- if(j>=p){
- h1[i][j] = add(h1[i][j], h1[i][j-p]);
- }
- }
- for(int j=0;j<=n;j++){
- f[i][j] = sub(mul(f[i][j], j/p),h1[i][j]);
- }
- }
- int main()
- {
- cin>> n>> mod;
- int _d = (n-1)/2;
- bool flg=0;
- if(n%2==0){ flg=1; }
- int cur = 0;
- f[cur][0] = 1;
- for(int i=_d;i;i--){
- int p = i;
- Do1(p,cur^=1);
- if(i==_d && flg)Do2(p+1,cur^=1);
- else Do1(p+1,cur^=1);
- }
- int ans = 0;
- if(n==2){cout << 3 << endl;return 0;}
- for(int i=0;i<=n;i++){
- ans = add(ans, mul(f[cur][i], n-i));
- }
- cout << ans << endl;
- }
来源: http://www.bubuko.com/infodetail-3355213.html