阿狸网站建设,用c 做网站设计系统的项目作业,高质量的赣州网站建设,举例说明商业网站的建设流程来源 卡特兰数 个人评价#xff08;一句话描述对这个题的情感#xff09; …~%?..,# *☆℃$︿★? 1 题面
一列火车n节车厢#xff0c;依次编号为1,2,3,…,n。每节车厢有两种运动方式#xff0c;进栈与出栈#xff0c;问n节车厢出栈的可能排列方式有多少种。
输入… 来源 卡特兰数 个人评价一句话描述对这个题的情感 …~%?..,# *☆℃$︿★? 1 题面
一列火车n节车厢依次编号为1,2,3,…,n。每节车厢有两种运动方式进栈与出栈问n节车厢出栈的可能排列方式有多少种。
输入
一个数n(n60000)
输出
一个数s表示n节车厢出栈的可能排列方式
样例
样例输入1
3样例输出1
52 分析题面
求卡特兰数的第n项不取模
有两种方式都能推出这是一道纯卡特兰数题
2.1 递推
“计数原理中的乘法原理总的方案数等于第一步的方案数和第二步的方案数之积”
以编号为 kkk 的车厢为界将列车分为两部分
一部分是在第 kkk 节车厢出栈前出栈的车厢一部分是在第 kkk 节车厢出栈后出栈的车厢
设在第kkk节车厢出栈前出栈的车厢的数量为 i(0ik)i(0ik)i(0ik)
则在第 kkk 节车厢出栈后出栈的车厢的数量为 (k−i−1)(k-i-1)(k−i−1)
前 iii 节车厢出栈的可能性数量有 F(i)F(i)F(i)
后 (n−i−1)(n-i-1)(n−i−1) 节车厢出栈的可能性数量有 F(k−i−1)F(k-i-1)F(k−i−1)
所以总的数量为 F(i)×F(k−i−1)F(i)\times F(k-i-1)F(i)×F(k−i−1)
由于当只有0节车厢即一节车厢也没有时方案数为111
所以F(0)1F(0)1F(0)1
因此我们可以得到一个递归公式
F(k)F(0)×F(k−1)F(1)×F(k−2)F(2)×F(k−3)...F(k−2)×F(1)F(k−1)×F(0)F(k)F(0)\times F(k-1)F(1)\times F(k-2)F(2)\times F(k-3)...F(k-2)\times F(1)F(k-1)\times F(0)F(k)F(0)×F(k−1)F(1)×F(k−2)F(2)×F(k−3)...F(k−2)×F(1)F(k−1)×F(0)
其中k1F(0)1其中k1F(0)1其中k1F(0)1
看出什么了吗
其实这道题就是Catalan number
只不过n的初值少111。。。
2.2 组合数
首先每一种进出栈的顺序都与出栈序列一一对应
也就是说如果我们用111表示进栈−1-1−1表示出栈
那么举个例子
出栈序列 1,3,4,21,3,4,21,3,4,2 与进出栈顺序 1,1,−1,1,1,−1,−1,−11,1,-1,1,1,-1,-1,-11,1,−1,1,1,−1,−1,−1 是对应的
那么对nnn个数的序列总的进出栈顺序不是就是给2n2n2n个111前面挑nnn个添加号
其他的添加−-−号共C2nn{\rm C}_{2n}^nC2nn种吗
答案是否定的这是因为出栈的前提是有进栈
于是要求每个排列中的前若干项和均不为负数
即排列1,−1,−1,1,1,−1,−1,11,-1,-1,1,1,-1,-1,11,−1,−1,1,1,−1,−1,1是无效的
那么无效的排列到底有多少呢
考虑MMM是所有无效的排列构成的集合
考虑其中第一次发现排列无效的时候也就是第一次发现其前若干项和为−1-1−1的时候
此时我们将包含使得前若干项和为−1-1−1的这一项开始的之前的所有项全都取相反数
那么就会得到一个新的排列
这个排列包含n1n1n1个111以及n−1n-1n−1个−1-1−1
设所有这样的排列构成集合NNN
显然这个M→NM\to NM→N的映射是一一映射的
NNN中的每一个排列从第一项往后累积求和的时候必然会出现和为111的情形
此时将排列中使得和为111的这一项连同之前的所有项全部取相反数
那么就会得到MMM中的一个排列
因此无效的排列共有C2nn−1{\rm C}_{2n}^{n-1}C2nn−1个
综上所有不同的出栈序列总数为C2nn−C2nn−1{\rm C}_{2n}^n-{\rm C}_{2n}^{n-1}C2nn−C2nn−1即C2nnn1\dfrac {{\rm C}_{2n}^n}{n1}n1C2nn
也就是卡特兰数
3 代码实现注释
3.1定义
//Cn为卡特兰数的第n项
int n;//输入
int ans[N];//高精度答案数组
int len1//答案的位数
int p[N];//质数
int c[N];//c[i]是Cn中p的个数
int tot;//2*n中质数的个数
bool vis[N];//埃氏筛标记数组3.2 输入
就输入一个n
scanf(%d,n);//输出的3.3 预处理
预处理质数这里我用的是埃氏筛用欧拉筛也行 for(int i2;in*2;i) {//预处理1-2n之间的质数if(!vis[i]) {//vis数组没有被标记过p[tot]i;//统计质数for(int ji;jN;ji) vis[j]1;//大量优化复杂度}//就是埃氏筛
} 3.4 高精度
这个乘法还是挺显然的吧
void jing(int x) {//高精乘法 乘xfor(int i1;ilen;i) ans[i]*x;//直接乘xlen6;//长度最多6for(int i1;ilen;i) {//每一位处理ans[i1]ans[i]/10;ans[i]%10;}//进位while(!ans[len]) len--;//将多加的长度剪掉
}3.5 计算
先考虑(n)小一点的做法我们可以直接用卡特兰数的线性递推公式:
fnfn−14n−2n1f_nf_{n-1}\frac{4n-2}{n1}fnfn−1n14n−2
然后看一眼数据显然不行
然后考虑一下优化
我们要换一个思路应该用这个公式:
CnC2nnn1C_n\frac{C_{2n}^n}{n1}Cnn1C2nn 大力感谢zjy提供的思路 3.5.1 转换公式
首先由卡特兰数的通项公式CnC2nnn−1C_n \frac{C_{2n}^n}{n-1}Cnn−1C2nn
⇒Cn!(2n)/(!n)2n1⇒Cn!(2n)(!n)2(n1)⇒C_n\frac{!(2n)/(!n)^2}{n1} \\ \ \\⇒C_n\frac{!(2n)}{(!n)^2(n1)}⇒Cnn1!(2n)/(!n)2 ⇒Cn(!n)2(n1)!(2n)
最终表示为阶乘形式Cn(2n)!n!(n−1)!C_n \frac{(2n)!}{n!(n-1)!}Cnn!(n−1)!(2n)!
再看一下算数基本定理
Ap1a1∗p2a2∗...∗pkakAp_1^{a_1}*p_2^{a_2}*...*p_k^{a_k}Ap1a1∗p2a2∗...∗pkak
注意到卡特兰数每一项都一定是一个整数
也就是说如果将如上公式的分子分母分解质因数
那么分母的各个因式指数上一定是可以被分子的各个因式相减抵消的
但是分子分母都是存在阶乘结构的那么就考虑然后对某个数的阶乘分解质因数
3.5.2 分解阶乘
其次一个质数p[i]p[i]p[i]在nnn中可分解的个数为n/p[i]n/p[i]n/p[i]
口胡一下证明 n!1×2×3×...×(n−1)×nn!1\times 2\times 3\times... \times(n-1)\times nn!1×2×3×...×(n−1)×n 所以在n!n!n!中即1−n1-n1−n中是p[i]p[i]p[i]的倍数的个数显然为n/p[i]n/p[i]n/p[i]个 然后在n!n!n!中可被至少包含kkk的mmm次方的个数x[m]x[m]x[m]为
x[m](2n)/p[i]m−n/p[i]m−(n−1)/p[i]mx[m](2n)/p[i]^m-n/p[i]^m-(n-1)/p[i]^mx[m](2n)/p[i]m−n/p[i]m−(n−1)/p[i]m
最终CnC_nCn中包含p[i]p[i]p[i]的个数为
所有nnn能被p[i]mp[i]^mp[i]m整除的mmm的x[m]x[m]x[m]之和
所以c[i]∑j1mx[j]c[i]\sum^m_{j1}x[j]c[i]∑j1mx[j]
口胡证明如下 证明1
不妨设k3∣n!k^3|n!k3∣n!且最多只能被kkk的3次方整除
当m1m1m1时x[1](2n)/k−n/k−(n−1)/kx[1](2n)/k-n/k-(n-1)/kx[1](2n)/k−n/k−(n−1)/k
当m2m2m2时x[2](2n)/k2−n/k2−(n−1)/k2x[2](2n)/k^2-n/k^2-(n-1)/k^2x[2](2n)/k2−n/k2−(n−1)/k2
当m2m2m2时x[3](2n)/k3−n/k3−(n−1)/k2x[3](2n)/k^3-n/k^3-(n-1)/k^2x[3](2n)/k3−n/k3−(n−1)/k2
由于xxx数组的定义是x[m]x[m]x[m]是n!n!n!即1−n1-n1−n中至少包含kkk的mmm次方的数的个数
所以n!n!n!中只包含k的1次方的数的个数为x[1]−x[2]x[1]-x[2]x[1]−x[2]
同理可得n!n!n!中只包含k的1次方的数的个数为x[2]−x[3]x[2]-x[3]x[2]−x[3]
又因为n!n!n!且最多只能被kkk的3次方整除所以n!n!n!中只包含k的1次方的数的个数为x[3]x[3]x[3]
所以总的包含的kkk的个数ccc为
c(x[1]−x[2])×1(x[2]−x[3])×2x[3]×3c(x[1]-x[2])\times1(x[2]-x[3])\times2x[3]\times3c(x[1]−x[2])×1(x[2]−x[3])×2x[3]×3
化简后得cx[1]x[2]x[3]cx[1]x[2]x[3]cx[1]x[2]x[3]
根据数学归纳法
c[i]∑j1mx[j]c[i]\sum^m_{j1} x[j]c[i]∑j1mx[j]
证毕 证明2
对于n!1×2×...×nn!1\times2\times...\times nn!1×2×...×n考虑它存在多少个质因子ppp
显然有⌊np⌋\lfloor\frac{n}{p}\rfloor⌊pn⌋个数有至少111个因子ppp那么有⌊np2⌋\lfloor\frac{n}{p^2}\rfloor⌊p2n⌋个数有至少222个因子ppp.........依次类推有⌊npx⌋\lfloor\frac{n}{p^x}\rfloor⌊pxn⌋个数有至少xxx个因子ppp 循环枚举每一个质因子对于每一个质因子
所以我们通过枚举1−2n1-2n1−2n的质数来进行拆分
再将拆分出的p[i]c[i]p[i]^{c[i]}p[i]c[i]乘进ansansans中
就ok了
可得代码 for(int i1;itot;i) {//枚举质数int nowp[i];while(nown*2) {//c[i]指出现的个数c[i]n*2/now-n/now-(n1)/now;now*p[i];}while(c[i]--) jing(p[i]);//乘p[i]的c[i]次方
}3.6 输出
输出高精ans数组即可
for(int ilen;i1;i--) {printf(%d,ans[i]);
}//注意要倒着输出3.7 总体代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N1200000;
int n,ans[N],len1,p[N],c[N],tot;
bool vis[N];
void jing(int x) {for(int i1;ilen;i) ans[i]*x;len6;//最多加六位*的数小于等于n*2for(int i1;ilen;i) {ans[i1]ans[i]/10;ans[i]%10;}while(!ans[len]) len--;
}//高精度乘法
int main(){scanf(%d,n);//初始化ans[1]1;//初始化高精ans1for(int i2;in*2;i) {if(!vis[i]) {p[tot]i;//统计质数for(int ji;jN;ji) vis[j]1;//排除合数//原因显然质数的k(k≠1)倍肯定不是质数,证明如下//质数的定义是一个数只有1和它本身两个因数称这个数叫做质数//质数(p[i])的k(k≠1)倍已经有了k和p[i]两个(不是1和它本身)的因数//综上所述质数的k(k≠1)倍肯定不是质数}//埃氏筛求2*n以内的质数} //预处理for(int i1;itot;i) {//枚举质数int nowp[i];while(nown*2) {//c[i]指出现的个数c[i]n*2/now-n/now-(n1)/now;now*p[i];}while(c[i]--) jing(p[i]);//高精乘法}//计算for(int ilen;i1;i--) {printf(%d,ans[i]);}//输出return 0;
}4 总结
就是卡特兰数高精的一种奇妙并且码量少的一种写法
完结撒花❀ ★,°:.☆(▽)/$:.°★ 。
