文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

來源：https://tianchi.aliyun.com/oj/15165469968503404/76745683739284070

2. 解題

按道理可以DP暴力求解，但是數(shù)據(jù)規(guī)模太大，會超時的

手算前幾項，然后去 oesi 網(wǎng)站查詢數(shù)列，找到 大施羅德數(shù)，就是本題的答案

但是這個數(shù)列的遞推公式是： $$F_n=F_{n?1}+\sum _{k=0}^{n?1}{F}_k?F_{n?1?k}$$

是 $O(n^2)$ 時間復(fù)雜度，會超時

又查到 超級卡特蘭數(shù)： $$F_n?(n+1)=(6?n?3)?F_{n?1}?(n?2)?F_{n?2}$$

發(fā)現(xiàn)，除了第 0 項以外，超級卡特蘭數(shù) X 2 = 大施羅德數(shù)。厲害！

---

另外，超級卡特蘭數(shù)，要求 $F_n$ 要除以 $(n+1)$，要用到除法的求模轉(zhuǎn)換方法。
除法是無法直接求模的。有以下方法。

除法求模 + 快速冪

a / c mod p = a / c mod p * 1 = a / c mod p * c^(p-1) mod p = a * c^(p-2) mod p

或者 乘法逆元法

inv[1] = 1; for (int i = 2; i <= n; ++i) {inv[i] = (mod - mod/i) * inv[mod%i] % mod;//求模運算的乘法逆元 }

---

解答：

class Solution {vector<long long> catalan;int mod = 1e9+7; public:/*** @param n: The number of pyramid levels n* @param k: Possible coordinates k* @return: Find the sum of the number of plans*/int pyramid(int n, vector<int> &k) {// write your code herelong long sum = 0;catalan = vector<long long>(n+1, 0);catalan[0] = 1;catalan[1] = 1;vector<long long> inv(n+1);inv[1] = 1;for (int i = 2; i <= n; ++i){inv[i] = (mod - mod/i) * inv[mod%i] % mod;//求模運算的乘法逆元}for(int i = 2; i <= n; i++){catalan[i] = ((catalan[i-1]*(6*i-3)%mod)-((i-2)*catalan[i-2]%mod)+mod)*inv[i+1]%mod;}for(int i = 0; i < k.size(); i++){sum = (sum+cal(n,k[i]))%mod;}return sum;}long long cal(int n, int k){if(n == k) return 1;return (catalan[n-k]*2)%mod;} };

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的阿里云 超级码力在线编程大赛初赛 第2场 题目4. 小栖的金字塔（超级卡特兰数+除法求模/乘法逆元）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。