題目描述

輸入格式

一行兩個整數 n 和 P， 意義如題面所示。

輸出格式

一行一個整數， 表示有多少種切法。

輸入樣例

【樣例一輸入】
6 1000000007

輸出樣例

【樣例一輸出】
14

題解：

?????? 我們用f[i-2]來表示將凸i邊形劃分的方案數，那么我們設一個凸n邊形的頂點順時針順序依次為p1，p2……pn，顯然p1和pn相鄰。現在我們選點pk，（k不為1和n），那么p1，pn，pk會把圖形分成兩部分+p1pnpk這個三角形，特殊的，當k=n-1或k=2時，我們把它看成分成了一個n-1邊形和一個0邊形。又因為0邊形無法劃分，我們暫定f[0]=1(表示0邊形的劃分數)。且由常識可知f[1]=1。

?????? 現在我們就可以得出遞推式：f[i-2]=f[0]*f[i-3]+f[1]*f[i-4]+……+f[i-3]*f[0]；由此可觀察出這就是我們所熟悉的卡特蘭數，求n邊形的劃分方案，就是求卡特蘭數的第n-2項。

?????? 在這里先介紹一下卡特蘭數的數學遞推式：

???? ? h(n)=C(2n,n)/(n+1)??? h(n)=h(n-1)*(4*n-2)/(n+1); ? h(n)=c(2n,n)-c(2n,n-1)

?????? 接下來就好簡單啦，不就求第n-2項嗎？

?????? 等等，真的簡單嗎？對于本題，n<=10,000,000，而且mod的p還不是質數！！！

?????? 假如我們質因數分解，用最小表示法處理f[n-2]，時間復雜度高達O（nlogn），所以我們必須找更優的方法。

?????? 我們的最終目的是用最小表示法表示f[n-2]，那么我們只需知道每個質數出現的個數就ok了。比如質數2，1-n中出現2的有n/2次，出現2^2的有n/4次，……，所以質數2出現的次數為

n/2+n/4+……+n/2^m，所以貼代碼（這個需要自己理解一下）：

#include<algorithm> #include<fstream> #include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> using namespace std;int n,p,tot,pri[10000010],vis[20000020]; long long mi[10000010]; long long ans;void Make_pri() {for (int i=2; i<=2*n; i++){if (vis[i]==0) {tot++; pri[tot] = i;}for (int j=1; j<=tot; j++){long long x = (long long)pri[j]*(long long)i;if (x>2*n) break; vis[x] = 1;if (i%pri[j]==0) break;}} }void Add(int len,int cur) {for (int i=1; i<=tot; i++){long long k = pri[i];while (k<=len){mi[i]+=(long long)cur*(long long)(len/k);k = k*pri[i];}} }void Fast_mi() {for (int i=1; i<=tot; i++){long long a = pri[i],b = mi[i];while (b>0){if (b%2==1) ans = ((long long)ans*(long long)a)%p;b = b/2; a = ((long long)a*(long long)a)%p;}} }int main() {freopen("c.in","r",stdin);freopen("c.out","w",stdout);scanf("%d%d",&n,&p);Make_pri(); n = n-2;Add(2*n,1); Add(n,-1); Add(n+1,-1); ans = 1;Fast_mi();printf("%I64d\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/Janous/p/7571608.html

總結

以上是生活随笔為你收集整理的蛋糕（卡特兰数）的全部內容，希望文章能夠幫你解決所遇到的問題。

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