数数总结

基础

Twelvefold way

我刚刚发现根本不会做这题/kk

$n$ 个有/无标号的球放到 $m$ 个有无标号的盒子中，无限制/每个盒子至少一个/每个盒子至多一个

$1.$ 有标号球放有标号盒子，无限制

​ $m^n$

$2.$ 有标号球放有标号盒子，每个盒子至少一个

​ 考虑容斥，设 $S(a_1,a_2,…,a_k)$ 表示 $a_1,a_2,…,a_k$ 全空的情况

​ 答案即为:

​ $m^n-S(1)-S(2)-...+(-1)^m S(1,2,...,m)=\sum_{i=0}^m (-1)^i (m-i)^n \binom{m}{i}$

$3.$ 有标号球放有标号盒子，每个盒子至多一个

​ $A_m^n$

$4.$ 无标号球放有标号盒子，无限制

​ 设 $y_i=x_i+1$ ，即求方程 $y_1+y_2+…+y_m=n+m$ 的正整数解的个数

​ $\binom{n+m-1}{m-1}$

$5.$ 无标号球放有标号盒子，每个盒子至少一个

​ 经典插板法，不妨看成方程 $x_1+x_2+…+x_m=n$ 的正整数解个数，也就是 $n$ 个球插入 $m-1$ 个板子

​ $\binom{n-1}{m-1}$

$6.$ 无标号球放有标号盒子，每个盒子至多一个

​ $A_m^n$

$7.$ 有标号球放无标号盒子，无限制

​ 通过 $8$ 的答案，枚举多少个盒子放了球即可

​ $$\sum_{i=1}^m {n\brace i}$$

$8.$ 有标号球放无标号盒子，每个盒子至少一个

​ 显然符合第二类斯特林数 $\displaystyle{{n\brace m}}$ ，即，将 $n$ 个物品的集合划分成 $m$ 个非空子集的方案数

$9.$ 有标号球放无标号盒子，每个盒子至多一个

​ $[n\leq m]$

$10.$ 无标号球放无标号盒子，无限制

​ 通过 $11$ 的答案，枚举盒子数

​ $\sum_{i=1}^m p_{n,i}$

$11.$ 无标号球放无标号盒子，每个盒子至少一个

​ 满足划分数 $p_{n,m}$ ，即，将 $n$ 划分为 $m$ 个正整数方案数

​ 满足递推式 $p_{n,m}=p_{n-m,m}+p_{n-1,m-1}$

$12.$ 无标号球放无标号盒子，每个盒子至多一个

​ $[n\leq m]$

错排

• 考虑 $D_n$ 的递推

  $n$ 能放到 $[1,n)$ 的任意一位置 $k$ 上

  若 $k$ 在 $n$ 上，则还有 $n-2$ 个数没有确定位置，答案为 $D_{n-2}$

  若 $k$ 不在 $n$ 上，那么 $n-1$ 个数都没有位置，$D_{n-1}$

  $k$ 有 $n-1$ 种取值，那么有 $\displaystyle{D_n=(n-1)(D_{i-1}+D_{i-2})}$

• 考虑封闭形式

  容斥有：

  $$D_n=n!-\binom{n}{1}(n-1) + \binom{n}{2}(n-2)!+...+(-1)^n \binom{n}{n}(n-n)!$$

  由于：

  $$\binom{n}{i}(n-i)! =\frac{n!}{i!(n-i)!} \times (n-1)!=\frac{n!}{i!}$$

  所以有：

  $$D_i=n!\times \sum_{i=0}^n (-1)^i \frac{1}{i!}$$

组合式子

上指标

对于任意实数 $r$ 和正整数 $k$ ，有

$$\binom{r}{k}=\frac{r^{\underline{k}}}{k!}$$

如此，在上指标是负数是，即有：

$$\binom{r}{k}=(-1)^k\binom{k-r+1}{k}$$

组合恒等式

• 一行的和

  $$\sum_k \binom{n}{k}=(1+1)^n=2^n$$

• 分奇偶

  $$\sum_k (-1)^k \binom{n}{k}=(1-1)^n=[n=0]$$

• 提取/吸收恒等式

  $$\binom{n}{m}=\frac{n}{m}\binom{n-1}{m-1}\Rightarrow m\binom{n}{m}=n\binom{n-1}{m-1}$$

• 相伴恒等式

  $$(r-k)\binom{r}{k}=r\times \frac{(r-1)^{\underline{r-k-1}}}{(r-k-1)!}=r\binom{r-1}{k}$$ $$k\binom{r}{k}=\frac{r^{\underline{k}}}{(k-1)!}=\frac{(r-k+1)\times r^{\underline{k-1}}}{(k-1)!}=(r-k+1)\binom{r}{k-1}$$

