正題

題目鏈接:https://www.luogu.org/problemnew/show/P1375

---

題目大意

東西兩兩綁在一起，要求繩子不能交叉，求方案數。

---

解題思路

0表示壓入第i只貓，1表示彈出棧頂的貓并且和第i只貓綁在一起，這樣就能保證不會交叉。
也就是卡特蘭數。

---

$code$

#include<cstdio> #define ll long long using namespace std; const int P=1e9+7; ll n; ll power(ll x,ll b) {ll ans=1;while(b){if(b&1) ans=(ans*x)%P;x=(x*x)%P;b>>=1;}return ans; } ll C(ll n,ll m) {ll k1=1,k2=1;for(ll i=n-m+1;i<=n;i++)k1=k1*i%P;for(ll i=1;i<=m;i++)k2=k2*power(i,P-2)%P;return k1*k2%P; } int main() {scanf("%d",&n);ll k=C(2*n,n),z=power(n+1,P-2);printf("%d",k*z%P); }

總結

以上是生活随笔為你收集整理的P1375-小猫【卡特兰数】的全部內容，希望文章能夠幫你解決所遇到的問題。

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