地精部落
题目描述
输入格式
输出格式
样例
数据范围与提示
一看似乎不太好转移,每个数要比它两边的数大或小,如果直接针对每个数进行状态转移,不太好弄
然而我们研究一下这种序列,要按照 小 大 小...这样,那么如果我们在一整个序列前加一个更大的数,变成 大 小 大 小 有成一个合法序列了
一个大小大小的序列可以唯一对应一个小大小大的合法序列,比如213变为231,相当于每个数a变为N-a+1,所以小大小大的个数与大小大小的个数相同
用f[i][j]表示长度为i的序列,开头为j的方案数 并且是大小大小
怎么转移?
再看看另一个特性
对于序列中的x和x+1,只要他们不相邻,交换后得到一个新序列仍合法。画一张图比较好得出
那么我们可以利用这一点直接从f[i][j-1]转移到f[i][j]
长为i,第一个数为j-1,它的第二个数一定小于j-1,也就是j一定不与j-1相邻,那么j与j-1交换就可以得到长为i第一位j,第二位不是j-1(比j-1小)的合法序列
要得到第二位是j-1的序列,可以将长为i-1的状态转移过来
找长i-1的首位是j-1 并且是 小 大 小 大 的序列,这样直接在前面添上j就合法了
那么这样的序列个数其实就是长为j-1首位为(i-1)-(j-1)的序列的个数(相当与用i-1去减没一个数,变成小大小大)
合起来f[i][j]=f[i][j-1]+f[i-1][(i-1)-(j-1)+1]
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 int N; 6 int p; 7 int f[4300][4300]; 8 int main(){ 9 memset(f,0,sizeof(f)); 10 scanf("%d%d",&N,&p); 11 f[1][1]=1; 12 for(int i=2;i<=N;++i){ 13 // f[i][1]=1; 14 for(int j=1;j<=i;++j){ 15 f[i][j]=1ll*(f[i][j-1]+f[i-1][i-1-(j-1)+1])%p; 16 } 17 } 18 int ans=0; 19 for(int i=1;i<=N;++i) 20 ans=1ll*(ans+f[N][i])%p; 21 ans=2ll*ans%p; 22 printf("%d ",ans); 23 }