• 上指标反转

  $$\binom{r}{k}=(-1)^k \binom{r-k-1}{k}$$

  • 证明：

    $$\binom{r}{k}=\frac{r^{\underline{k}}}{k}=\frac{r(r-1)\times ...\times (r-k+1)}{k!}=(-1)^k\frac{(r-k-1)^{\underline{k}}}{k!}=(-1)^k\binom{r-k-1}{k}$$

• 三项式系数恒等式

  $$\binom{r}{m}\binom{m}{k}=\frac{r!}{(r-m)!(m-k)!k!}=\binom{r-k}{m-k}\binom{r}{k}$$

一些求和

• 上指标求和

  $$\sum_{i=m}^n\binom{i}{m}=\binom{n+1}{m+1}$$

  文字叙述为：在 $n$ 个物品后分别插入一个结束符，强选结束符并在结束符前选 $m$ 个物品数

• 平行求和

  $$\sum_{i=0}^n\binom{m+i}{i}=\binom{m+n+1}{n}$$

卷积与点积

• 下指标卷积

  $$\sum_k\binom{n}{k}\binom{m}{r-k}=\binom{n+m}{r}$$

• 下指标点积

  $$\sum_i\binom{n}{i}\binom{m}{i}=\sum_i\binom{n}{i}\binom{m}{m-i}=\binom{n+m}{m}$$

  特殊的，有

  $$\sum_i\left(\binom{n}{i}^2\right)=\binom{2n}{n}$$

• 上指标卷积

  $$\begin{aligned} \sum_i\binom{i}{a}\binom{n-i}{b}&=\sum_i\left(\sum_{j<i}\binom{i}{a-1}\right)\binom{n-i}{b} \\ &=\sum_j\binom{j}{a-1}\sum_{i>j}\binom{n-i}{b} \\ &=\sum_j\binom{j}{a-1}\binom{n-j}{b+1} \\ &=...=\sum_{j\leq n}\binom{n-j}{a+b} \\ &=\binom{n+1}{a+b+1} \\ \end{aligned}$$

  考虑组合意义：原式相当于把 $n$ 个物品分开从前一段选 $a$ ，后一段选 $b$ 个

  等同于将一个分隔符同 $a+b$ 个物品从 $n+1$ 选出来，其中第 $a+1$ 个物品是分隔符，方案与原式对应

多重集的排列数

多重集的全排列数为元素总数的阶乘除以重复度之和的阶乘，形式化的：

对于多重集 $S=\{a_1\times n_1,a_2\times n_2,…,a_k\times n_k\}$ ，全排列数为：

$$\frac{\left(\sum n_i \right)!}{\prod (n_i!)}$$

证明：

设 $n=\sum n_i$

对于元素 $a_1$ ，放置的方案数为 $\displaystyle{\binom{n}{n_1}}$

对于元素 $a_2$ ，放置的方案数为 $\displaystyle{\binom{n-n_1}{n_2}}$

对于元素 $a_k$ ，放置的方案数为 $\displaystyle{\binom{n-n_1-n_2-…-n_{k-1}}{n_k}}$

那么总方案数即为 $\displaystyle{\frac{n!}{n_1!\times n_2!\times …\times n_k!}}$

P2518 [HAOI2010]计数

一组非 $0$ 数字，可以插入人一个 $0$ ，给出一个数，求这个数前有多少被上述方法产生的数

设 $t$ 表示当前已处理的几位的排列总数，初始有 $t=1$

考虑手玩数据得到：从后往前枚举每一位，若当前位为 $a$ ，截至目前 $a$ 出现 $b$ 次，比 $a$ 小的数有 $c$ 个，则当前位对 $ans$ 的贡献为 $\frac{t\times c}{b}$

emmm对于正确性的话并不是太会证，感性理解一下吧qwq

const int N=60;
char ch[N];
int cnt[20],tr[20],n;
ld s=0,t=1;//s当前答案，t当前已处理的后t位的排列总数

inline int lowbit(int x){ return x&(-x);}
inline void add(int x){ for(;x<=10;x+=lowbit(x)) ++tr[x];}
inline int sum(int x,int res=0){ for(;x;x-=lowbit(x)) res+=tr[x]; return res;}

signed main(){
    scanf("%s",ch+1); n=strlen(ch+1);
    for(rei i=n;i;--i){
        rei a=ch[i]-'0'+1,c=sum(a-1);//c:比a小的数的个数
        if(!c) t=t*(n-i+1)/(++cnt[a]);
        else{
            t/=(++cnt[a]);
            s+=t*c,t*=(n-i+1);
        }
        add(a);
        // printf("%d %lld\n",a,(ll) s);
    }
    printf("%lld\n",(ll) s);
    getchar(),getchar();
    return 0;
}

多项式系数

定义

