海腴部落

[Sdoi2010]神草部落

Time Limit: 10 Sec  Memory
Limit: 64 MB
Submit: 1643  Solved: 1025
[Submit][Status][Discuss]

Description

相传很久从前,大地上位居着一种神秘的生物体:鬼盖。
野山参喜欢住在连绵不绝的山体中。具体地说,一座长度为 N 的山脊 H可分
为从左到右的 N 段,每段有二个旷世的莫斯中国科学技术大学学 Hi,其中Hi是1到N 之间的正
整数。
如若一段山脉比有所与它附近的群山都高,则那段山脉是二个山脊。位于边
缘的山体唯有一段附近的山体,别的都有两段(即右侧和左侧)。
类似地,就算一段山脉比有所它附近的山峰都低,则那段山脉是二个峡谷。
沙参们有三个共同的喜爱——饮酒,酒店可以设置在山里之中。人葠的饭店不论白天黑夜总是人声鼎沸,太子参美酒的花香能够飘到方圆数里的地方。
防党参照旧一种非凡警觉的生物体,他们在每座山体上都足以实行瞭望台,并轮
流担当瞭望工作,以保险在第临时间得知外敌的入侵。 高丽参们希望那N
段山脉每段都得以建造瞭望台或酒吧的中间之一,只有满意这一个规格的整座山脉才只怕有移山参居住。 未来您愿意知道,长度为N
的大概有丹参居住的山峰有稍许种。两座山脉A 和B差异当且仅当存在3个i,使得 Ai≠Bi。由于那个数额只怕非常大,你只对它 除以P的余数感兴趣。

Input

仅含一行,四个正整数 N, P。

Output

仅含一行,四个非负整数,表示您所求的答案对P取余 之后的结果。

Sample Input

4 7

Sample Output

3

HINT

4858mgm 1 
4858mgm,对于 20%的数据,满足 N≤10; 
对于 40%的数据,满足 N≤18; 
对于 70%的数据,满足 N≤550; 
对于 100%的数据,满足 3≤N≤4200,P≤109

Source

第一轮Day2

 

题解 style=”font-size: 14pt;”> style=”font-size: 14pt;”> 

将难点简化为1-n的具有排列中满足高低交替出现的个数,能够用动态规划落实。

我们用f[n][k]意味着n个数,最后三个为k且最终八个递增,g[n][k]意味着n个数最终贰个数为k且最终三个递减。

对于f[n][k],若我们将数列中种种数x换为n+1-x,则就成了g[n][n+1-k],所以可得f[n][k]=g[n][n+1-k]。

那正是说可得:

4858mgm 2

所以动态转换方程为f[n][k]=f[n][k-1]+f[n-1][n-k+1]

4858mgm 3

出于对称性,最后的答案为2ans。

唯独难题范围n<=4200,所以想到用滚动数组来压缩空间,于是那道题就AC了。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #include<cmath>
 6 
 7 #define N 4307
 8 using namespace std;
 9 
10 int n,p;
11 int f[2][N],ans=0,x=0,y=1;
12 
13 int main()
14 {
15     scanf("%d%d",&n,&p);
16     if (n==1){cout<<1<<endl;return 0;}
17 
18     f[0][1]=1;
19     for (int i=2;i<=n;i++)
20     {
21         for (int j=1;j<=i;j++) f[y][j]=(f[y][j-1]+f[x][i-j+1])%p;
22         swap(x,y);
23     }
24     for (int i=1;i<=n;i++) ans=(ans+f[x][i])%p;
25     ans=(ans*2)%p;
26     
27     printf("%d\n",ans);
28 }

 

相关文章