葡京娱乐场海腴部落

Description

相传很久从前,大地上位居着壹种神秘的生物体:人衔。
土精喜欢住在连绵不绝的群山中。具体地说,1座长度为 N 的深山 H可分
为从左到右的 N 段,每段有一个环球无双的万丈 Hi,在那之中Hi是一到N 之间的正
整数。
假使一段山脉比有所与它相近的山峰都高,则这段山脉是一个山脉。位于边
缘的群山唯有一段周围的深山,别的都有两段(即右侧和右边)。
类似地,假如一段山脉比全数它相近的山脉都低,则那段山脉是几个峡谷。
人参们有三个一齐的喜爱——饮酒,商旅能够设立在低谷之中。人葠的酒吧
不论白天黑夜总是人声鼎沸,土精美酒的浓香能够飘到方圆数里的地方。
人衔照旧壹种十分警惕的浮游生物,他们在每座山体上都得以设置瞭望台,并轮
流担当瞭望工作,以保险在第一时半刻间得知外敌的打扰。 海腴们希望那N
段山脉每段都得以建造瞭望台或酒馆的中间之1,唯有满意那几个标准的整座山脉才也许有人衔居住。 以往你愿意知道,长度为N
的或然有人葠居住的山峰有稍许种。两座山脉A 和B分裂当且仅当存在多个i,使得 Ai≠Bi。由于这些数额大概非常的大,你只对它 除以P的余数感兴趣。

1925: [Sdoi2010]沙参部落

Time Limit: 10 Sec  Memory
Limit: 64 MB
Submit: 1519  Solved: 952
[Submit][Status][Discuss]

Input

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

Description

相传很久从前,大地上位居着1种神秘的浮游生物:丹参。
人葠喜欢住在连绵不绝的山脉中。具体地说,一座长度为 N 的山峰 H可分
为从左到右的 N 段,每段有三个全球无双的可观 Hi,个中Hi是壹到N 之间的正
整数。
借使1段山脉比有所与它周边的山体都高,则那段山脉是二个山峰。位于边
缘的山脉惟有1段周边的山脉,别的都有两段(即左边和左边)。
类似地,借使一段山脉比有所它周边的群山都低,则那段山脉是几个峡谷。
野山参们有一个联合签字的喜悦——吃酒,饭馆能够设立在山谷之中。黄党的小吃摊
不论白天黑夜总是人声鼎沸,黄参美酒的川白芷能够飘到方圆数里的地点。
人参照旧1种十二分警惕的浮游生物,他们在每座山体上都得以设置瞭望台,并轮
流担当瞭望工作,以确认保证在第权且间得知外敌的侵袭。 丹参们希望那N
段山脉每段都得以建造瞭望台或酒吧的内部之一,只有满意那几个规则的整座山脉才可能有人参居住。 现在您期望掌握,长度为N
的可能有神草居住的深山有多少种。两座山脉A 和B差异当且仅当存在一个i,使得 Ai≠Bi。由于那个数量只怕不小,你只对它 除以P的余数感兴趣。

Output

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

Input

仅含1行,五个正整数 N, P。

Sample Input

4 7

Output

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

Sample Output

3

Sample Input

4 7

HINT

葡京娱乐场 1
对于 20%的数据,满足 N≤10;
对于 40%的数据,满足 N≤18;
对于 70%的数据,满足 N≤550;
对于 100%的数据,满足 3≤N≤4200,P≤109

 

题解:

丰硕强的思辨题哈……

大家要了解壹些至关心珍重要的定律:

原难点是求波动数列的个数

(一).若是四个数i,i-1且他们在数列中地方不相邻,那么交流他们八个,数列也为不安数列

(2).把一个波动数列同时成为n-i+一,那么还是为不安类别,且有些山谷变山峰

 

故此大家设状态为f[i][j]代表:已经填了[1,i]本条范围的数,第三个数为j且j为高峰的方案数

传说(一)可以得出f[i][j]=f[i][j-1]
因为调换j,j-1就能够产生新方案
又因为我们强制j为高峰,那么不会再也

依照(二)得:假诺第三个数是j-一那么去掉第3个数j后,还剩[1,j-1]和[j+1,i]据此大家把后四个间距数都减一,就改为了叁个[1,i-1]的排列,所以我们强制第2个数为j-一,且为谷,那么怎么转变呢?

因为满意(二)的对称性那么能够从f[i-1][(i-1)-(j-1)+1]得出不是啊?

综上f[i][j]=f[i][j-1]+f[i-1][i-j+1]

最终记得答案乘二,因为满意对称性

 

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 using namespace std;
 8 const int N=4505;
 9 int f[2][N];
10 void work()
11 {
12     int n,mod;
13     scanf("%d%d",&n,&mod);
14     bool tt=0,t=1;
15     f[tt][2]=1;
16     for(int i=3;i<=n;i++){
17         for(int j=2;j<=i;j++){
18             f[t][j]=(f[t][j-1]+f[tt][i-j+1])%mod,f[t][j]%=mod;
19         }
20         t^=1;tt^=1;
21     }
22     int ans=0;
23     for(int i=2;i<=n;i++)
24         ans+=f[tt][i],ans%=mod;
25     printf("%d\n",(ans<<1)%mod);
26 }
27 
28 int main()
29 {
30     work();
31     return 0;
32 }

 

Sample Output

3

HINT

葡京娱乐场 2 
对于 20%的数据,满足 N≤10; 
对于 40%的数据,满足 N≤18; 
对于 70%的数据,满足 N≤550; 
对于 100%的数据,满足 3≤N≤4200,P≤109

Source

第一轮Day2

  近年来做题都是那种想到了秒A,想不到刚1天也打不出去的题啊……

  那道题当时想的是五个点三个点的转变,因为壹旦不去思量山脉两端的话把它们放在任意一个山体两侧都以法定的。然后就不知底怎么搞了。

  事实注脚笔者要么太菜了……

  我们设f[i][j]为我们选i个数(大小Infiniti制),在那之中第j小的数位居开端且她为山谷的方案数,那么它能够从g[i-1][k](j<=k<=i-一),g数组表示i个数中第k小的数在早先且他为山体的方案数。这们转移的实际意义便是把j放在十二分山峰后面。为啥那样合法呢?因为一旦1个数是i个数里第j小的,那么他迟早是比不上i-2个数里第j个数大的。

  可是由于那是2个颠簸类别,大家让各样地点的中度成为i-x+一,那么大家就足以由f[i][j]的到g[i][i-j+1],将七个姿态合并一下就赢得了下边只和f有关的转移方程

    f[i][j]=∑f[i-1][1~i-j]

  所以大家就足以在n^2的时日复杂度内求出全体的f,再把f加和乘以贰就是答案。

葡京娱乐场 3葡京娱乐场 4

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<string>
 8 #include<queue>
 9 #define N 5000
10 using namespace std;
11 long long f[2][N];
12 int n,p;
13 int main(){
14     scanf("%d%d",&n,&p);
15     int now=1,la=0;
16     f[now][1]=1;
17     for(int i=2;i<=n;i++)
18     {
19         swap(now,la);
20         long long sum=0;
21         memset(f[now],0,sizeof(f[now]));
22         for(int j=i-1;j>0;j--)
23         {
24             sum+=f[la][i-j];
25             sum%=p;
26             f[now][j]=sum;
27         }
28     }
29     long long ans=0;
30     for(int i=1;i<n;i++)
31     {
32         ans+=f[now][i];
33         ans%=p;
34     }
35     ans*=2;
36     ans%=p;
37     printf("%lld\n",ans);
38     return 0;
39 }

View Code

相关文章