$$(x+y+z)^n=\sum_{i+j+k=n} \binom{n}{i,j,k}\ \ x^i y^jz^k$$ $$其中 \binom{n}{k_1,k_2,...,k_m}=\frac{n!}{\prod_{i=1}^m k_i!} 即为多重集的组合数，即，将n分为多个集合的方案数$$ $$\sum k_i=n$$

例题

n个节点的有根树。给每个节点分配一个 $1\sim n$ 的数字，使得每个节点分配的数字不同，并且每个节点分配的数字都是它子树内最小的。求方案数。

对于子树 $u$ 被分配到的字符集 $\{p_1,p_2,…,p_k | i<j\Leftrightarrow p_i<p_j\}$ , 节点 $u$ 值即为 $p_1$

将剩下的分给其子树，方案数即为：

$$\binom{size_u-1}{size_{v_1},size_{v_2},...,size_{v_k}}$$

考虑转移，由树形 $\text{dp}$ 得：

$$dp_u=\binom{size_u-1}{size_{v_1},size_{v_2},...,size_{v_k}} \times \prod_{i=1}^k dp_{v_i}$$

不妨设 $\displaystyle{P_i=\frac{dp_i}{size_i!}}$

那么有：

$$dp_u=(size_u-1)!\times \prod_{i=1}^k P_{v_i}=\frac{size_u!}{size_u} \times P_{v_1}$$

发现递推 $\text{dp}$ 后并不太能直接看出答案：

$$dp_u=\frac{size_u!}{size_u}\times \prod_{i=1}^k \frac{\frac{size_{v_i}!}{size_{v_1}} \times \prod_{j=1}^{kk} \frac{dp_{vv_i}}{size_{vv_i}!}}{size_{v_i!}}$$

考虑尝试递推 $\text{P}$ ，那么有：

$$P_u=\frac{1}{size_u}\times \prod_{i=1}^k P_{v_i}=\frac{1}{size_u}\prod_{i=1}^k \frac{1}{size_v}\prod_{j=1}^{kk} P_{vv_j}=\prod_{v \in subtree\ of\ u} \frac{1}{size_v}$$ $$P_1=\prod^n \frac{1}{size_i}$$

那么答案即为：

$$dp_1=P_1\times size_i! =n!\times \prod^n \frac{1}{size_i}$$

树计数

有标号无/有根树计数

结论为：有标号无根树计数为 $n^{n-2}$ ，有标号有根树计数为 $n^{n-1}$

证明：

由 $\text{Cayley}$ 定理可得

设当前有 $k$ 个子树，可以任选一颗子树上的一个点连边到另一颗子树，那么方案数为 $n\times (k-1)$

假设刚开始的 $n$ 个点是 $n$ 个子树，每次操作会使子树减少一个，方案数即为 $\displaystyle{\prod_{i=1}^{n-1}n\times i=n^{n-1}(n-1)!}$

考虑到连边顺序不需要考虑，那么方案数即为 $n^{n-1}$

对于有根树，需要花 $n$ 的代价指定根，那么无根树的情况即是 $n^{n-2}$

const int N=1e3+100;
int n,mod,op;
int inv[N],f[N],g[N];

inline void fix(int &x){ x>=mod ? x-=mod : 0; x<0 ? x+=mod : 0;}
inline int qpow(ll x,ll y,ll res=1){ while(y){ if(y&1) res=res*x%mod; y>>=1; x=x*x%mod;} return res;}
inline int solve1(){ return qpow(n,max(n-2,0));}
inline int solve2(){ return qpow(n,n-1);}

inline int solve3(){
    inv[1]=1;
    for(rei i=2;i<=n;++i) inv[i]=(ll) (mod-mod/i)*inv[mod%i]%mod;
    memset(f,0,sizeof f),memset(g,0,sizeof g);
    f[1]=1;
    for(rei i=1;i<=n;++i){
        for(rei j=1;j<i;j++) fix(f[i]+=(ll) f[j]*g[i-j]%mod);
        if(i>1) f[i]=(ll) f[i]*inv[i-1]%mod;
        for(rei j=i,val=(ll) f[i]*i%mod;j<=n;j+=i) fix(g[j]+=val);
    }
    return f[n];
}

inline int solve4(){
    rei ans=solve3();
    for(rei i=n/2+1;i<n;++i) fix(ans+=mod-(ll) f[i]*f[n-i]%mod);
    if(n%2==0) fix(ans+=mod-(ll) f[n/2]*(f[n/2]-1)/2%mod);
    return ans;
}

int main(){
    while(~scanf("%d%d%d",&op,&n,&mod)){
        if(op==1) printf("%d\n",solve1());
        if(op==2) printf("%d\n",solve2());
        if(op==3) printf("%d\n",solve3());
        if(op==4) printf("%d\n",solve4());
    }
    getchar(),getchar();
    return 0;
}

无标号有/无根树计数

看不懂先咕了/kk

有根树

