卡特兰数&&prufer序列&&BSGS水题集

首先说一下BSGS的一个坑点：

解方程A^x≡B(mod p)

需要特判一个东西=>A%p==B%p==0?

如果相等的话puts("1")反之则无解。

因为如果A%p=0，那么无法移项，导致BSGS算法的错误

进入正题:

一卡特拉数（C(2*n,n)/(n+1)）用于处理01序列里任意位置0的个数>1的情况。。

但知道定义没用，重要的是打表找规律。

善于用next_permutation,搜索等工具找出前几项。

记住卡特兰数的前几项:1 2 5 14 42 132 429。(反正也只能求出这几项)

至于求法，先化到最简，取模可以用lucas,不取模的高精。

喜欢高精除的畜生就打高精除，不喜欢的就分解质因数，数据小的也可以O(n^2)枚举。

贴一下分解质因数的代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 #define MAXN 4000005
 5 int prime[MAXN],tot,n,frpr[MAXN],fenzi[MAXN],tot1;
 6 void pre()
 7 {
 8     for(int i=2;i<=2*n;i++)
 9     {
10         if(!frpr[i])
11         {
12             frpr[i]=i;
13             prime[++tot]=i;
14         }
15         for(int j=1;j<=tot;j++)
16         {
17             if(prime[j]*i>2*n)break;
18             frpr[prime[j]*i]=prime[j];
19             if(!(i%prime[j]))break;
20         }
21     }
22     return ;
23 }
24 void Get_pr(int x,int opt)
25 {
26     while(x!=1)
27     {
28         if(opt==0)fenzi[frpr[x]]++;
29         else fenzi[frpr[x]]--;
30         x/=frpr[x];
31     }
32     return ;
33 }
34 int main()
35 {
36     int p,ans=1;
37     scanf("%d%d",&n,&p);
38     pre();
39     for(int i=n+2;i<=2*n;i++)Get_pr(i,0);
40     for(int i=1;i<=n;i++)Get_pr(i,1);
41     for(int i=1;i<=tot;i++)
42     {
43         while(fenzi[prime[i]]>0)
44         {
45             ans=1ll*ans*prime[i]%p;
46             fenzi[prime[i]]--;
47         }
48     }
49     cout<<ans<<endl;
50     return 0;
51 }

View Code

二 prufer序列

用n-2个点表示n个节点的有标号树，可以证明prufer序列和对应的树都是唯一确定的。

由此可以得到一些推论：

1. n个点构成的无根树的个数：n^(n-2)

2. 确定n个点度数分别为d1,d2…时无根树个数： (n-2)!/((d1-1)!*(d2-1)!*…)

3. n个点的有标号有根树的个数： n*n^(n-2)=n^(n-1)

4. 所有节点的度之和为n*2-2

除了统计树的个数，别的。。。就没啥了(听说还能优化暴力枚举)

三 BSGS

模板：

 1 void insert(int x,int d)
 2 {
 3     int k=x%mod;
 4     val[++cnt]=x;nxt[cnt]=head[k];id[cnt]=d;head[k]=cnt;
 5 }
 6 int find(int x)
 7 {
 8     int k=x%mod;
 9     for(int i=head[k];i;i=nxt[i])
10         if(val[i]==x)return id[i];
11     return -2333;
12 }
13 int BSGS()
14 {
15     int m=ceil(sqrt(p*1.0)),bs=1;
16     int now=1;insert(B%p,0);//insert A^j*B
17     if(B==1)return 0;
18     for(int i=1;i<m;i++)
19     {
20         now=1ll*now*A%p;
21         insert(1ll*now*B%p,i);
22     }
23     now=1ll*now*A%p;
24     for(int i=m;;i+=m)
25     {
26         bs=1ll*bs*now%p;
27         int x=find(bs);
28         if(x!=-2333)return i-x;
29         if(i>p)break;
30     }
31     return -2333;
32 }

View Code

除了上面提到的坑点，还有就是根据题意啦