部分内容来自学长。
Catalan数
梳理
-
定义：
-
n个不同的数依次进栈，其出栈序列的种类数
我们设 $ f[t] $ 表示 $ t $ 个数依次进栈，其出栈序列的个数
首先显然f[0]=1；
那么我们拿出一个数 $ a $ ，设他被压入之后有 $ i $ 个数曾经被压入过，显然这些数在 $ a $ 弹出前定已弹出，那么这些数的方案数为 $ f[i] $
那么除了 $ a $ 和曾经压在 $ a $ 上的数 进出的方案数和之前的 $ f[i] $ 是不互相影响的，这些方案的总数为 $ f[n-i-1] $
有没有很熟悉？
没错，因为数 $ a $ 是随便拿的，所以 $ i $ 可以取 $ 0dots n-1 $ 中的任何一个数，再来表示我们的思路，就可以化成 $ Catalan $ 的递归定义
-
长度为 $ 2n $ 的合法括号序列数
将一个(视为入栈，一个)视为出栈，就转化成了上一个问题。 -
圆上有 $ 2n $ 个不同的点两两连接，连出的弦均不相交的方案数
把连线看成有向边，每个起点视为入栈，每个终点视为出栈即与前证同理。 -
从 $ (0,0) $ 走到 $ (n,n) $ (只能向上或向右),不越过对角线的方案数
向右走视为入栈，向上走视为出栈，即与前证同理。 -
凸 $ n $ 边形 $ (ngeq 3) $ 的三角划分数
这个不太一样。
设凸 $ t $ 边形 $ (tgeq 3) $ 的三角划分数为 $ f[t-2] $
显然 $ f[0]=f[1]=1 $ ;（ $ f[0] $ 是我们这里特别规定的）
我们搞一个三角形出来，凸 $ n $ 边形没被划分部分就分成两个新多边形，设一组是 $ i+2 $ 边形，则另一组是 $ n-i-1 $ 边形，那么此时有 $ f[i]*f[n-i-3] $ 种方案。
总方案数就可以化成 $ Catalan $ 的形式
。
-
阶梯的矩形划分数
以一个阶为顶点做矩形，则剩下的阶被分成了 $ i $ 个和 $ n-i-1 $ 个。
其他可以自行理解。 -
$ n $ 个不同的节点组成的有根二叉树的方案数
这个比较简单。
设以一个结点为根的子树大小为 $ t $ ，这个子树的方案为 $ f[t] $
设根节点的左子树大小为 $ i $ ，则右子树大小为 $ n-i-1 $
其他可以自行理解。
有趣的数列
我们把所有数从小到大依次放入，把奇数位和偶数位分开，那我们在往里加东西的时候肯定是挑第一个空位加。
如果当前奇数位上数的个数大于偶数位上数的个数，就不合法。
抽象一下，既然合法时奇数位上数的个数不大于偶数位上数的个数，就可以抽象成前面那个不越过对角线的问题。
于是答案就是卡特兰数，数据范围大得写高精，这里用 $ frac{C_{2n}^{n}}{n+1} $ 加分解质因数就比较方便
树屋阶梯
裸题，可以参考前面阶梯的矩形划分数一节
Prufer序列
梳理
定义
一个重要的性质
节点x在无根树中的度数=x在prufer序列中出现的次数+1
理解：每次删除和一个节点相邻的叶节点时这个节点进去一次，这个节点成为叶子后进去的是他的最后一个相连的点，这一次没有算上所以 $ +1 $ 。
明明的烦恼
构造 $ prufer $ 序列，因为对于每个出度为 $ d[i] $ 的点，他在序列中出现的次数为 $ d[i]-1 $ ，所以我们把能确定出度的点出现次数求和为 $ sum $ ，然后从序列的 $ n-2 $ 个数里选 $ sum $ 个位置用来放，再组合求出每个点放的位置的方案相乘。对于出度随便的点，我们就随便放。
令 $ sum=sumlimits_{iin (d[i]!=-1)}(d[i]-1) $ ， $ cnt=sumlimits_{iin (d[i]!=-1)}1 $ ，
答案：
BSGS
梳理
分为狭义 ( ext{BSGS}) 和广义 ( ext{BSGS}) ，以及扩展 ( ext{BSGS})
狭义BSGS
求方程 $ A^xequiv B(mod p) $
这是一个用分块思想实现的方法。
我们先随便找一个数 $ S $ ，那么先预处理出 $ A0,A1,dots,A^{S-1} mod p $ 的值
那么考虑这样一个方程：
那么
那么我们枚举每一个 $ a $ ，然后看是否存在满足条件的 $ Bcdot A^b $ ，这个过程我们可以通过把 $ Bcdot A^b $ 扔到 $ map $ 里实现。（或者手写 $ hash $ 不过我有点懒）找到以后，答案就是 $ aS-b $ 。
当然，这里也可以用 $ A^{aS+b}equiv B(mod p) $ 这个方程，但是这样一来我们要查的变成了 $ frac{B}{A^b} $ ，如果 $ A,B $ 是个数求逆元也还行，但是如果拓展到广义 ( ext{BSGS}) ，可能会需要矩阵求逆，就会麻烦一些，不如直接用乘法解决。
那么话说回来， $ S $ 是我们刚刚随便找的，那他取哪个值最好呢？显然原算法时间复杂度是 $ O(S+frac{p}{S})的 $ ，所以这里取 $ S=sqrt{p} $ 显然最优。
写这篇时突然发现了个问题，为啥是用 $ p $ 做被除数？
因为 $ A $ 的逆元是 $ A^{p-2} $ ，所以 $ A^{p-1}equiv 1 (mod p) $ ，由此 $ A^{p-1}equiv A^0 (mod p) $
于是 $ A^{p+n-1}equiv A^n (mod p) $ ，这是一个循环节，就没问题了。
这里也发现，必须当 $ gcd(A,p)==1 $ 时才能用普通的 ( ext{BSGS}) ，否则我们走扩展 ( ext{BSGS}) 。
广义BSGS
求一个嵌套的函数满足模 $ p $ 意义下值等于某个数时的嵌套层数 $ x $
这个函数我们可以用矩阵表示，所以就把狭义里头加个矩阵快速幂，用 $ A^{aS}equiv Bcdot A^b(mod p) $ 这个方程不用求逆。
扩展BSGS
用来处理 $ A^xequiv Bpmod{p} $ 中 $ A,B $ 不互质的问题
首先肯定想把他转化成 (A,B) 互质的形式，考虑原来方程的等价形式：$ A^x + pk = B $
即 $Acdot A^{x-1} + pk = B $，由裴蜀定理可得：方程有解当且仅当 (gcd(A,p)|B)，所以这时可以左右同除 (d=gcd(A,p))
得到 (frac{A}{d}cdot A^{x-1}+kcdot frac{p}{d}=frac{B}{d})，等价于 (frac{A}{d}cdot A^{x-1}equiv frac{B}{d}pmod{frac{p}{d}})
这个形式也可以用 ( ext{BSGS}) 求，不过是算的时候多乘一个数
重复这个过程直到当前的 (gcd(A,p)=1)，就可以用普通 ( ext{BSGS}) 求解，记这样处理的次数为 (g)，
最后就得到 (frac{A^g}{d}cdot A^{x-g}equiv frac{B}{d} pmod{frac{p}{d}})
那么一遍 ( ext{BSGS}) 解这个方程，因为他和原方程是等价的，最后答案加上 (g) 就好
code:
#include<bits/stdc++.h>
using namespace std;
unordered_map<int,int>mp;
int a,b,p,ans;
inline int ksm(int a,int b,int p){ a%=p; int res=1;
for(;b;b>>=1,a=1ll*a*a%p)if(b&1)res=1ll*res*a%p; return res%p;
}
inline int gcd(int a,int b){
if(!b)return a;
return gcd(b,a%b);
}
inline int bsgs(int a,int b,int p,int k){
a%=p; b%=p; mp.clear();
if(!a)return b?-1:0;
int t=ceil(sqrt(p)),x=b;
for(int i=0;i<=t;i++)mp[x]=i,x=1ll*x*a%p;
a=ksm(a,t,p); x=1ll*a*k%p;
for(int i=1;i<=t;i++){
if(mp[x])return 1ll*i*t-mp[x];
else x=1ll*x*a%p;
}
return -1;
}
inline int exbsgs(int a,int b,int p){
a%=p; b%=p; int g=0,k=1,ans;
while(gcd(a,p)!=1){ int d=gcd(a,p);
if(b%d)return -1;
g++; b/=d; k=1ll*k*a/d%p; p/=d;
if(k==b)return g;
}
ans=bsgs(a,b,p,k);
return (~ans)?ans+g:-1;
}
inline int read(){
int f=0,s=0; char c=getchar();
while(c>'9'||c<'0')f=(c=='-'),c=getchar();
while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^'0'),c=getchar();
return f?-s:s;
}
signed main(){
while(1){ a=read(); p=read(); b=read(); if(!(a+p+b))break;
int ans=exbsgs(a,b,p);
if(ans!=-1)printf("%d
",ans);
else puts("No Solution");
}
return 0;
}