引入 $\text{Euler}$ 变换：

$$\xi(F(x))=\sum_{i=1}\left(\sum_{j=0}x^{ij} \right)^{\left[x^i\right]F(x)}$$

由 $\text{ln+exp}$ 可得：

$$\large{\xi(F(x))=e^{\sum_{i=1}\frac{F(x^i)}{i}}}$$

设 $f_n$ 表示 $n$ 个点的有根树的方案数，$F(x)$ 为 $f$ 的 $\text{OGF}$

那么有:

$$F(x)=x\times \xi(F(x))=x\times \prod_{i=1}\left(\frac{1}{1-x^i} \right)^{f_i}$$

同时求 $\ln$ 得：

$$\ln F(x)=\ln x+\sum_{i=1}-f_i\ln\left(1-x^i\right)$$

两边同时求导得：

$$\begin{aligned} \frac{F'(x)}{F(x)}&=\frac{1}{x}+\sum_{i=1}f_i\frac{i\times x^{i-1}}{1-x^i} \\ xF'(x)&=F(x)+F(x)\times \sum_{i=1}f_i\times i\times \frac{x^i}{1-x^i} \\ \end{aligned}$$

观察式子第 $n$ 项的系数，右边是卷积形式，有：

$$\frac{x^i}{1-x^i}=\sum_{j=1}x^{i\times j}=\sum_{j=1}[i\mid j]x^j$$

代入得：

$$n\times f_n=f_n+\sum_{j=1}^nf_j\times \sum_{i=1}^nf_i\times i\ [i\mid n-j]$$

设 $g_n=\sum_{i\mid n}f_i\times i$ ，则

$$\begin{aligned} f_n&=\sum_{i=1}f_ig_{n-i} \\ F(x)&=\frac{1}{n-1}F(x)G(x) \\ \end{aligned}$$

无根树

一颗无根树可能被统计为多颗有根树，那么只考虑根为重心的情况，即，$f_n-\text{根不是重心的情况数}$

显然根节点如果有一颗子树大小超过 $\left\lfloor\frac{n}{2} \right\rfloor+1$ 则其一定不是重心，那么有：

$$ans=f_n-\sum_{i=\left\lfloor\frac{n}{2} \right\rfloor+1}^{n-1} f_i\times f_{n-i}$$

当 $n$ 为偶数，可能有两个重心，去重减去 $\binom{f_{\frac{n}{2}}}{2}$

#define int long long
#define bin(x) (1<<(x))
const int N=6e5+100;
const int mod=998244353;
int n,F[N],G[N],inv[N],w[N];
int limit,r[N];
int A[N],B[N];

inline int add(int x){ return x>=mod ? x-mod : x;}
inline int dec(int x){ return x<0 ? x+mod : x;}
inline void fix(int &x){ x>=mod ? x-=mod : 0; x<0 ? x+=mod : 0;}
inline int qpow(ll x,ll y,ll res=1){ while(y){ if(y&1) res=res*x%mod; y>>=1; x=x*x%mod;} return res;}
inline void InitR(int lg){ for(rei i=1;i<bin(lg);++i) r[i]=(r[i>>1]>>1) | ((i&1)<<(lg-1));}
inline void init(int lg){
    rei lim=bin(lg);
    inv[1]=1;
    for(rei i=2;i<=lim;++i) inv[i]=(ll) (mod-mod/i)*inv[mod%i]%mod;
    for(rei i=1,wn;i<lim;i<<=1){
        w[i]=1;
        wn=qpow(3,(mod-1)/(i<<1));
        for(rei j=1;j<i;++j) w[i+j]=(ll) w[i+j-1]*wn%mod;
    }
}

inline void ntt(int *f,int lg,int type=0){
    limit=bin(lg);
    if(type) reverse(f+1,f+limit);
    for(rei i=1;i<limit;++i) if(i<r[i]) swap(f[i],f[ r[i] ]);
    for(rei mid=1,t;mid<limit;mid<<=1) for(rei j=0;j<limit;j+=(mid<<1)) for(rei i=0;i<mid;++i){
        t=(ll) f[j+i+mid]*w[mid+i]%mod;
        f[j+i+mid]=dec(f[j+i]-t);
        f[j+i]=add(f[j+i]+t);
    }
    if(type) for(rei i=0;i<bin(lg);++i) f[i]=(ll) f[i]*inv[limit]%mod;
}

void solve(int l,int r){
    if(r-l<64){
        for(rei i=l;i<r;++i){
            for(rei j=l;j<i;++j){
                fix(F[i]+=(ll) F[j]*G[i-j]%mod);
                if(l>1) fix(F[i]+=(ll) G[j]*F[i-j]%mod);
            }
            if(i>1) F[i]=(ll) F[i]*inv[i-1]%mod;
            for(rei j=i,val=(ll) F[i]*i%mod;j<=n;j+=i) fix(G[j]+=val);
        }
        return ;
    }
    rei mid=l+r>>1;
    solve(l,mid);
    rei lg=ceil(log2(r-l+1));
    InitR(lg);
    auto cont=[&](int *f,int ln1,int *g,int ln2){
        for(rei i=0;i<bin(lg);++i)
            A[i]=(i<ln1 ? f[i] : 0),B[i]=(i<ln2 ? g[i] : 0);
        ntt(A,lg),ntt(B,lg);
        for(rei i=0;i<bin(lg);++i) A[i]=(ll) A[i]*B[i]%mod;
        ntt(A,lg,1);
        for(rei i=mid;i<r;++i) fix(F[i]+=A[i-l]);
    };
    if(l==1) cont(G+l,mid-l,F,mid);//F和G都只取左半部分
    else cont(G+l,mid-l,F,r-l),cont(F+l,mid-l,G,r-l);
    //补上之前少贡献的，以及让F左半部分与G的完整部分贡献右半部分
    solve(mid,r);
}

signed main(){
    scanf("%d",&n);
    init( ceil(log2((n+1)<<1)) );
    F[1]=1;
    solve(1,n+1);
    rei ans=F[n];
    for(rei i=n/2+1;i<n;++i) fix(ans+=mod-(ll) F[i]*F[n-i]%mod);
    if(n%2==0) fix(ans+=mod-(ll) F[n/2]*(F[n/2]-1)/2%mod);
    printf("%d",ans);
    getchar(),getchar();
    return 0;
}

例题

P3214 [HNOI2011]卡农

题意见原题面 实在太繁琐了吧

要求在 $n$ 个音节中挑选若干个，且音节集合不同，那么不妨将音阶集合用二进制表示，即 $1\sim 2^n-1$ 种片段

又要求选择无序的 $m$ 个片段，可以考虑按照有序计算并除以 $m!$

题干中的规定可以有如下转化：

• 任意两片段音节集合不同 $\Rightarrow$ $m$ 个数互不相同
• 一段音乐中每个音阶出现次数为偶数 $\Rightarrow$ $m$ 个数异或和为 $0$

设 $f_i$ 表示选 $i$ 个数且满足上述性质的方案数

直接计算并不方便，考虑做一下容斥：

先局部的考虑：若有 $f_{i-1}$ 的异或和为 $x$

是的这准确来说不是 $f$

为了便于理解，设 $a_i$ ，其中 $a_{1\sim i-1}$ 并不满足上述性质，但 $a_i$ 满足性质 $2$

那么 $a_i$ 的方案数就是 $a_{i-1}$ 的方案数，也就是，选出 $a_i$ 的方案数为 $A_{2^n-1}^{i-1}$ ，即，从所有非空子集里选出前 $i-1$ 个的排列数

再考虑减去其中不合法的方案：

• 第 $i$ 个子集为空，即前 $i-1$ 个子集异或和为 $0$

  方案数 $f_{i-1}$

• 第 $i$ 个子集和之前的第 $j$ 个子集相同

  方案数 $f_{i-2}\times (2^n-1-(i-2))\times (i-1)$

那么总的转移就是：

$$f_i=A_{2^n-1}^{i-1}-f_{i-1}-f_{i-2}\times (2^n-1-(i-2))\times (i-1)$$

答案就是:

$$\frac{f_m}{m!}$$

#define int long long
const int N=1e6+100;
const int mod=1e8+7;
int n,m,a[N],f[N],fac;//f_i是满足性质的有序集合的方案数

inline int qpow(ll x,int y,ll res=1){ while(y){ if(y&1) res=res*x%mod; y>>=1; x=x*x%mod;} return res;}
inline int get_fac(int x,ll res=1){ for(rei i=2;i<=x;++i) res=res*i%mod; return res;}

signed main(){
    scanf("%lld%lld",&n,&m);
    fac=qpow(2,n)-1; a[0]=1;
    for(rei i=1;i<=m;++i) a[i]=(ll) a[i-1]*(fac-i+1+mod)%mod;
    f[0]=1;
    for(rei i=2;i<=m;++i) f[i]=(ll) (a[i-1]-f[i-1]+mod-(fac-i+2)*(i-1)%mod*f[i-2]%mod+mod)%mod;//容斥一下
    printf("%d\n",(ll) f[m]*qpow(get_fac(m),mod-2)%mod);//答案需要无序，去重
    getchar(),getchar();
}

P5376 [THUPC2019]过河卒二

$n\times m$ 的棋盘上有 $k$ 个障碍点，从 $(1,1)$ 移动到棋盘的最上方或最右方 ，移动方式为 $(i,j)\Rightarrow(i+1,j),(i,j+1),(i+1,j+1)$ ，走出棋盘时仍有方案的选择，求方案数

先考虑没有障碍：题目能转化为 $(1,1)\Rightarrow (n+1,m+1)$ ，理解为到边缘就只有一种走法

该题比平常的过河卒问题多了斜着走，那么枚举斜着走的次数就能转化为经典的过河卒，即：

$$\sum_{i=0}^{\min(n,m)} \binom{n+m-i}{i}\binom{n+m-2\times i}{n-i}$$

再考虑有障碍情况，$k\leq 20$ 启示把障碍用二进制表示为 $S$

那么能做容斥：

$$\sum_S (-1)^{|S|} g_S$$

其中 $g_S$ 表示至少有 $S$ 的障碍时到达终点方案数

提前预处理两两障碍相到达的方案数，以及起点到每个障碍，每个障碍到终点的方案数就能在 $O(\log S)$ 的时间里求出 $g_S$

注意 $S$ 中障碍的顺序要排序

题中的 $mod\leq 59393$ 较小，做预处理并用 $\text{Lucas}定理$ 求组合数

const int N=25,M=1048576+100;
const int mod=59393;
PII p[N];
int n,m,k,ans,fac[mod+10],inv[mod+10],fac_inv[mod+10];
int Size[M],cnt[N][N],s_b[N],b_e[N];//s_b:start-block; b_e:block-end

inline void fix(int &x){ x>=mod ? x-=mod : 0; x<0 ? x+=mod : 0;}
inline int get_C(int n,int m){ return (n<0 || m<0 || n<m) ? 0 : (ll) fac[n]*fac_inv[m]%mod*fac_inv[n-m]%mod;}
int lucas(int n,int m){ return n<mod ? get_C(n,m) : (ll) lucas(n/mod,m/mod)*lucas(n%mod,m%mod)%mod;}
inline int get_ways(int n,int m,ll ans=0){ for(rei i=0;i<=min(n,m);++i) ans=(ans+(ll) lucas(n+m-i,i)*lucas(n+m-2*i,n-i))%mod; return ans;}

inline void init(){
    fac[0]=fac[1]=inv[1]=fac_inv[0]=fac_inv[1]=1;
    for(rei i=2;i<=mod-1;++i){
        fac[i]=(ll) fac[i-1]*i%mod;
        inv[i]=mod-(ll) (mod/i)*inv[mod%i]%mod;
        fac_inv[i]=(ll) fac_inv[i-1]*inv[i]%mod;
    }
}

inline int solve(int S){//至少经过S中的障碍的方案数
    rei pre=-1,ans=1;
    for(rei i=0;i<=k-1;++i) if((S>>i)&1){
        if(pre==-1) ans=(ll) ans*s_b[i]%mod;
        else{
            if(p[pre].second>p[i].second) return 0;
            ans=(ll) ans*cnt[pre][i]%mod;
        }
        pre=i;
    }
    return (~pre) ? (ll) ans*b_e[pre]%mod : get_ways(n,m);
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    init();
    for(rei i=0;i<=k-1;++i) scanf("%d%d",&p[i].first,&p[i].second);
    sort(p,p+k);
    for(rei i=0;i<=k-1;++i) for(rei j=i+1;j<=k-1;++j) cnt[i][j]=get_ways(p[j].first-p[i].first,p[j].second-p[i].second);//预处理两两障碍点的方案数
    for(rei i=0;i<=k-1;++i) s_b[i]=get_ways(p[i].first-1,p[i].second-1),b_e[i]=get_ways(n-p[i].first+1,m-p[i].second+1);
    for(rei i=1;i<=(1<<k)-1;++i) Size[i]=Size[i>>1]+(i&1);
    for(rei i=0;i<=(1<<k)-1;++i)//容斥原理：\sum_S (-1)^{|S|} g_S
        (Size[i]&1) ? fix(ans-=solve(i)) : fix(ans+=solve(i));
    printf("%d\n",ans);
    getchar(),getchar();
    return 0;
}

P5339 [TJOI2019]唱、跳、rap和篮球

见原题

设 $f_i$ 表示序列中至少有 $i$ 组人讨论的方案数，由容斥得：

$$ans=\sum_{i=0}^{\min(\frac{n}{4},a,b,c,d)} (-1)^i f_i$$

将讨论 $\text{cxk}$ 的四个人看成一个一个元素，那么共有 $n-4\times i+i=n-3\times i$ 个元素

考虑多重集排列的方案数：

$$\left(\sum_{i=1}^m a_i\right)!\times \prod_{i=1}^m\frac{1}{a_i!}$$

const int N=2e3+100;
const int mod=998244353;
int n,a,b,c,d,lim;
int fac[N],facinv[N],f[N],res,ans;

inline void fix(int &x){ x>=mod ? x-=mod : 0;}
inline int qpow(ll x,int y,ll res=1){ while(y){ if(y&1) res=res*x%mod; y>>=1; x=x*x%mod;} return res;}
inline void init(){
    fac[0]=1; for(rei i=1;i<=n;++i) fac[i]=(ll) fac[i-1]*i%mod;
    facinv[n]=qpow(fac[n],mod-2); for(rei i=n-1;i>=0;--i) facinv[i]=(ll) facinv[i+1]*(i+1)%mod;
}

int main(){
    scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
    init();
    lim=(n>>2,min(min(a,b),min(c,d)));
    for(rei x=0;x<=lim;++x){
        rei flag=x&1 ? mod-1 : 1; memset(f,0,sizeof f);
        for(rei i=0;i<=a-x;++i) for(rei j=0;j<=min(n-4*x-i,b-x);++j) fix(f[i+j]+=(ll) facinv[i]*facinv[j]%mod);
        res=0;
        for(rei i=0;i<=c-x;++i) for(rei j=0;j<=min(n-4*x-i,d-x);++j) fix(res+=(ll) facinv[i]*facinv[j]%mod*f[n-4*x-i-j]%mod);
        res=(ll) res*fac[n-3*x]%mod*facinv[x]%mod;
        fix(ans+=(ll) flag*res%mod);
    }
    printf("%d\n",ans);
    getchar(),getchar();
    return 0;
}

P3244 [HNOI2015]落忆枫音

$n$ 点 $m$ 边的 $\text{DAG}$ 保证点 $1$ 无入边，在 $\text{DAG}$ 中加入一条不在原图中的边 $x,y$ ，求改有向图以 $1$ 为根的树形图个数

先考虑不加入边时的方案数，显然为：

$$\prod_{i=2}^n in_i$$

加入新边后可能会形成环，需要减去环的情况：设环上的点为 $a_1,a_2,…,a_k$

对于环上的点不能任意选择，那么有环时的情况数为：

$$\frac{\prod_{i=2}^n in_i}{\prod_{i=1}^k in_{a_i}}$$

设新加入的边 $(add_x,add_y)$，$g_x$ 表示路径 $add_y\rightarrow x$ 中上式的值

那么有

$$g_x=\frac{\sum_{u,v\in E} g_v}{in_u}$$

const int mod=1e9+7;
const int N=1e5+100;
int head[N],Next[N<<1],ver[N<<1],in[N],tot;
int g[N],vis[N];
int n,m,ans=1,dsum=1,add_x,add_y;

inline void fix(int &x){ x>=mod ? x-=mod : 0;}
inline void add(int u,int v){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot; ++in[u];}
inline int qpow(ll x,int y,ll res=1){ while(y){ if(y&1) res=res*x%mod; y>>=1; x=x*x%mod;} return res;}
void dfs(int x){
    if(vis[x]) return ;
    vis[x]=1;
    if(x==add_y) return g[x]=(ll) dsum*qpow(in[x],mod-2)%mod,void();
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i];
        dfs(y);
        fix(g[x]+=g[y]);
    }
    g[x]=(ll) g[x]*qpow(in[x],mod-2)%mod;
}

