卡特兰数
应用场景：
1.n个节点能组成几种二叉树
2.括号匹配给出n对括号，求可以组成的合法表达式的个数
3.凸多边形的三角划分
4.一个顺序为1~n的进栈序列，有多少种出栈序列
卡特兰数求解代码（从0开始，用的组合数方法求）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const int MOD=1e9+7;
ll fact[N];
ll inv_fact[N];
ll qpow(ll x,ll y){
ll base=x,ret=1;
while(y){
if(y&1)
ret=ret*base%MOD;
base=base*base%MOD;
y>>=1;
}
return ret;
}
void init(){
fact[0]=inv_fact[0]=1;
for(int i=1,inv;i<N;++i){
fact[i]=(fact[i-1]*i)%MOD;
inv=qpow(i,MOD-2);
inv_fact[i]=(inv_fact[i-1]*inv)%MOD;
}
}
ll C(int a,int b){
return ((fact[a]*inv_fact[b])%MOD*inv_fact[a-b])%MOD;
}
void solve(){
init();
int n;
cin>>n;
ll ans=((C(2*n,n)-C(2*n,n-1))%MOD+MOD)%MOD;
cout<<ans<<endl;
}
int main()
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
solve();
return 0;
}
|
题的变形：
括号匹配给出n对括号，k种括号，求可以组成的合法表达式的个数
答案就成了n的卡特兰数*pow(k,n)
字符串不同子串个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<cstdio>
#include<iostream>
#define maxn 100005
#define re register
int n,cnt=1,lst=1;
long long ans;
char S[maxn];
int fa[maxn<<1],len[maxn<<1],son[maxn<<1][26];
inline void ins(int c)
{
int f=lst,p=++cnt; lst=p;
len[p]=len[f]+1;
while(f&&!son[f][c]) son[f][c]=p,f=fa[f];
if(!f) {fa[p]=1;return;}
int x=son[f][c];
if(len[f]+1==len[x]) {fa[p]=x;return;}
int y=++cnt;
len[y]=len[f]+1,fa[y]=fa[x],fa[x]=fa[p]=y;
for(re int i=0;i<26;i++) son[y][i]=son[x][i];
while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];
}
int main()
{
scanf("%d",&n),scanf("%s",S+1);
for(re int i=1;i<=n;i++) ins(S[i]-'a');
for(re int i=2;i<=cnt;i++) ans+=(long long)(len[i]-len[fa[i]]);
printf("%lld\n",ans);
return 0;
}
|
字符串某一个子串的数目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include<bits/stdc++.h>
using namespace std;
int dp[1010][1010];
string s,t;
int main()
{
int len1,len2;
cin>>s>>t;
len1=s.size();
len2=t.size();
for(int i = 0 ; i <= len1 ; i++){
dp[i][0] = 1;
}
for(int i = 1 ; i <= len1 ; i++){
for(int j = 1 ; j <= len2 ; j++){
if(s[i - 1] == t[j - 1])
dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
else
dp[i][j] = dp[i - 1][j];
}
}
cout<<dp[len1][len2];
return 0;
}
|
数组不同子序列个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+5;
const int mod = 1000000007;
int a[N];
ll dp[N];
int vis[N];
int main()
{
int n;
while(cin >> n){
for(int i=1;i<=n;i++){
cin >> a[i];
}
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
dp[1]=1;
vis[a[1]]=1;
for(int i=2;i<=n;i++){
if(vis[a[i]]==0){
dp[i] = (dp[i-1]*2 + 1)%mod;
}else{
dp[i] = (dp[i-1]*2 - dp[ vis[a[i]] - 1 ] + mod) % mod;
}
vis[a[i]]=i;
}
cout<<dp[n]<<endl;
}
return 0;
}
|
两端相等子数组最大和，返回最后一次相等左，右位置和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include<bits/stdc++.h>
using namespace std;
int num[210000];
int main()
{
int t;
cin>>t;
while(t--){
int n,sum=0,sum1=0,l;
cin>>n;
for(int i=0;i<n;i++)
cin>>num[i],sum+=num[i];
for(int i=0;i<n;i++){
sum1+=num[i];
if(sum1>=sum/2){
l=i;
break;
}
}
int r=l+1,sum2=sum-sum1;
while(sum1!=sum2){
if(sum1>sum2)
sum1-=num[l--];
else
sum2-=num[r++];
}
cout<<l+n-r+1<<endl;
}
return 0;
}
|
