组合计数

卡特兰数

/*
h(n)=C(2n,n)/(n+1)
h(n)=sum(h(i-1)h(n-i)),n>=2
h(n)=h(n-1)(4n-2)/(n+1)
h(n)=C(2n,n)-C(2n,n-1)
*/

斯特林数

第二类斯特林数

性质：

​ $$\begin{Bmatrix}n\\\\m\end{Bmatrix}=\frac{1}{m!}\sum_{k=0}^m(-1)^{m-k}\binom{k}{m}k^n=\sum_{i=0}^m\frac{(-1)^{m-i}i^n}{(m-i)!i!}$$

反演得：
$m^n=\sum_{i=0}^m\begin{Bmatrix}n\\\\i\end{Bmatrix}\binom{i}{m}i!$,
写成下降幂形式为
$m^n=\sum_{i=0}^m\begin{Bmatrix}n\\\\i\end{Bmatrix}m^\underline{i}$
写成上升幂形式为
$m^n=\sum_{i=0}^n\begin{Bmatrix}n\\\\i\end{Bmatrix}(-1)^{n-k}x^{\overline{k}}$

第一类斯特林数

$F(x)^n=\prod_{i=0}^{n-1}(x+i),F(x)^{2n}=F(x)^nF(x+n)^n$

考虑CDQ分治，$F(x+n)^n=\sum_{i=0}^n(i!)^{-1}(\sum_{j=i}^n(\frac{n^{j-i}}{(j-i)!})(j!a_j))x^i$,得到右半部分后再相乘即可。
性质:
考虑置换和第一类斯特林数关系：
$$n!=\sum_{i=0}^n\begin{bmatrix}n\\\\ i\end{bmatrix}$$
下降幂转普通幂
$x^{\underline{n}}=\sum_{i=0}^n\begin{bmatrix}n\\\\i\end{bmatrix}(-1)^{n-i}x^i$
上升幂转普通幂
$x^{\over{n}}=\sum_{i=0}^n\begin{bmatrix}n\\\\i\end{bmatrix}x^i$

第二类：

void solve() {
    int n;read(n);
    NTT::ntt_init((1<<(POLY::norm(n)+2)));
    vector<int> f(n+1),g(n+1),fac(n+1),ifac(n+1);
    fac[0]=ifac[0]=1;
    rep(i,1,n) fac[i]=mul(i,fac[i-1]),ifac[i]=fp(fac[i],mod-2);
    rep(i,0,n) f[i]=mul(ifac[i],(i&1)?mod-1:1);
    rep(i,0,n) g[i]=mul(ifac[i],fp(i,n));
    f=f*g;
    rep(i,0,n) printf("%d ",f[i]);
}

第一类

void Stirling(int n,int a[]) {
    if(!n) {a[0]=1;return;}
    if(n==1) {a[1]=1;return;}
    int mid=(n/2);
    Stirling(mid,a);
    vector<int> f(mid+1),g(mid+1);
    rep(i,0,mid) {
        f[i]=mul(fp(mid,i),ifac[i]);
        g[i]=mul(fac[i],a[i]);
    }
    reverse(g.begin(),g.end());
    f=f*g;
    f.resize(mid+1);
    g.resize(mid+1);
    reverse(f.begin(),f.end());
    rep(i,0,mid) f[i]=mul(f[i],ifac[i]);
    rep(i,0,mid) g[i]=a[i];
    f=f*g;
    rep(i,0,(mid<<1)) a[i]=f[i];
    if(n&1) downrep(i,1,n) a[i]=add(a[i-1],mul(n-1,a[i]));
}

容斥

设U中元素有n种不同的属性，而第i种属性为$P_i$,拥有$P_i$的元素构成集合$S_i$,则有：

$$ \begin{aligned} \left|\bigcup_{i=1}^nS_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^mS_{a_i}\right| \end{aligned} $$

对于集合的交可以使用全集减去补集的并集求的：
$$ \begin{aligned} \left|\bigcap_{i=1}^nS_i\right|=\left|U\right|-\left|\bigcup_{i=1}^n\overline{S_i}\right| \end{aligned} $$
可以解决的问题：
(1)不定方程的解:$\sum_{i=1}^nx_i=m,x_i<b_i$，直接考虑容斥可得：
$$ \begin{aligned} Ans=\binom{n+m-1}{n-1}-\sum_{k=1}^n(-1)^k\sum_{k}\binom{n+t-1}{n-1},t=m-\sum_k{b_i} \end{aligned} $$
(2) 最大公约数
$\sum_{x}\sum_{y}(x,y)$
不妨设$f(k)=|\{(x,y)|(x,y)=k\}|$,考虑容斥，$f(k)=\lfloor(N/k)\rfloor^2-\sum_{i=2}^{ik<N}f(ik)$,显然当$k>N/2$时，$f(k)=\lfloor N/k\rfloor^2$

(3)DAG 计数
求n个点组成DAG的个数
令$f(x)$表示x个点组成的dag的个数
则有 $f(i)=\sum_{j=1}^i(-1)^{j-1}\binom{i}{j}2^{j(i-j)}f(i-j)$

(4) 一般容斥
定义$f(S),g(S)$表示集合函数，则若
$$ f(S)=\sum_{T\subset S}g(T) $$

，则有

$$ g(S)=\sum_{T\subset S}(-1)^{|T|-1}f(T) $$

证明带入即可

应用：$\text{Min-Max},$反演
令$U=\{x_1,x_2,x_3..x_n\},\min(S)=\min_{x_i\in S}{x_i}\,\max(S)=\max_{x_i\in S}{x_i}$
定理:
$$ \begin{aligned} \min(S)=\sum_{T\subseteq S}{\max(T)}\\\\ \max(S)=\sum_{T\subseteq S}{\min(T)} \end{aligned} $$
推广到期望问题：
$$ \begin{aligned} E(\min(S))=\sum_{T\subseteq S}{E(\max(T))}\\\\ E(\max(S))=\sum_{T\subseteq S}{E(\min(T))} \end{aligned} $$

//HAOI 按位或 
void FWT(double *A,const int up) {
    for(int len=2,mid=1;len<=up;len<<=1,mid<<=1)
        for(int pos=0;pos<up;pos+=len)
            for(int k=0;k<mid;k++)
                A[pos+k+mid]+=A[pos+k];
}

void solve() {
    int n,m;scanf("%d",&n);
    m=(1<<n);
    vector<double> p(m);
    rep(i,0,m) scanf("%lf",&p[i]);
    //计算P(S)
    FWT(p.data(),m);

    double ans=0;
    rep(x,1,m-1) {
        int cnt=0;
        rep(i,0,n-1) cnt+=((x>>i)&1);
        ans+=cnt&1?1/(1-p[x^(m-1)]):-1/(1-p[x^(m-1)]);
    }
    if(ans>1e307) puts("INF");
    else printf("%.10lf\n",ans);
}