int main(){
    scanf("%d%d%d%d",&n,&m,&add_x,&add_y);
    for(rei i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),add(v,u);
    ++in[1];
    for(rei i=1;i<=n;++i){
        if(i==add_y) ans=(ll) ans*(in[i]+1)%mod;
        else ans=(ll) ans*in[i]%mod;
        dsum=(ll) dsum*in[i]%mod;
    }
    dfs(add_x);
    fix(ans+=mod-g[add_x]);
    printf("%d\n",ans);
    getchar(),getchar();
    return 0;
}

P6773 [NOI2020] 命运

给定一棵树 $T=(V,E)$ ，点对集合 $V\times V$ ，满足对于所有 $(u,v)\in Q$ ，都有 $u\not ={v}$ 且 $u$ 是 $v$ 在树上的祖先。求有多少个不同的函数 $f:E\rightarrow\{0,1\}$ 。即，将每条边值 $f(e)$ 置为 $0/1$ ，满足对于任何 $(u,v)\in Q$ 都存在 $u\rightarrow v$ 使 $f(e)=1$

题意即为：要求树上一条链上必须至少有一个 $1$ ，求钦定边权的方案数

那么有一个显然的结论：若有 $depth_{v_2}<depth_{v_1}$ 且 $v_1,v_2$ 都是 $u$ 的祖先，若满足 $(u,v_1)$ 那么一定满足 $(u,v_2)$

