(\)

(Description)

---

鍵盤上有三個鍵，敲擊效果分別是：

在輸出序列尾部添加一個左括號
在輸出序列尾部添加一個右括號
刪除輸出序列尾部的第一個元素，若輸出序列為空，則什么都不發生

求恰好按鍵(N)次，輸出序列是一個合法的括號序列的方案數對(P)取模的值。

只要按鍵順序或內容有一個位置不同就視為不同。

(Nin [1,10^3])，(Pin [1,10^4])，不保證(P)為質數。

(\)

(Solution)

---

神仙出題人神仙解法......

首先有一個結論，對于一個長度確定的序列，其輸出的方案數是確定的，且與具體每一個位置的內容無關。

為什么呢？因為每一個位置輸出是確定的，所以最后操作序列只需要改成符合要求的即可。

于是我們先考慮求出輸出一個長度為(i)的序列的方案數，設(f[i][j])表示一共按鍵(i)次，當前輸出序列長度為(k)的方案數。轉移就很自然，考慮是新加上一個還是刪掉一個末尾的。因為序列確定，如果新加上的是輸出序列，那么新加上的方案是唯一的，而刪除就不需要確定末尾是什么了。注意退格鍵在輸出序列為空時也可使用，有轉移方程：

[f[i][j]=(f[i-1][max(0,j-1)]+f[i-1][j+1] imes 2)\%mod
]

然后就是考慮長度為(i)的合法序列方案數了，這不是(Catalan)嗎！一個非質數打你臉上分解質因數太麻煩了，然后出題神仙就給出了神仙(DP)做法。設(g[i][j])為當前輸出序列長度為(i)，強制所有右括號合法，有(j)個左括號不合法的方案數。那么就有自然簡單易懂直接的轉移方程：

[g[i][j]=(g[i-1][j+1]+(j>0?g[i-1][j-1]:0))\%mod
]

代表新放一個右括號抵消掉一個左括號或新放一個左括號。

[ans=sum_{i=0}^{lfloorfrac N 2floor} f[n][i imes2] imes g[i imes 2][0]
]

(\)

(Code)

---

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define R register
#define N 1010
using namespace std;
 
int n,mod,ans,f[N][N],g[N][N];
 
int main(){
  scanf("%d%d",&n,&mod);
  f[0][0]=1;
  for(R int i=1;i<=n;++i)
    for(R int j=0;j<=i;++j)
      f[i][j]=(f[i-1][j+1]+(j!=0?f[i-1][j-1]:0))%mod;
  g[0][0]=1;
  for(R int i=1;i<=n;++i)
    for(R int j=0;j<=i;++j)
      g[i][j]=(g[i-1][max(0,j-1)]+(g[i-1][j+1]<<1))%mod;
  for(R int i=0;i<=(n>>1);++i) (ans+=g[n][i<<1]*f[i<<1][0])%=mod;
  printf("%d
",ans);
  return 0;
}

總結

以上是生活随笔為你收集整理的[ Nowcoder Contest 165 #D ] 合法括号序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。