題目鏈接：?http://acm.hdu.edu.cn/showproblem.php?pid=5673
題目描述： 一個人從原點開始向右走， 要求N秒后回到原點， 且過程中不能到負半軸， 人有兩種操作， 走動或者停止， 問總共有多少種方案？
解題思路： 類似于括號匹配問題， 和那個我去年這個時候接觸到的最裸的不能越過對角線的正方形走到對角問題， 卡特蘭數， 從2開始枚舉走動步數， 然后剩下的就是不動的步數， 用不動的步數做個填充就可以了， 設計到取模， 需要逆元
代碼：?
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #include <map> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define mem0(a) memset(a,0,sizeof(a)) #define meminf(a) memset(a,-0x3f,sizeof(a)) #define fi(n) for(i=0;i<n;i++) #define fj(m) for(j=0;j<m;j++) #define sca(x) scanf("%d",&x) #define ssca(x) scanf("%s",x) #define scalld(x) scanf("%I64d",&x) #define print(x) printf("%d\n", x) #define printlld(x) printf("%I64d\n",x) #define de printf("=======\n") #define yes printf("YES\n") #define no printf("NO\n") typedef long long ll; using namespace std;const int mod = 1e9+7; const int maxn = 1e6+100;ll inv[maxn]; ll h[maxn]; ll c[maxn];void init() {inv[1] = 1;for( int i = 2; i < maxn; i++ ) { // 預處理逆元inv[i] = (mod - mod / i) * inv[mod%i] % mod;} }int main() {init();int t;int n;h[0] = h[1] = 1;for( int i = 2; i < maxn; i++ ) { // 卡特蘭數h[i] = h[i-1] * (4*i-2)%mod * inv[i+1] % mod;}sca(t);while( t-- ) {sca(n);ll ans = 1;c[0] = 1;for( int i = 1; i <= n; i++ ) { // 組合數c[i] = c[i-1] * (n-i+1) % mod * inv[i] % mod;}for( int i = 1; ; i++ ) {int k = n - (i<<1);if( k < 0 ) break;ans = (ans + h[i] * c[k]) % mod;}printf( "%lld\n", ans );}return 0; }
思考： 很裸的卡特蘭數， 組合數學很有意思， 然后就是說我感覺現在需要開始整理一下板子了， 比如說這個， 還有那個神題等等， 洗完澡回來再說， 我好菜啊
http://acm.hdu.edu.cn/showproblem.php?pid=5673
?