那么考虑点 $u$ ，限制一端在 $u$ 子树内的情况，那么设状态$f_{u,i}$ 为 $u$ 子树内边状态已经确定，下端点在子树内且没有被满足的条件中，上端点最深的深度是 $y$

对于转移，考虑边的权值是 $0/1$ ，那么有：

$$f_{u,i}=\sum_{j=0}^{depth_u}f_{u,i}\times f_{v,j} + \sum_{j=0}^i f_{u,i}\times f_{v,j} + \sum_{j=0}^{i-1}f_{y,i}\times f_{u,j}$$

枚举前缀和就有 $64$

设 $g_{u,i}=\sum_{j=0}^i f_{u,i}$ ，转移即为：

$$f_{u,i}=f_{u,i}\times (g_{v,depth_u}+g_{v,i})+g_{u,i-1}\times f_{v,i}$$

对于 $g_{v,depth_u}$ 可以用线段树合并，设 $Size_1=g_{v,depth_u}+g_{v,i},Size2=g_{x,i-1}$

具体实现见代码

const int N=5e5+100;
const int mod=998244353;
vector<int> G[N];
int head[N],Next[N<<1],ver[N<<1],depth[N],tot;
int n,m,cnt,T[N];

inline void fix(int &x){ x>=mod ? x-=mod : 0;}
inline void add(int u,int v){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot;}

