题解 P2467 【[SDOI2010]地精部落】
devout
2020-11-25 11:44:45
**description**
求长度为 $n$ 的每个位置都是极值的排列的个数对 $p$ 取模的结果。
$n\leq 4200$
**solution**
我们观察发现，对于一个最开始是极大值的满足条件的序列，如果把整个序列翻过来，即 $a_i=n+1-a_i$ 时，一定也是可以的。
所以我们只需要求第一个位置为极大值的序列个数。
设 $f_i$ 表示一个 $1$ 到 $i$ 的排列，第一个位置为极大值的方案数。
考虑将这些数从小到大放进去，考虑到 $i$ 时，设他排在第 $j$ 个位置，那么可以得到转移
$$f_i=\sum_{j=1,j\bmod 2=1}^i f_{j-1}\times f_{i-j}\times\binom{i-1}{j-1}$$
这样的转移就是 $O(n^2)$ 的了，只需要最后 $\times 2$ 就可以了
**code**
```cpp
# include <bits/stdc++.h>
using namespace std;
# define Rep(i,a,b) for(register int i=a;i<=b;i++)
# define _Rep(i,a,b) for(register int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
typedef long long ll;
const int N=4205;
template<typename T> void read(T &x){
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
x*=f;
}
int n,m;
int f[N];
int C[2][N];
int main()
{
read(n),read(m);
f[0]=1;
C[0][0]=C[1][0]=1;
Rep(i,1,n){
Rep(j,1,i)
if(j&1)(f[i]+=1ll*f[j-1]*f[i-j]%m*C[i&1^1][j-1]%m)%=m;
Rep(j,1,i)C[i&1][j]=(C[i&1^1][j]+C[i&1^1][j-1])%m;
C[i&1][0]=1;
}
printf("%d\n",2*f[n]%m);
return 0;
}
```