Chtholly

題目描述

傳說很久以前，大地上居住著一種神秘的生物：地精。
地精喜歡住在連綿不絕的山脈中。具體地說，一座長度為N的山脈H可分為從左到右的N段，每段有一個獨一無二的高度Hi，其中Hi是1到N之間的正整數(shù)。
如果一段山脈比所有與它相鄰的山脈都高，則這段山脈是一個山峰。位于邊緣的山脈只有一段相鄰的山脈，其他都有兩段（即左邊和右邊）。
類似地，如果一段山脈比所有它相鄰的山脈都低，則這段山脈是一個山谷。
地精們有一個共同的愛好——飲酒，酒館可以設(shè)立在山谷之中。地精的酒館不論白天黑夜總是人聲鼎沸，地精美酒的香味可以飄到方圓數(shù)里的地方。
地精還是一種非常警覺的生物，他們在每座山峰上都可以設(shè)立瞭望臺，并輪流擔(dān)當瞭望工作，以確保在第一時間得知外敵的入侵。
地精們希望這N段山脈每段都可以修建瞭望臺或酒館的其中之一，只有滿足這個條件的整座山脈才可能有地精居住。
現(xiàn)在你希望知道，長度為N的可能有地精居住的山脈有多少種。兩座山脈A和B不同當且僅當存在一個i，使得Ai≠Bi。由于這個數(shù)目可能很大，你只對它除以P的余數(shù)感興趣。

輸入輸出格式

輸入格式
輸入文件goblin.in僅含一行，兩個正整數(shù)N, P。
輸出格式
輸出文件goblin.out僅含一行，一個非負整數(shù)，表示你所求的答案對P取余之后的結(jié)果。

輸入輸出樣例

輸入樣例#1

4 7

輸出樣例#1

3

解題思路

定義狀態(tài)變量 f [ i ] [ j ] 表示序列長度為 i 時有 j 個數(shù)不符合要求時的方案數(shù)，這里的“不符合要求”指的是后一個數(shù)大于前一個數(shù)，例如1,2,3這樣的序列，3對于2來說定義為不符合要求，故最終答案應(yīng)該為 f [ n ] [ 0 ] * 2，因為這種狀態(tài)只考慮了一種情況，還有可能后一個數(shù)小于前一個數(shù)而不符合要求的情況
那么狀態(tài)轉(zhuǎn)移方程就很好想了，有以下三種情況可以轉(zhuǎn)移：

• 考慮第 i + 1 個數(shù)插在了對其自身來說符合要求的位置，那么對當前已有的不符合要求的數(shù)的個數(shù)是沒有影響的，故轉(zhuǎn)移方程為：
  f [ i + 1 ] [ j ] += f [ i ] [ j ] ;
• 考慮第 i + 1 個數(shù)插在了一個當前不符合要求的數(shù)之前，那么這個數(shù)在 i + 1 插入之后就符合要求了，故轉(zhuǎn)移方程為：
  f [ i + 1 ] [ j - 1 ] += f [ i ] [ j ] * j ;
• 考慮第 i + 1 個數(shù)插在了當前已經(jīng)符合要求的數(shù)之前，那么在插入了 i + 1 之后就會再新增一個不符合要求的數(shù)，故轉(zhuǎn)移方程應(yīng)為：
  f [ i + 1 ] [ j + 1 ] += f [ i ] [ j ] * ( i - j ) ;

最終的答案就是 f [ n ] [ 0 ] * 2
在代碼實現(xiàn)過程中需要注意的就是取模，在沒有別的什么了
下面是C++代碼

數(shù)據(jù)規(guī)模和約定

對于20%的數(shù)據(jù)，滿足N≤10；
對于40%的數(shù)據(jù)，滿足N≤18；
對于70%的數(shù)據(jù)，滿足N≤550；
對于100%的數(shù)據(jù)，滿足3≤N≤4200，P≤1e9。

C++代碼

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rr register
using namespace std;

typedef long long LL;
const int maxn=4200+10;
LL n,m,p,ans;
LL f[maxn][maxn];

inline LL read(){//珂朵莉版快讀~~~
    int chtholly=0,willem=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')willem=-1;c=getchar();}
    while(c<='9' && c>='0'){chtholly=chtholly*10+(LL)(c-'0');c=getchar();}
    return chtholly*willem;
}

int main(){
    n=read(),p=read();
    f[1][0]=1;
    for(rr int i=1;i<=n;i++)for(int j=0;j<=i;j++){
        f[i+1][j]=(f[i+1][j]+f[i][j])%p;
        f[i+1][j-1]=(f[i+1][j-1]+f[i][j]*j%p)%p;
        f[i+1][j+1]=(f[i+1][j+1]+f[i][j]*(i-j)%p)%p;
    }
    ans=(f[n][0]<<1)%p;//位運算加速
    printf("%lld\n",ans);
    return 0;
}