題目描述
傳說很久以前，大地上居住著一種神秘的生物：地精。
地精喜歡住在連綿不絕的山脈中。具體地說，一座長度為N的山脈H可分為從左到右的N段，每段有一個[b][u]獨一無二[/u][/b]的高度Hi，其中Hi是1到N之間的正整數。
如果一段山脈比所有與它相鄰的山脈都高，則這段山脈是一個山峰。位于邊緣的山脈只有一段相鄰的山脈，其他都有兩段（即左邊和右邊）。
類似地，如果一段山脈比所有它相鄰的山脈都低，則這段山脈是一個山谷。
地精們有一個共同的愛好——飲酒，酒館可以設立在山谷之中。地精的酒館不論白天黑夜總是人聲鼎沸，地精美酒的香味可以飄到方圓數里的地方。
地精還是一種非常警覺的生物，他們在每座山峰上都可以設立瞭望臺，并輪流擔當瞭望工作，以確保在第一時間得知外敵的入侵。
地精們希望這N段山脈每段都可以修建瞭望臺或酒館的其中之一，只有滿足這個條件的整座山脈才可能有地精居住。
現在你希望知道，長度為N的可能有地精居住的山脈有多少種。兩座山脈A和B不同當且僅當存在一個i，使得Ai≠Bi。由于這個數目可能很大，你只對它除以P的余數感興趣。
輸入輸出格式
輸入格式：
?
輸入文件goblin.in僅含一行，兩個正整數N, P。
?
輸出格式：
?
輸出文件goblin.out僅含一行，一個非負整數，表示你所求的答案對P取余之后的結果。
?
輸入輸出樣例
4 7
3
說明
說明：共有10種可能的山脈，它們是：
1[u]3[/u]2[u]4[/u] 1[u]4[/u]2[u]3[/u] [u]2[/u]1[u]4[/u]3 2[u]3[/u]1[u]4[/u] 2[u]4[/u]1[u]3[/u]
[u]3[/u]1[u]4[/u]2 [u]3[/u]2[u]4[/u]1 3[u]4[/u]1[u]2[/u] [u]4[/u]1[u]3[/u]2 [u]4[/u]2[u]3[/u]1
其中加下劃線的數位表示可以設立瞭望臺的山峰，其他表示可以設立酒館的山谷。
【數據規模和約定】
對于20%的數據，滿足N≤10；
對于40%的數據，滿足N≤18；
對于70%的數據，滿足N≤550；
對于100%的數據，滿足3≤N≤4200，P≤109。
?
題意：求波動序列的個數
首先，了解波動序列的對稱性
序列如果為 1 4 2 5 3
對稱序列為 5 2 4 1 3
如果原序列開始遞減，那么同n+1減每個數，就變成了遞減序列的對稱遞增序列
所以我們只需要求遞減序列，乘2就是總個數
dp[i][j] 表示 前i個數的排列中，第1個數為j，且開始遞減的序列個數
f[i][j] 表示 前i個數的排列中，第1個數為j，且開始遞增的序列個數
當第1個數是j時，后面可以填1,2,3，……j-1，j+1，j+2……n
把>j的每個數-1，就是1,2,3，……j-1，j，j+1，j+2……n-1
即變成了n-1的排列
如果開始遞減
當第1個數是j時，將>j的數全部-1，那么后面可以填的數就是一個n-1的排列
這個排列要求 第一個數<j，且開始遞增
即dp[i][j]= Σ f[i-1][k] ?k∈[1,j-1]
根據對稱性，dp[i][j]= Σdp[i-1][k] ?k∈[i-j+1,i-1]?
時間復雜度：O（n^3），空間復雜度：O（n^2）
使用前綴和優化，可以 優化到時間O（n^2）,空間O（n）
?
沒有用前綴和優化的代碼：
#include<cstdio> #define N 4201 using namespace std; int n,p,ans; int dp[N][N],sum[N]; int main() {scanf("%d%d",&n,&p);for(int i=1;i<=n;i++) dp[1][i]=1;for(int i=2;i<=n;i++)for(int j=2;j<=i;j++)for(int k=i-j+1;k<=i-1;k++) dp[i][j]=(dp[i-1][k]+dp[i][j])%p;for(int i=1;i<=n;i++) ans=(ans+dp[n][i])%p;ans=ans*2%p;printf("%d",ans); }
?
前綴和優化AC代碼：
#include<cstdio> #include<cstring> #include<algorithm> #define N 4201 using namespace std; int n,p,ans; int dp[N],sum[N]; int main() {scanf("%d%d",&n,&p);for(int i=1;i<=n;i++) dp[i]=1;for(int j=1;j<=n;j++) sum[j]=(sum[j-1]+dp[j])%p;for(int i=2;i<=n;i++){dp[1]=0; for(int j=2;j<=i;j++) dp[j]=(sum[i-1]-sum[i-j]+p)%p;for(int j=i+1;j<=n;j++) dp[j]=0;for(int j=1;j<=n;j++) sum[j]=(sum[j-1]+dp[j])%p;}for(int i=1;i<=n;i++) ans=(ans+dp[i])%p;ans=ans*2%p;printf("%d",ans); }
?
)
)