namespace ST{
    struct node{
        int ls,rs,sum,mul;
    }tr[N<<5];
    inline void pushdown(int now){
        if(tr[now].ls){
            tr[ tr[now].ls ].sum=(ll) tr[ tr[now].ls ].sum*tr[now].mul%mod;
            tr[ tr[now].ls ].mul=(ll) tr[ tr[now].ls ].mul*tr[now].mul%mod;
        }
        if(tr[now].rs){
            tr[ tr[now].rs ].sum=(ll) tr[ tr[now].rs ].sum*tr[now].mul%mod;
            tr[ tr[now].rs ].mul=(ll) tr[ tr[now].rs ].mul*tr[now].mul%mod;
        }
        tr[now].mul=1;
    }
    int query(int now,int l,int r,int pos){
        if(!now || r<=pos) return tr[now].sum;
        rei mid=l+r>>1; rei sum=0;
        pushdown(now);
        if(mid<pos) fix(sum+=query(tr[now].rs,mid+1,r,pos));
        fix(sum+=query(tr[now].ls,l,mid,pos));
        return sum;
    }
    void build(int &now,int l,int r,int pos){
        now=++cnt;
        tr[now].sum=tr[now].mul=1;
        if(l==r) return ;
        rei mid=l+r>>1;
        pos<=mid ? build(tr[now].ls,l,mid,pos) : build(tr[now].rs,mid+1,r,pos);
    }
    int merge(int x,int y,int l,int r,int &size1,int &size2){
        if(!x && !y) return 0;
        if(!x || !y){
            if(!x){
                fix(size1+=tr[y].sum);
                tr[y].sum=(ll) tr[y].sum*size2%mod;
                tr[y].mul=(ll) tr[y].mul*size2%mod;
                return y;
            }
            fix(size2+=tr[x].sum);
            tr[x].sum=(ll) tr[x].sum*size1%mod;
            tr[x].mul=(ll) tr[x].mul*size1%mod;
            return x;
        }
        if(l==r){
            rei tmpx=tr[x].sum,tmpy=tr[y].sum;
            fix(size1+=tmpy);
            tr[x].sum=((ll) tr[x].sum*size1%mod+tr[y].sum*size2%mod)%mod;
            fix(size2+=tmpx);
            return x;
        }
        pushdown(x),pushdown(y);
        rei mid=l+r>>1;
        tr[x].ls=merge(tr[x].ls,tr[y].ls,l,mid,size1,size2);
        tr[x].rs=merge(tr[x].rs,tr[y].rs,mid+1,r,size1,size2);
        tr[x].sum=(tr[ tr[x].ls ].sum+tr[ tr[x].rs ].sum)%mod;
        return x;
    }
}

void dfs(int x,int fa){
    depth[x]=depth[fa]+1;
    rei MAX=0;
    for(auto y:G[x]) MAX=max(MAX,depth[y]);
    ST::build(T[x],0,n,MAX);
    for(rei i=head[x];i;i=Next[i]){
        rei y=ver[i]; if(y==fa) continue;
        dfs(y,x);
        rei Size=ST::query(T[y],0,n,depth[x]),Size2=0;
        T[x]=ST::merge(T[x],T[y],0,n,Size,Size2);
        // printf("now at %d,T[x]=%d\n",x,T[x]);
        // printf("%d %d\n",Size,Size2);
    }
}

signed main(){
    scanf("%lld",&n);
    for(rei i=1,u,v;i<n;++i) scanf("%lld%lld",&u,&v),add(u,v),add(v,u);
    scanf("%lld",&m);
    for(rei i=1,u,v;i<=m;++i) scanf("%lld%lld",&u,&v),G[v].push_back(u);
    dfs(1,0);
    printf("%lld\n",ST::query(T[1],0,n,0));
    getchar(),getchar();
    return 0;
}