黄参部落葡京娱乐场

15二三 鬼盖部落

 

省代表队选拔赛

 时限: 一s

 空间范围: 25五千KB

 标题等第 : 大师
Master

题解

 

 

 

标题叙述 Description

    轶事很久从前,大地上位居着壹种神秘的古生物:人参。 
    野山参喜欢住在连绵不绝的群山中。具体地说,壹座长度为 N 的深山
H可分为从左到右的 N 段,每段有1个旷世的万丈 Hi,个中Hi是一到N
之间的正整数。 
   
假设1段山脉比有所与它周边的山脊都高,则那段山脉是多少个山脉。位于边缘的山脉唯有一段相近的山峰,别的都有两段(即右侧和左侧)。 
   
类似地,要是壹段山脉比有所它周边的山脊都低,则那段山脉是二个峡谷。 
   
人葠们有2个共同的喜爱——饮酒,酒馆能够举行在谷底之中。人衔的旅舍不论白天黑夜总是喝伍吆6,人葠美酒的菲菲能够飘到方圆数里的地点。 
   
人葠照旧一种卓殊警惕的海洋生物,他们在每座山体上都足以进行瞭望台,并轮流担负瞭望工作,以保证在第暂且间得知外敌的侵入。 
    黄参们希望那N
段山脉每段都足以建造瞭望台或酒馆的内部之一,唯有满足那几个原则的整座山脉才大概有海腴居住。 
    现在您愿意知晓,长度为N
的只怕有西洋参居住的山脊有微微种。两座山脉A和B分歧当且仅当存在1个 i,使得
Ai≠Bi。由于这一个数额大概一点都不小,你只对它除以P的余数感兴趣。

输入描述 Input Description

    输入仅含一行,八个正整数 N,P。 

输出描述 Output Description

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

样例输入 萨姆ple Input

4 7

样例输出 Sample Output

3

数码范围及提示 Data Size & Hint

共有10 种只怕的山脊,它们是: 
1324 1423 2143 2314 2413 
3142 3241 3412 4132 4231 

【数据规模和平条目定】 
对于 20%的数据,满足 N≤10; 
对于 40%的数据,满足 N≤18; 
对于 70%的数据,满足 N≤550; 
对于 100%的数据,满足 3≤N≤4200,P≤109。

 

/*
    f[i][j]第一位为[1,j]且第一位下降的1~i的合法排列数,先给出结论:f[i][j] = f[i][j – 1] + f[i – 1][i – j]
    首先是要加上[1,j – 1]的合法排列数,然后考虑j开头的第一位下降合法排列数
    这个就是求以[1,j]开头的1~n-1的第一位上升合法排列数(这个应该可以YY一下吧..)
    但是第一位上升的合法排列数我们是没有算的,但注意到第一位上升和第一位下降具有对称性
    所以求以[1,j]开头的1~n-1的第一位上升合法排列数就是f[i – 1][i – j]
    然后如果开[4200][4200]的int的话正好会被卡掉,所以必须滚动数组..
*/
#include<iostream>
#include<cstdio>
using namespace std;
int n,p;
int dp[2][5000];
int main(){
    scanf("%d%d",&n,&p);
    int x;
    dp[1][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            x=i&1;
            dp[x][j]=dp[x][j-1]+dp[x^1][i-j];
            dp[x][j]%=p;
        }
    }
    printf("%d",(long long)(dp[n&1][n]*2)%p);
    return 0;
}

 

Description

逸事很久从前,大地上位居着1种神秘的浮游生物:沙参。
黄参喜欢住在连绵不绝的山峰中。具体地说,1座长度为 N 的深山 H可分
为从左到右的 N 段,每段有1个旷世的万丈 Hi,当中Hi是一到N 之间的正
整数。
假设1段山脉比有所与它周围的山脉都高,则那段山脉是3个山峰。位于边
缘的群山唯有1段相近的群山,其余都有两段(即左侧和右手)。
类似地,若是一段山脉比有所它周围的山脊都低,则那段山脉是1个低谷。
黄参们有3个联合的爱好——喝酒,旅馆能够举行在峡谷之中。海腴的小吃摊
不论白天黑夜总是众楚群咻,丹参美酒的川白芷能够飘到方圆数里的地点。
黄党照旧壹种格外小心的古生物,他们在每座山体上都得以设置瞭望台,并轮
流肩负瞭望专门的职业,以担保在第暂时间得知外敌的凌犯。 黄参们希望那N
段山脉每段都得以建造瞭望台或旅社的内部之壹,唯有满意这一个条件的整座山脉才大概有黄党居住。 以后您期望知道,长度为N
的或许有海腴居住的山峰有多少种。两座山脉A 和B差别当且仅当存在三个i,使得 Ai≠Bi。由于这些数量大概比非常的大,你只对它 除以P的余数感兴趣。

Input

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

Output

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

葡京娱乐场,Sample Input

4 7

Sample Output

3

HINT

葡京娱乐场 1

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

 

正解:$DP$

那种题真的太恶心了,小编观念弱啊!!!

不想写题解了。。

二个神犇的题解:http://blog.csdn.net/mrazer/article/details/53426415?locationNum=12&fps=1

 

 1 //It is made by wfj_2048~
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <complex>
 5 #include <cstring>
 6 #include <cstdlib>
 7 #include <cstdio>
 8 #include <vector>
 9 #include <cmath>
10 #include <queue>
11 #include <stack>
12 #include <map>
13 #include <set>
14 #define inf (1<<30)
15 #define il inline
16 #define RG register
17 #define ll long long
18 
19 using namespace std;
20 
21 ll f[2][4210],n,p,cur,ans;
22 
23 il void work(){
24     cin>>n>>p; f[1][1]=1,cur=1;
25     for (RG ll i=2;i<=n;++i){
26     cur^=1;
27     for (RG ll j=1;j<=i;++j)
28         f[cur][j]=(f[cur][j-1]+f[cur^1][i-j+1])%p;
29     }
30     for (RG ll i=1;i<=n;++i) ans=(ans+f[cur][i])%p;
31     printf("%lld",ans*2%p); return;
32 }
33 
34 int main(){
35     work();
36     return 0;
37 }

 

相关文章