数论的第二舞——卡特兰数
当然了，虽然主角是卡特兰数，但是我们该学的数论还是不能落下的，首先先来介绍一个开胃小菜线性筛
1.积性函数：
2.线性筛
线性筛的筛选素数的时间复杂度更低，可以达到O(n)的时间复杂度
将每一轮进行筛选的数 n 表示为 i * su[ j ] (即 n = i * su[ j ])。i 为 n 的最大因子，su[ j ] 为 n 的最小因子(最小因子必为质数。如果不为质数，则该数可以分解为两个数的乘积, 与最小因子矛盾)
每个数都只会被筛一次，因此时间复杂度可以达到O(n)
对于一个质数来说，最多会达到他本身，对于一个合数来说，最多会达到他的最小质数
数 n 能被分解成有限个质数相乘，（在这有限个质数当中可能包含了相同的质数，比如300可以分解为2 * 2 * 3 * 5 * 5），将这有限个质数从小到大排列，取出其中最小的质数即为最小因子，再将剩下的数乘起来即为最大因子（比如300的最小因子为2，最大因子为150）
因此就可以完成线性筛的板子
vis[1]=1;//vis数组用于记录某个数是否是素数，如果是1则不是素数，反之则是
int cnt=0;//用于统计素数数组的长度
for(int i=2;i<=n;i++)
{
if(!vis[i])//是素数，存进素数数组
su[++cnt]=i;
for(int j=1;j<=cnt&&i*su[j]<=n;j++)//进行第i轮的询问
{
vis[i*su[j]]=1;//将其标记为合数
if(i%su[j]==0)//如果会被整除就立马结束
break;
}
}ps：也是来到了本篇博客的重点，前面两个只是为了后面一道题的铺垫
3.卡特兰数
我们先列举卡特兰数的一部分序列：1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440
1.通项式
卡特兰数的通项式： 我们用f(n)表示，第n想的卡特兰数
这时我们还可以通过这个通项式推导出来其另一种表示形式
2.递推式
3.卡特兰数的应用：
这里的理解我认为可以将别人总结的多种情形再总结一下，说白了就是封闭式的问题都可以用到卡特兰数，什么叫做封闭式的问题呢？
我的理解就是一种有始有终的问题，就像左右括号的匹配，一个左括号必然要有一个右括号去匹配，这个我也确实不好讲清楚，看个人的理解了
因此可以有以下的应用场景
在开始讲解场景之前，我们首先来考虑一个问题，在数学上如何去确定两个集合中的值是相等的
假设我们有a,b两个集合，假设我们有一种映射关系f，可以让b集合中的每一个数映射过来都是a集合中的不同的数，那么a>=b，如果我们还有一种隐射关系g，可以让a集合中的每一个数隐射过来都是b集合中的不同的数，那么就可以说a<=b，因此a=b,即两个集合中的元素相同
（1）括号匹配的场景
给定N个左括号，N个右括号，它们自由组合，必须全部使用，能得到多少个合法的组合
我们能否将这个问题转换一下，假设我们的左括号是是向右上走一步，右括号是向右下走一步，那么最终我们一定会走到(2*n,0)这个点，我们可以来讨论一下不合法的情况，什么时候会存在不合法的情况，那就是我们的前缀出现右括号的数量大于左括号的数量的时候，那种情况放在我们的数学结构中就是，只要y轴上的值小于0，那么就是不合法的
我们想要求合法的序列的种数，我们可以用总的排列数-不合法的排列数=合法的排列数
总的排列数为C（n，2*n）即从2*n个位置里面挑n个作为左括号的位置
我们此时来考虑不合法的数量，因为我们刚才提到一个重要的点，不合法的序列中，一定存在一个前缀使得左括号的数量比右括号的数量少1
比如说: ( ) ) ( ( ) 这种就是不合法的，因为前缀为( ) )很明显右括号的数量大于左括号
假设我们将前缀后面的括号都进行反转，那么上面那个括号序列就变成了( ) ) ) ) (
这样左括号的数量=右括号的数量-2，我们此时可以将这个翻转操作称为映射关系f
因此我们不合法的序列,就变成了n-1个左括号和n+1个右括号，用数学公式表示就是C(n-1,2*n)
因此我们合法的个数就可以直接用组合数学求出来了，即为：
我们可以发现，这不就是卡特兰数的第n项通项式的推导吗？对这就是卡特兰数
（2）入栈出栈问题
给你n个数字判断，总共有多少种出栈序列
这个和上面那个还是一样的，只不过是问法不同的括号匹配问题罢了，我们首先来看一下对于只有1,2两个数都有哪些操作吧
第一种:1进栈 ( '(' ) 2进栈 ( '(' ) 1出栈( ')' ) 2出栈( ')' )
第二种:1进栈 ( '(' ) 1出栈( ')' ) 2进栈 ( '(' ) 2出栈( ')' )
我们可以将进栈变成左括号，出栈变成右括号，结果还是一样的
所以我习惯性将这种问题，归类到封闭类问题
剩下的情景我就不一一列举了，可以自己想一下
例题
P1641 [SCOI2010] 生成字符串
这个不就是卡特兰数结论的板子吗，但是中间可能会很大，有取模，因此我们可以考虑用线性求逆元，这样O(n)的时间复杂度就可以求出来，然后我们之间敲代码就过了
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
int f[2000005];
int inv[2000005];
int mod=20100403;
int fast(int a, int b)
{
long long result = 1;
long long base = a;
while (b > 0)
{
if (b % 2 == 1)
{
result = (result * base) % mod;
}
base = (base * base) % mod;
b /= 2;
}
return result;
}
int cal(int n,int k)
{
return f[n]*inv[n-k]%mod*inv[k]%mod;
}
signed main()
{
cin>>n>>m;
f[0]=1;
for(int i=1;i<=n+m;i++)
{
f[i]=(f[i-1]*i)%mod;
}
inv[n+m]=fast(f[n+m],mod-2);
for(int i=n+m-1;i>=0;i--)
{
inv[i]=inv[i+1]*(i+1)%mod;
}
cout<<(cal(n+m,n)-cal(n+m,m-1)+mod)%mod;
return 0;
}P3200 [HNOI2009] 有趣的数列
我们会发现这题其实也是一个卡特兰数的板子，但是呢？我们的p并不一定是质数，直接把我们逆元的路堵死了，那么我们该如何操作呢？
我后面实在是没想到，于是就去看了大犇们的思路，发现实在是太妙了，我们由唯一分解定理可以知道，任何一个数都可以被拆分成若干个质数的乘积的形式，因此我们可以用线性筛去将所有素数筛选出来，然后用cnt数组去统计每个素数出现的次数，用mp去统计每个数的最小质因数，慢慢分解成质数的形式，最后统计就可以了
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,p;
bool vis[2000005];
int su[2000005];
int cnt[2000005];//统计每个数的指数
int mp[2000005];
int len;
int fast(int a, int b)
{
long long result = 1;
long long base = a;
while (b > 0)
{
if (b % 2 == 1)
{
result = (result * base) ;
}
base = (base * base) ;
b /= 2;
}
return result;
}
signed main()
{
cin>>n>>p;
vis[1]=true;
len=0;
for(int i=2;i<=2*n;i++)//先筛选出素数
{
if(!vis[i])
{
su[++len]=i;
mp[i]=i;
}
for(int j=1;j<=len&&i*su[j]<=2*n;j++)
{
vis[i*su[j]]=true;
mp[i*su[j]]=su[j];
if(i%su[j]==0)
break;
}
}
for(int i=1;i<=n;i++)
{
cnt[i]=-1;
}
for(int i=n+2;i<=2*n;i++)
{
cnt[i]=1;
}
for(int i=2*n;i>=2;i--)
{
if(vis[i]==1)
{
cnt[mp[i]]+=cnt[i];
cnt[i/mp[i]]+=cnt[i];
}
}
int ans=1;
for(int i=2;i<=2*n;i++)
{
if(vis[i]==0)
ans=(ans*fast(i,cnt[i]))%p;
}
cout<<ans;
return 0;
}原文地址：https://blog.csdn.net/2301_80475191/article/details/143030557
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！