头像

wxy_


访客:2201

离线:3小时前



wxy_
4天前

题目描述

给定$n$,要求找到$k$个不同的组合数$\binom{a_i}{b_i}$满足$0≤b_i≤a_i≤n$且所有组合数本质不同。

两个组合数本质不同当且仅当$a_i≠a_j$或$b_i≠b_j$

输入格式

从标准输入读入数据。

第一行两个整数 $n,k$。

输出格式

输出到标准输出。

一行一个整数,代表 $k$ 个组合数的和对 $10^9+7$取模之后的结果;数据保证一定有至少 $k$ 个数可以选。

输入输出样例

input:
2 3
output:
4

说明/提示

对于$100$%的数据,满足$1≤n≤10^6,1≤k≤10^5$

思路

首先有一个显然的结论,若存在一组组合数

$$
\binom{m}{j},\binom{n}{j} \ (m<n)
$$
那么有
$$
\binom{m}{j}<\binom{n}{j}
$$
那么我们可以把所有的$\binom{n}{i}(0≤i≤n)$放入一个集合维护,每次取出最大的,取$k$次。

那么我们可以维护一个大根堆,存一下二元组$(n,k)$,每次取出$\binom{n}{k}$中最大的,取完后再将$\binom{n-1}{k}$加入大根堆。

但是$n$最多可至$10^6$,通过组合数比较显然不现实,这里采用一种十分巧妙的方法:取对数。
$$
\begin{aligned}
log\binom{n}{k}&=log\frac{n!}{k!(n-k)!}\\
&=log(n!)-log(k!)-log(n-k)!\\
&=\sum_{i=1}^nlog(i)-\sum_{j=1}^klog(j)-\sum_{p=1}^{n-k}log(n-k)
\end{aligned}
$$
可以通过预处理前缀和$O(n)$处理出所有的$log$前缀和,然后$O(1)$询问。

总复杂度为$O(n+k\ log\ n)$

代码

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

const int N = 1e6 + 50,mod = 1e9 + 7;

typedef std::pair<long long,long long> PLL;
typedef std::pair<double,PLL> PDL;

std::priority_queue <PDL,std::vector<PDL>,std::less<PDL> > heap;

long long fac[N],invfac[N];

double sum[N];

namespace wxy{

    inline int C(int n,int m){return n<m?0:(long long)fac[n]*invfac[m]%mod*invfac[n-m]%mod;}

    inline void init(){
        for(int i = 1; i <= 1e6; i++) sum[i] = sum[i - 1] + log(i);
        fac[0]=invfac[0]=invfac[1]=1;
        for(int i=1;i<=1e6;i++)fac[i]=(long long)fac[i-1]*i%mod;
        for(int i=2;i<=1e6;i++)invfac[i]=(long long)(mod-mod/i)*invfac[mod%i]%mod;
        for(int i=2;i<=1e6;i++)invfac[i]=(long long)invfac[i-1]*invfac[i]%mod;
    }

    inline double get(int n,int m){return sum[n] - sum[m] - sum[n - m];}

    inline void insert(int n,int m){
        PDL a;
        a.first = get(n,m);
        a.second.first = n;
        a.second.second = m;
        heap.push(a);
    }

    void main(){
        init();
        int n,k;
        std::cin >> n >> k;
        for (int i = 0;i <= n; i++) insert(n,i);
        long long ans = 0;
        while (k--){
            int n = heap.top().second.first,m = heap.top().second.second;
            ans = (ans % mod + C(n,m) % mod) % mod;
            n--;
            heap.pop();
            if (n >= m) insert(n,m);
        }
        std::cout << ans % mod;
    }

}signed main(){wxy::main();return 0;}


活动打卡代码 AcWing 307. 连通图

wxy_
5天前
#include <iostream>
#include <cstring>

const int N = 55;

unsigned long long f[N],c[N][N],two[N << 1];

namespace wxy{
    inline unsigned long long get(int n){return two[n * (n - 1) / 2];}
    inline void init(){
        two[0] = c[0][0] = 1;
        for (int i = 1; i <= 250; i++) two[i] = two[i - 1] * 2;
        for (int i = 1; i <= 50; i++){
            c[i][0] = 1;
            for (int j = 1; j <= i; j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
    inline unsigned long long sol(int n){
        memset(f,0,sizeof f);
        for (int i = 1; i <= n; i++){
            f[i] = get(i);
            for (int j = 1; j < i; j++)
                f[i] -= f[j] * c[i-1][j-1] * get(i-j); 
        }
        return f[n];
    }
    void solve(){
        init();
        int n;
        while(std::cin >> n && n){
            std::cout << 1ll * sol(n) << std::endl;
        }
    }
}signed main(){wxy::solve();return 0;}






wxy_
5天前

我们可以知道,从点$\left (x_i,y_i \right )$到点$\left (x_j,y_j \right )$的路径数为$\binom{x_j-x_i+y_j-y_i}{x_j-x_i}$

不考虑黑白格子的限制,从点$\left ( 1,1\right )$到$(h,w)$的路径共有$\binom{h+w-2}{h-1}$种。

如果存在一个黑格子,那么所有经过当前黑格子到$(h,w)$的路径都不合法。

考虑两部分,即从$(1,1)→(x_i,y_i)$与$(x_i,y_i)→(h,w)$

根据乘法原理,从经过黑格子$(x_i,y_i)$到$(h,w)$的总路径为

$$
\binom{x_i+y_i-2}{x_i-1}\times \binom{h-x_i+w-y_i}{h-x_i}
$$

其中要满足$x_i≤h,y_i≤w$

考虑两个黑格子的情况,$(x_i,y_i),(x_j,y_j)$其中$(x_i,y_i)$在$(x_j,y_j)$的前面。

如果两个格子都像前面那样计算,则会产生重复计数。

即从$(x_i,y_i)→(x_j,y_j)→(h,w)$的路径会算两次。

如果我们要进行容斥,不同集合的交各不相同,其复杂度是指数级的。

我们考虑$(x_j,y_j)$的计算

如果我们每次计算黑格子的方案时,都把经过他前面的黑格子的路径给减掉,不就不会产生重复计数了吗?

设$f(i)$为在不经过前面黑格子到第$i$个黑格子的方案数。

那么有
$$
ans=\binom{h+w-2}{h-1}-\sum_{i=1}^nf(i)\binom{h-x_i+w-y_i}{h-w_i}
$$
同理对于$f(i)$有
$$
f(i)=\binom{x_i+y_i-2}{x_i-1}-\sum_{j=1}^{i-1}f(j)\binom{x_i-x_j+y_i-y_j}{x_i-x_j}
$$
代码:

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10,M = 2e3 + 10,mod = 1e9 + 7;

typedef pair<int,int> PII;

PII a[M];

int f[M];

int fac[N << 1],invfac[N << 1];

int C(int n,int m){return n<m?0:(long long)fac[n]*invfac[m]%mod*invfac[n-m]%mod;}

void init(){
    fac[0]=invfac[0]=invfac[1]=1;
    for(int i=1;i<=2e5 + 10;i++)fac[i]=(long long)fac[i-1]*i%mod;
    for(int i=2;i<=2e5 + 10;i++)invfac[i]=(long long)(mod-mod/i)*invfac[mod%i]%mod;
    for(int i=2;i<=2e5 + 10;i++)invfac[i]=(long long)invfac[i-1]*invfac[i]%mod;
}

int main(){
    init();
    int h,w,n;
    cin >> h >> w >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a + 1,a + n + 1);
    a[n + 1].first = h,a[n + 1].second = w;
    for (int i = 1; i <= n + 1; i++){
        f[i] = C(a[i].first+a[i].second - 2,a[i].first - 1);
        for (int j = 1; j < i; j++){
            if (a[j].first > a[i].first || a[j].second > a[i].second) continue;
            f[i] = (f[i] - 1ll * f[j] * C(a[i].first-a[j].first+a[i].second-a[j].second,a[i].first-a[j].first) + mod) % mod;
        }
    }  
    cout << (f[n + 1] + mod) % mod;
    return 0;
}




wxy_
5天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10,M = 2e3 + 10,mod = 1e9 + 7;


typedef pair<int,int> PII;

PII a[M];

int f[M];

int fac[N << 1],invfac[N << 1];

int C(int n,int m){return n<m?0:(long long)fac[n]*invfac[m]%mod*invfac[n-m]%mod;}

void init(){
    fac[0]=invfac[0]=invfac[1]=1;
    for(int i=1;i<=2e5 + 10;i++)fac[i]=(long long)fac[i-1]*i%mod;
    for(int i=2;i<=2e5 + 10;i++)invfac[i]=(long long)(mod-mod/i)*invfac[mod%i]%mod;
    for(int i=2;i<=2e5 + 10;i++)invfac[i]=(long long)invfac[i-1]*invfac[i]%mod;
}

int main(){
    init();
    int h,w,n;
    cin >> h >> w >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a + 1,a + n + 1);
    a[n + 1].first = h,a[n + 1].second = w;
    for (int i = 1; i <= n + 1; i++){
        f[i] = C(a[i].first+a[i].second - 2,a[i].first - 1);
        for (int j = 1; j < i; j++){
            if (a[j].first > a[i].first || a[j].second > a[i].second) continue;
            f[i] = (f[i] - 1ll * f[j] * C(a[i].first-a[j].first+a[i].second-a[j].second,a[i].first-a[j].first) + mod) % mod;
        }
    }  
    cout << (f[n + 1] + mod) % mod;
    return 0;
}




wxy_
8天前

题目描述

一个有$N$个元素的集合有$2^N$个不同子集(包含空集),现在要在这$2^N$个集合中取出若干集合(至少一个),使得
它们的交集的元素个数为$K$,求取法的方案数,答案模$1e9+7$。

输入格式

一行两个整数$N,K$

输出格式

一行为答案。

对于$100$%的数据,$1≤N≤1000000$;$0≤K≤N$;

$ (TimeLimit:1s,MemoryLimit:128M)$

思路

我们首先确定我们交集所包含的$k$个元素,一共有$\binom{n}{k}$种方法。

假定我们当前确定的包含$k$个的元素的集合为$S$。

那么包含$S$的子集相当于在除了$S$包括的元素中,选任意多元素的元素凑成的子集。

那么包含$S$的所有子集有
$$
\sum_{i=0}^{n-k}\binom{n-k}{i}=2^{n-k}
$$

从中选任意多个集合相交共有
$$
\sum_{i=1}^{2^{n-k}}\binom{2^{n-k}}{i}=\sum_{i=0}^{2^{n-k}}\binom{2^{n-k}}{i}-\binom{2^{n-k}}{0}=2^{2^{n-k}}-1
$$
种方案

但是这样算是所有交集大于等于$k$个元素的方案,即除了$S$还有其他的交集。

那么我们就要把其中所有交集大小大于$k$个元素的方案给减掉。

所有交集大小大于$k$个元素的方案等价于所有交集大小大于等于$k+1$个元素的方案。

我们当前的方案已经确定了包含$k$个元素的集合$S$,那么我们只需要在除了$S$的元素中任选一个即可凑成一个包含$k+1$个元素的集合,设除了$S$以外的元素为$a$,那么我们就可以用上面的方法算出交集至少为$S,a$的方案数。其中$a$共有$\binom{n-k}{1}$种选法。

那么是否我们直接减去
$$
\binom{n-k}{1}(2^{2^{n-k-1}}-1)
$$

就是交集恰好为$S$的方案数呢?

考虑下面的情况:

{$Sabcd,Sabcf$}

交集为$Sabc$

而当我们确定交集至少为$Sa,Sb,Sc$都可以凑成这种方案,也就会产生重复计数导致答案变小。

我们设$P_a$为交集除了包括$S$,还需包括$a$的集合。

那么我们要求的是一个并集的关系,即
$$
\left|\bigcup P \right|
$$
我们考虑任意两个方案集合$P_a$与$P_b$的交集
$$
\left|P_a \bigcap P_b \right|
$$
考虑其意义,即满足交集至少包含$S$,$a$,$b$的方案。

那么有

$$
\left|P_a \bigcap P_b \right|=(2^{2^{n-k-2}}-1)
$$

其方案集合交集的大小只与相交集合的个数有关,与具体是哪几个相交无关。

而$P$集合一共有$n-k$个

那么有
$$
\left|\bigcup P \right|=\sum_{i=1}^{n-k}\binom{n-k}{i}(-1)^{i-1}(2^{2^{n-k-i}}-1)
$$

那么确定交集为$k$个元素的方案数为
$$
\begin{aligned}
(2^{2^{n-k}}-1)-\left|\bigcup P \right|&=(2^{2^{n-k}}-1)-\sum_{i=1}^{n-k}\binom{n-k}{i}(-1)^{j-1}(2^{2^{n-k-i}}-1)\\
&=(2^{2^{n-k}}-1)+\sum_{i=1}^{n-k}\binom{n-k}{i}(-1)^{i}(2^{2^{n-k-i}}-1)\\
&=\sum_{i=0}^{n-k}\binom{n-k}{i}(-1)^{i}(2^{2^{n-k-i}}-1)
\end{aligned}
$$
那么答案为
$$
\binom{n}{k}\times \sum_{i=0}^{n-k}\binom{n-k}{i}(-1)^{i}(2^{2^{n-k-i}}-1)
$$
那么不同的两个交集$S$和$A$之间的方案是否会有冲突?

那么显然是不会的,在我们上面的计算中,可以确保我们每种选$k$个元素的方案的交集一定是交集恰好为$S$或$A$的。

代码

#include <iostream>

using namespace std;

const int N = 1e6 + 10,mod = 1e9 + 7;

long long fac[N],invfac[N],two[N];

int C(int n,int m){return n<m?0:(long long)fac[n]*invfac[m]%mod*invfac[n-m]%mod;}

inline void init(){
    fac[0]=invfac[0]=invfac[1]=1;
    for(int i=1;i<=N - 10;i++)fac[i]=(long long)fac[i-1]*i%mod;
    for(int i=2;i<=N - 10;i++)invfac[i]=(long long)(mod-mod/i)*invfac[mod%i]%mod;
    for(int i=2;i<=N - 10;i++)invfac[i]=(long long)invfac[i-1]*invfac[i]%mod;
    two[0] = 2;
    for (int i = 1; i <= N - 10; i++){
        two[i] = two[i - 1] * two[i - 1] % mod;
    }
}

int main(){
    init();
    int n,k;
    cin >> n >> k;
    long long ans = 0;
    for (int i = 0;i <= n - k; i++){
        if ((i % 2) == 0) ans = (ans + C(n-k,i) * (two[n - k - i] - 1) % mod) % mod;
        else ans = (ans - C(n-k,i) * (two[n - k - i] - 1) % mod + mod) % mod; 
    }
    cout << C(n,k) * ans % mod;
    return 0;
}



wxy_
17天前

特殊处理方法

捆绑法

如果要求若干物品相邻,则可以将它们作为一个整体来进行计数。
$ABCDE$五个人要排队,$A$和$B$要相邻,$C$和$D$要相邻,求有多少种排列方法。

把$AB$看作一个整体,$CD$看成一个整体。再计算$AB$与$CD$内部的相对顺序。

方案数:$3!\times2!\times2!=24$。

插空法

如果要求若干物品两两不相邻,可以先将其他物品放好,然后将这些物品插入其中,进行计数。

$ABCDEFG$七个人要排队,$ABC$三个人两两不相邻,求方案数。

先将$DEFG$四个人排好,中间有$5$个空位(包括其两侧的),$ABC$只能插入到空位中。

方案数:$4!\times A_5^3=1440$

隔板法

把个相同的苹果分给$k$个人,要求每个人至少分到一个,求方案数。

把$n$个苹果排成一排,在其中插入$k-1$块隔板,表示$k$个人分到的部分。

插隔板的方法与分苹果的方案是一一对应的,那么方案数为$\binom{n-1}{k-1}$

那么如果有人可以分到$0$个苹果呢?

我们给每个人多分一个苹果,使得每个人至少分配到一个苹果,在分配完之后再将每个人的苹果拿走一个。

那么方案数为$\binom{n+k-1}{k-1}$

隔板法与不定方程整数解问题

求不定方程$x_1+x_2+x_3+x_4+....+x_k=n$的解的个数,要求$x_i>d_i$

设$y_i=x_i-d_i>0$

那么有$y_1+y_2+y_3+y_4+....+y_k=n-(d_1+d_2+d_3+d_4+....+d_k)$

那么原问题就等价于“分苹果”的问题,即有$n-(d_1+d_2+d_3+d_4+....+d_k)$个苹果,分给$k$个人,要求每个人分到的苹果都大于$0$
那么方案数为。
$$
\binom{n-(d_1+d_2+d_3+d_4+....+d_k)-1}{k-1}
$$

多重集的排列数与组合数

设$S=$ {$n_1a_1,n_2a_2,…,n_ka_k$}是由$n_1$个$a_1$,$n_2$个$a_2$,$n_k$个$a_k$组成的多重集。

多重集排列数

多重集$S$的全排列,不考虑相同的元素,其全排列个数为$(\sum_{i=1}^kn_i)!$,但是因为存在若干个相同的元素,因此要把相同元素的贡献给除掉。

对于每种排列的每个$a_{i,j}$,我们都可以从$n_i$个$a_i$中挑选任意一个,其对答案的贡献满足乘法原理为$n_i!$

因此方案数为
$$
\frac{(\sum_{i=1}^kn_i)!}{\prod_{i=0}^kn_i!}
$$

多重集的组合数

求从多重集$S$中取$r$个元素的组合数的。

不考虑$n_i$个元素的限制,即从多重集$S’= ${$∞a_1,∞a_2,…,∞a_k$}中取$r$个元素的组合数。

我们设$a_i$取$x_i$个,那么原问题就等价于不定方程$\sum_{i=1}^kx_i=r\ (x≥0)$的解的个数。

等价于一共有$r$个苹果,分给$k$个人,可以有人拿$0$个苹果的方案数。

用隔板法计算,其方案为$\binom{r+k-1}{k-1}$

我们考虑第每个$a_i$的$n_i$的限制。

设不满足第$i$个限制的方案集合为$F_i$

那么答案即为$\binom{r+k-1}{k-1}-\left |\bigcup_{i=1}^nF_i \right |$

而$|\left |\bigcup_{i=1}^nF_i \right |$则可以用容斥原理计算。

类似[HAOI2008]硬币购物,我们先把$n_i+1$个拿出来,那么其余的我们不用管他,不管怎么安排,肯定都是非法方案。

显然有$\left|F_i\bigcap F_j \right|=\binom{r+k-1-(n_i+n_j+2)}{k-1}$

那么答案为
$$
\binom{r+k-1}{k-1}-\sum_{T \subseteq{1,2,…,k}}(-1)^{|T|-1}\binom{k+r-1-(\sum_{j \in T}n_j+|T|)}{k-1}
$$




wxy_
17天前

二项式系数的应用与和式简单处理

化简:$\sum_{i=0}^n\binom{n}{i}i$

解:
$$
\begin{aligned}
\sum_{i=0}^n\binom{n}{i}i \ &=\sum_{i=0}^n\frac{n}{i}\binom{n-1}{i-1}i\\
&=n\times \sum_{i=0}^{n-1}\binom{n}{i}\\
&=n\times2^{n-1}
\end{aligned}
$$

化简$\sum_{i=0}^n\sum_{j=0}^i\binom{n}{j}$

(交换求和顺序)

解:
$$
\begin{aligned}
\sum_{i=0}^{n} \sum_{j=0}^{i}\left(\begin{array}{l}
n \\
j
\end{array}\right) &=\sum_{j=0}^{n}\left(\begin{array}{c}
n \\
j
\end{array}\right) \sum_{i=j}^{n} 1 \\
&=\sum_{j=0}^{n}\left(\begin{array}{c}
n \\
j
\end{array}\right)(n-j+1) \\
&=(n+1) \sum_{j=0}^{n}\left(\begin{array}{c}
n \\
j
\end{array}\right)-\sum_{j=0}^{n} j\left(\begin{array}{c}
n \\
j
\end{array}\right) \\
&=(n+1) 2^{n}-n 2^{n-1} \\
&=(n+2) 2^{n-1}
\end{aligned}
$$

化简:$\sum_{i=k}^n\binom{i}{k}$

解:将其看成$\sum_{i=k}^n(1+x)^i$的$k$次幂系数和
$$
\begin{aligned}
\sum_{i=k}^n(1+x)^i&=(1+x)^k\times\frac{1-(1+x)^{n-k+1}}{1-(1+x)}\\
&=\frac{(1+x)^{n+1}-(1+x)^k}{x}\\
&=\frac{\sum_{i=0}^{n+1}\binom{n+1}{i}x^i-\sum_{j=0}^k\binom{k}{j}x^j}{x}\\
&=\frac{x(\sum_{i=0}^{n+1}\binom{n+1}{i}x^{i-1}-\sum_{j=0}^k\binom{k}{j}x^{j-1})}{x}\\
&=\sum_{i=0}^{n+1}\binom{n+1}{i}x^{i-1}-\sum_{j=0}^k\binom{k}{j}x^{j-1}
\end{aligned}
$$
因为$j-1$不可能等于$k$,因此即为$\sum_{i=0}^{n+1}\binom{n+1}{i}x^{i-1}$的$k$次项的系数,$i-1=k$时,二项式系数为$\binom{n+1}{k+1}$
(也可以把$\binom{k}{k}$看成$\binom{k+1}{k+1}$归纳递推)



活动打卡代码 AcWing 166. 数独

wxy_
19天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

char s[100];

int col[10],row[10],maze[5][5];

int mz[20][20];

int ones[1 << 10];

int table[1 << 9 + 10];

inline int lowbit(int x){
    return x & -x;
}



inline void flip(int x,int y,int z){
    col[x] ^= 1 << z;
    row[y] ^= 1 << z;
    maze[x / 3][y / 3] ^= 1 << z;
}

bool dfs(int now){
    if (now == 0) return true;
    int minv = 10;
    int x,y,v;
    for (int i = 0; i <= 8; i++){
        for (int j = 0; j <= 8; j++){
            if (mz[i][j] != 0) continue;
            int val = col[i] & row[j] & maze[i / 3][j / 3];
            if (!val) return false;
            int sum = ones[val];
            if (sum < minv){
                minv = sum;
                x = i;
                y = j;
                v = val;
            }
        }
    }
    for (int i = v; i > 0; i -= lowbit(i)){
        int w = lowbit(i);
        int z = table[w];
        flip(x,y,z);
        mz[x][y] = z;
        if (dfs(now - 1)) return true;
        flip(x,y,z);
        mz[x][y] = 0;
    }
    return false;
}

int main(){

    for (int i = 0; i <= 1 << 10; i++){
        int res = 0;
        for (int j = 0; j  <= 9; j++)
            if (i >> j & 1) res++;
        ones[i] = res;
    }
    for (int i = 0; i <= 9; i++) table[1 << i] = i;

    while(~scanf("%s", s) && s[0] != 'e'){
        memset(mz,0,sizeof mz);
        for (int i = 0; i <= 9; i++){
            col[i] = row[i] = (1 << 10) - 2;
        }
        for (int i = 0; i <= 3; i++){
            for (int j = 0; j <= 3; j++){
                maze[i][j] = (1 << 10) - 2;
            }
        }

        int n = strlen(s);
        for (int i = 0; i < n; i++){
            if (s[i] != '.'){
                int x,y;
                int val = s[i] - '0';
                if ((i + 1) % 9 == 0){
                    x = 8;
                    y = (i + 1) / 9 - 1;
                }else{
                    x = (i + 1) % 9 - 1;
                    y = i / 9;
                }
                mz[x][y] = val;
                flip(x,y,val);
            }
        }


        int ct = 0;
        for (int i = 0; i <= 8; i++)
            for (int j = 0; j <= 8; j++)
                if (mz[i][j] == 0)ct++;


        dfs(ct);

        for (int i = 0;i <= 8; i++){
            for (int j = 0; j <= 8; j++){
                cout << mz[j][i];
            }
        }
        cout << endl;

    }

    return 0;
}




wxy_
1个月前

配套视频:
https://www.bilibili.com/video/BV1T5411a7LJ

加法原理

完成一件事情有$n$类方法,每类方法分别有$a_1…a_n$种方法

那么完成这件事情的方法总数为

$$
\sum_{i=1}^n
a_i
$$

乘法原理

如果完成一件事情有$n$个步骤,每个步骤有若干种方法分别$a_1…a_n$

那么完成这件事情的方法总数为$a_1\times a_2…\times a_n$

排列数

从$n$个不同元素中取出$m(m <=n)$个元素的所有排列的个数,叫做从$n$个不同元素中取出$m$个元素的排列数,⽤符号$A_n^m$表示
$$
A_n^m=n(n-1)(n-2)(n-3)(n-4)…(n-m+1)=\frac{n!}{(n-m)!}
$$

组合数

从$n$个不同元素中取出$m$个元素的所有组合的个数,叫做从$n$个不同元素中取出$m$个元素的组合数。⽤符号$C_n^m$或$\binom{n}{m}$来表示
$$
\binom{n}{m}=\frac{n!}{m!(n-m)!}
$$

组合恒等式

$$
\begin{aligned}
\binom{n}{m}&= \binom{n}{n-m} \\
\binom{n}{m}&=\frac{n}{m}\binom{n-1}{m-1} \\
m\binom{n}{m}&=n\binom{n-1}{m-1} \\
(n-m)\binom{n}{i}&=n\binom{n-1}{m} \\
\binom{n}{m}&=\binom{n-1}{m-1}+\binom{n-1}{m}
\end{aligned}
$$

组合数的求法(组合恒等递推$O(nm)$求组合数)

for(int i=0;i<=n;i++){   
    c[i][j]=1;   
    for(int j=1;j<=i;j++)c[i][j]=c[i-1][j]+c[i-1][j-1]; 
} 

组合数求法(乘法逆元$O(n)$求组合数)

intC(int n,int m){return n<m?0:(longlong)fac[n]*invfac[m]%mod*invfac[n-m]%mod;}
fac[0]=invfac[0]=invfac[1]=1;
for(int i=1;i<=n;i++)fac[i]=(longlong)fac[i-1]*i%mod;
for(int i=2;i<=n;i++)invfac[i]=(longlong)(mod-mod/i)*invfac[mod%i]%mod;
for(int i=2;i<=n;i++)invfac[i]=(longlong)invfac[i-1]*invfac[i]%mod;

二项式系数与二项式反演

杨辉三角

$$
\begin{aligned}
&1\\
&1\ 1\\
&1\ 2\ 1\\
&1\ 3\ 3\ 1\\
&1\ 4\ 6\ 4\ 1
\end{aligned}
$$
因为其每个数是左上与右上的数的和,即$f[i][j]=f[i-1][j]+f[i-1][j-1]$且有组合恒等$\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$,且$\binom{0}{0}=f[0][0]=1$
因此杨辉三角第$i$行$j$个数即为$\binom{i}{j}$

$(x+1)^n$的系数

观察下面的等式与杨辉三角的关系:
$$
\begin{aligned}
&(x+1)^0=1\\
&(x+1)^1=x+1\\
&(x+1)^2=x^2+2x+1\\
&(x+1)^3=x^3+3x^2+3x+1\\
&(x+1)^4=x^4+4x^3+6x^2+4x+1
\end{aligned}
$$
我们发现系数的分布极其地像杨辉三角。
考虑组合意义:

有$n$个互不相同的球,每个我们可以选或者不选,求选出$k$个球的方案数。

$(x+1)^n$相当于是$n$个二项式$(x+1)$的乘积,如果我们在这$n$个等式中每次都可以选择$x$或$1$相乘,我们最少可以选$0$个$x$,最多可以选$n$个$x$。

那么有:

$$
(1+x)^n=\sum_{i=0}^n\binom{n}{i}x^i
$$

那么推广到$(a+b)^n$的情况,如果$a$选了$i$个,那么$b$必然选了$n-i$个,那么有:

$$
(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{n-i}(n≥0)
$$

从式子的推导同样可以得到:
我们已经有$(1+x)^n=\sum_{i=0}^n\binom{n}{i}x^i$。
令$x=\frac{a}{b}$有
$$
(\frac{a}{b}+1)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{(-i)}
$$
两边同时乘$b^n$
$$
(a+b)^n=\sum_{i=0}^{n}\binom{n}{i}a^ib^{n-i}
$$

特殊恒等

$$
\begin{aligned}
a=1,b=1 \\
\sum_{i=0}^n\binom{n}{i}=2^n
\end{aligned}
$$


$$
\begin{aligned}
a=1,b=-1 \\
\sum_{i=0}^n\binom{n}{i}(-1)^i=0
\end{aligned}
$$

其中奇数项的和等于偶数项的和


二项式系数的应用与和式简单处理

化简:$\sum_{i=0}^n\binom{n}{i}i$

解:
$$
\begin{aligned}
\sum_{i=0}^n\binom{n}{i}i \ &=\sum_{i=0}^n\frac{n}{i}\binom{n-1}{i-1}i\\
&=n\times \sum_{i=0}^{n-1}\binom{n}{i}\\
&=n\times2^{n-1}
\end{aligned}
$$

化简$\sum_{i=0}^n\sum_{j=0}^i\binom{n}{j}$

(交换求和顺序)

解:
$$
\begin{aligned}
\sum_{i=0}^{n} \sum_{j=0}^{i}\left(\begin{array}{l}
n \\
j
\end{array}\right) &=\sum_{j=0}^{n}\left(\begin{array}{c}
n \\
j
\end{array}\right) \sum_{i=j}^{n} 1 \\
&=\sum_{j=0}^{n}\left(\begin{array}{c}
n \\
j
\end{array}\right)(n-j+1) \\
&=(n+1) \sum_{j=0}^{n}\left(\begin{array}{c}
n \\
j
\end{array}\right)-\sum_{j=0}^{n} j\left(\begin{array}{c}
n \
j
\end{array}\right) \\
&=(n+1) 2^{n}-n 2^{n-1} \\
&=(n+2) 2^{n-1}
\end{aligned}
$$

化简:$\sum_{i=k}^n\binom{i}{k}$

解:将其看成$\sum_{i=k}^n(1+x)^i$的$k$次幂系数和
$$
\begin{aligned}
\sum_{i=k}^n(1+x)^i&=(1+x)^k\times\frac{1-(1+x)^{n-k+1}}{1-(1+x)}\\
&=\frac{(1+x)^{n+1}-(1+x)^k}{x}\\
&=\frac{\sum_{i=0}^{n+1}\binom{n+1}{i}x^i-\sum_{j=0}^k\binom{k}{j}x^j}{x}\\
&=\frac{x(\sum_{i=0}^{n+1}\binom{n+1}{i}x^{i-1}-\sum_{j=0}^k\binom{k}{j}x^{j-1})}{x}\\
&=\sum_{i=0}^{n+1}\binom{n+1}{i}x^{i-1}-\sum_{j=0}^k\binom{k}{j}x^{j-1}
\end{aligned}
$$
因为$j-1$不可能等于$k$,因此即为$\sum_{i=0}^{n+1}\binom{n+1}{i}x^{i-1}$的$k$次项的系数,$i-1=k$时,二项式系数为$\binom{n+1}{k+1}$
(也可以把$\binom{k}{k}$看成$\binom{k+1}{k+1}$归纳递推)


二项式反演

而对于两个数列有

$$
f_n=\sum_{i=0}^n(-1)^i\binom{n}{i}g_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^i\binom{n}{i}f_i
$$

变形有

$$
f_n=\sum_{i=0}^{n}\binom{n}{i}g_i \Leftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f_i
$$

容斥原理

$$
\left|\bigcup_{i=1}^{n} A_{i}\right|=\sum_{T \subseteq{1,2,3, \ldots, n}}(-1)^{|T|-1}\left|\bigcap_{j \in T} S_{j}\right|
$$

即对于若干个集合的并集的元素个数,相当于$i(1<=i<=n)$个集合的交集的个数的乘上容斥系数(若交集个数为奇数则为-1,若交集个数为偶数则为+1)和

证明:要证明容斥原理等价于我们要证明每个元素对答案的贡献都为1.

设元素$p$在$k$个元素出现过,那么$p$对答案的贡献为

$$
\sum_{i=1}^k(-1)^{(k-1)}\binom{k}{i}=0-(-1)^{(-1)}\times\binom{k}{0}=1
$$

集合反演

对于函数$f(S),g(S)$有

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

证明

$$
\begin{aligned}
& \sum_{T \subseteq S}(-1)^{|S|-|T|} f(T) \\
=& \sum_{T \subseteq S}(-1)^{|S|-|T|} \sum_{Q \in T} g(Q) \\
=& \sum_{Q \subseteq S} g(Q) \sum_{Q \subseteq T \subseteq S}(-1)^{|S|-|T|} \\
=& \sum_{Q \subseteq S} g(Q) \sum_{T \subseteq(S \backslash Q)}(-1)^{|S \backslash Q|-|T|} \\
=& \sum_{Q \subseteq S} g(Q) h(S \backslash Q)
\end{aligned}
$$

其中

$$
\begin{aligned}
h(S) &=\sum_{T \subseteq S}(-1)^{|S|-|T|} \\
&=\sum_{i=0}^{|S|}\left(\begin{array}{c}
|S| \\
i
\end{array}\right)(-1)^{|S|-i} \\
&=(1-1)^{|S|} \\
&=[S=\varnothing]
\end{aligned}
$$

$$
\sum_{Q \subseteq S} g(Q)[(S \backslash Q)=\varnothing]=g(S)
$$

容斥原理与错排问题通项公式

$n$封信和信箱⼀⼀对应,求把每封信都装错信箱的⽅案数。

对于错排问题,我们有一个递推式,即$D[n]=(n-1)\times (D[n-1]+D[n-2])$

我们可以得知其中全部装错信箱的方案=总方案$-$没有把所有信都装错的方案

即总方案$-$不满足要求的方案

而显然,对于总方案即$n$的全排列,为$n!$

而什么样的方案是不满足的?

我们把我们的信编号为$1,2,3,4,5....n$

其对应的邮箱编号为$1,2,3,4,5....n$

如果存在一个$i$,其对应的邮箱编号是$i$,那么不管其他的信件对应的邮箱的编号是几,这种方案一定不合法。

我们设$A_i$为第$i$封信送进所对应的$i$号邮箱的方案集合。

我们有$1$个邮箱所放的信件是确定的,而其他$n-1$个邮箱放什么信我们都不关心

而对于除了第$i$个邮箱的其他邮箱,每一次分别可以从$(n-1),(n-2),(n-3)…1$封信中挑选一个进去,即有$n-1$步,第$k$步有$(n-k)$种选法,那么其选择的方案总和为$(n-1)!$

即对于任意一个$i$,都有$|A_i|=(n-1)!$

而我们把所有信都装错的方案数就等价于

$$
n!- \left|\bigcup_{i=1}^{n} A_{i}\right|
$$

那么我们只需要用容斥原理求出$A_i$的并集,即可容易地计算出答案

而要进行容斥,就需要知道
$$
\left|\bigcap_{j \in T \subseteq{1,2,3, \ldots, n}} A_{j}\right|
$$
考虑最简单的情况
$$
\left|A_i\bigcap A_j\right|
$$
$A_i$为第$i$个信箱装信$i$的方案
$A_j$为第$j$个信箱装信$j$的方案
因此$A_i \bigcap A_j$就等价于第$i$个信箱装信$i$且第$j$个信箱装信$j$的方案,其方案数为$(n-2)!$同理可推广到若干个集合的情况,即$k$个$A$集合的交的大小为$(n-k)!$

而我们要从$A_1,A_2,A_3,…,A_n$这些集合中,选若干个集合相交,选$k$个集合相交的个数为,则一共有$\binom{n}{k}$种选择方案。那么则有

$$
\begin{aligned}
\left|\bigcup_{i=1}^{n} A_{i}\right| = \sum_{i=1}^{n}(-1)^{(i-1)}\binom{n}{i}(n-i)!
\end{aligned}
$$

那么

$$
\begin{aligned}
D[n]&=n!-\sum_{i=1}^{n}(-1)^{(i-1)}\binom{n}{i}(n-i)! \\
&=n!-\sum_{i=1}^n(-1)^{(i-1)}\frac{n!}{i!} \\
\end{aligned}
$$

[HAOI2008]硬币购物

共有四种硬币,其面值分别为$c_1,c_2,c_3,c_4$

$n$次询问,每次给定每种硬币的个数$D_i$和付款金额$S$,问共有多少种付款方式

$n≤10^3,S≤10^5$

暴力做法

我们可以把问题看作做$n$次多重背包,用单调队列优化,最优的复杂度为$O(n4s)$在这里不详细讨论

完全背包+容斥

对于每次询问,相当于给定四个限制,第$i$个限制即只能至多使用$i$个硬币支付。类似于错排,满足限制的方案数=全部方案数-不满足的方案数

而对于全部的方案数,相当于做体积为$S$的完全背包,而$S$至多为$10^5$,因此我们可以$O(4S)$预处理所有$S$。

而对于不满足条件的方案数

类似于错排,若不满足其中一个限制条件,一定是非法的,我们可以设$A_i$为第$i$种硬币不满足限制的方案集合。

那么不满足条件的方案数即
$$
\left|\bigcup_{i=1}^4 A_i\right|
$$
而对于$|A_i|$,我们当前一共要支付$S$个硬币,而对于第$i$种只能支付$D_i$个,那么我们如果先把$D_i+1$个硬币付完剩下的支付方案(即从四种硬币中支付$S-C_i(D_i+1)$的金额)是一定不合法的,因为第$i$个硬币至少需要选零个,而如果选$0$个,最终还是多付了一个。

因此,第$|A_i|=F[S-C_i(D_i+1)]$

因为我们要求集合的并,因此,我们需要考虑容斥,而考虑容斥我们就需要求出集合的交

我们考虑任意最简单的情况:两个集合的交
$$
\left|A_i \bigcap\ A_j\right|
$$
我们从定义出发,$A_i$为第$i$种硬币不满足限制的方案集合,而$A_j$为第$j$种硬币不满足限制的方案集合。

而显然,同时满足$i$种硬币不满足限制与$j$种硬币不满足限制这样的性质的集合,为它们的交。

同样地,我们可以把他们两个的$D_i+1$都先支付出去,那么则有
$$
\left|A_i \bigcap\ A_j\right|=F[S-C_i(D_i+1)-C_j(D_j+1)]
$$

那么
$$
\begin{aligned}
ans&=F[s]-\left|\bigcup_{i=1}^4 A_i\right| \\
&=F[s]-\sum_{T \subseteq{1,2,3,4}} -1^{|T|-1}\left|\bigcap_{j \in T } A_{j}\right| \\
&=F[s]-(-1)^{|T|-1}F[S-\sum_{j \in T} C_{j}\left(D_{j}+1\right)]\\
&=F[s]+(-1)^{|T|}F[S-\sum_{j \in T} C_{j}\left(D_{j}+1\right)]
\end{aligned}
$$
那么我们可以状压枚举$T$算出答案。

总的复杂度为$O(4S+16n)$
代码:


#include <iostream>

using namespace std;

const int maxn = 10;

int c[maxn],d[maxn];

long long f[100010];

int main(){
    int n;
    cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
    f[0] = 1;
    for (int i = 1; i <= 4; i++){
        for (int j = c[i]; j <= 100010; j++){
            f[j] += f[j - c[i]];
        }
    }
    while(n--){
        int s;
        cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
        long long ans = f[s];
        for (int i = 0; i < 1 << 4; i++){
            long long sum = 0,cnt = 0;
            for (int j = 0; j < 4; j++){
                if (i >> j & 1){ 
                    sum += c[j + 1] * (d[j + 1] + 1);
                    cnt++;
                }
            }
            //cout << sum << endl;
            long long t = s - sum;
            if (cnt % 2 == 0 && t >= 0 && sum != 0) ans += f[s - sum];
            else if (t >= 0 && sum != 0) ans -= f[s - sum];
        }
        cout << ans << endl;
    }
    //system("PAUSE");
    return 0;
}


特殊处理方法

捆绑法

如果要求若干物品相邻,则可以将它们作为一个整体来进行计数。
$ABCDE$五个人要排队,$A$和$B$要相邻,$C$和$D$要相邻,求有多少种排列方法。

把$AB$看作一个整体,$CD$看成一个整体。再计算$AB$与$CD$内部的相对顺序。

方案数:$3!\times2!\times2!=24$。

插空法

如果要求若干物品两两不相邻,可以先将其他物品放好,然后将这些物品插入其中,进行计数。

$ABCDEFG$七个人要排队,$ABC$三个人两两不相邻,求方案数。

先将$DEFG$四个人排好,中间有$5$个空位(包括其两侧的),$ABC$只能插入到空位中。

方案数:$4!\times A_5^3=1440$

隔板法

把个相同的苹果分给$k$个人,要求每个人至少分到一个,求方案数。

把$n$个苹果排成一排,在其中插入$k-1$块隔板,表示$k$个人分到的部分。

插隔板的方法与分苹果的方案是一一对应的,那么方案数为$\binom{n-1}{k-1}$

那么如果有人可以分到$0$个苹果呢?

我们给每个人多分一个苹果,使得每个人至少分配到一个苹果,在分配完之后再将每个人的苹果拿走一个。

那么方案数为$\binom{n+k-1}{k-1}$

隔板法与不定方程整数解问题

求不定方程$x_1+x_2+x_3+x_4+....+x_k=n$的解的个数,要求$x_i>d_i$

设$y_i=x_i-d_i>0$

那么有$y_1+y_2+y_3+y_4+....+y_k=n-(d_1+d_2+d_3+d_4+....+d_k)$

那么原问题就等价于“分苹果”的问题,即有$n-(d_1+d_2+d_3+d_4+....+d_k)$个苹果,分给$k$个人,要求每个人分到的苹果都大于$0$
那么方案数为。
$$
\binom{n-(d_1+d_2+d_3+d_4+....+d_k)-1}{k-1}
$$

多重集的排列数与组合数

设$S=${$n_1a_1,n_2a_2,…,n_ka_k $}是由$n_1$个$a_1$,$n_2$个$a_2$,$n_k$个$a_k$组成的多重集。

多重集排列数

多重集$S$的全排列,不考虑相同的元素,其全排列个数为$(\sum_{i=1}^kn_i)!$,但是因为存在若干个相同的元素,因此要把相同元素的贡献给除掉。

对于每种排列的每个$a_{i,j}$,我们都可以从$n_i$个$a_i$中挑选任意一个,其对答案的贡献满足乘法原理为$n_i!$

因此方案数为
$$
\frac{(\sum_{i=1}^kn_i)!}{\prod_{i=0}^kn_i!}
$$

多重集的组合数

求从多重集$S$中取$r$个元素的组合数的。

不考虑$n_i$个元素的限制,即从多重集$S’=${$∞a_1,∞a_2,…,∞a_k$}中取$r$个元素的组合数。

我们设$a_i$取$x_i$个,那么原问题就等价于不定方程$\sum_{i=1}^kx_i=r\ (x≥0)$的解的个数。

等价于一共有$r$个苹果,分给$k$个人,可以有人拿$0$个苹果的方案数。

用隔板法计算,其方案为$\binom{r+k-1}{k-1}$

我们考虑第每个$a_i$的$n_i$的限制。

设不满足第$i$个限制的方案集合为$F_i$

那么答案即为$\binom{r+k-1}{k-1}-\left |\bigcup_{i=1}^nF_i \right |$

而$|\left |\bigcup_{i=1}^nF_i \right |$则可以用容斥原理计算。

类似[HAOI2008]硬币购物,我们先把$n_i+1$个拿出来,那么其余的我们不用管他,不管怎么安排,肯定都是非法方案。

显然有$\left|F_i\bigcap F_j \right|=\binom{r+k-1-(n_i+n_j+2)}{k-1}$

那么答案为
$$
\binom{r+k-1}{k-1}-\sum_{T \subseteq{1,2,…,k}}(-1)^{|T|-1}\binom{k+r-1-(\sum_{j \in T}n_j+|T|)}{k-1}
$$

下降阶乘幂与上升阶乘幂

下降阶乘幂:$x^{\underline{m}}=n(n-1)(n-2)(n-3)…(n-m+1)$($m$个因子)读作$x$直降$m$次。

上升阶乘幂:$x^{\overline{m}}=n(n+1)(n+2)(n+2)…(n+m-1)$($m$个因子) 读作$x$直升$m$次

显然有$n!=n^{\underline{n}}=1^{\overline{n}}$

负数上指标组合数

我们有$\binom{n}{k}=0\ (k<0)$即当组合数下指标为负数时,值为$0$

那么上指标为负数的时候呢?是否也为$0$呢?显然不是的

例如$\binom{0}{0}=\binom{-1}{-1}+\binom{-1}{0}=1$,其中$\binom{-1}{-1}=0$,那么显然有$\binom{-1}{0}=1$

那么我们应该如何计算出负数上指标的组合数呢?


$$
\binom{n}{m}=(-1)^m\binom{m-n-1}{m}
$$
上述等式过程被称为反转上指标。

证明:
$$
\begin{aligned}
\binom{n}{m}&=\frac{n!}{m!(n-m)!}\\
&=\frac{n^{\underline{m}}}{m!}\\
&=\frac{n(n-1)(n-2)…(n-m+1)}{m!}\\
&=\frac{-1^m(-n)(1-n)(2-n)…(m-n-1)}{m!}\\
&=-1^m\frac{(m-n-1)^{\underline{m}}}{m!}\\
&=(-1)^m\binom{m-n-1}{m}
\end{aligned}
$$

广义二项式定理

在上面,我们已经得到了一般性二项式定理
$$
(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{n-i}(n≥0)
$$
那么如果$n$为负数呢?这时候就需要广义二项式定理来处理了
$$
(a+b)^n=\sum_{k}\binom{n}{i}a^ib^{n-i}
$$
($n$可以为任意实数或复数,只需满足$|a/b|<1$确保和式绝对收敛)

证明可以利用泰勒级数一基复变量理论因为作者能力不足所以不展开叙述。

生成函数(母函数)

通常,我们用一个辅助变量$z$的幂级数来表示一个无限序列$\left\langle a_0,a_1,a_2,a_3…\right\rangle$的生成函数
$$
A(z)=\sum_{i=0}^{n}a_iz^i
$$

卷积

我们定义$A(z)$为无限序列$\left\langle a_0,a_1,a_2,a_3…\right\rangle$的生成函数,$B(z)$为无限序列$\left\langle b_0,b_1,b_2,b_3…\right\rangle$的生成函数。
那么有$A(z)\times B(z)=a_0b_0+(a_0b_1+a_1b_0)z^1+(a_0b_2+a_1b_1+a_2b_0)z^2+(a_0b^3+a_1b^2+a_2b_1+a_3b_0)z^3$

用$\left[z^n\right]A(z)B(z)$表示$A(z)B(z)$中$z^n$的系数


$$
\left[z^n\right]A(z)B(z)=\sum_{i=0}^{n}a_ib^{n-i}
$$
令$c_n=\left[z^n\right]A(z)B(z)=\sum_{i=0}^{n}a_ib^{n-i}$

我们称$\left \langle c_n \right \rangle$为序列$\left \langle a_n\right\rangle$与$\left \langle b_n \right \rangle$的卷积

生成函数与卷积对于求证组合恒等有着至关重要的作用。

由二项式定理可知$\left \langle \binom{n}{0},\binom{n}{1},\binom{n}{2}… \right\rangle$的生成函数为$A(z)=(1+z)^n$

同理,$\left \langle \binom{s}{0},\binom{s}{1},\binom{s}{2}… \right\rangle$的生成函数为$B(z)=(1+z)^s$

$$
A(z)B(z)=(1+z)^{s+n}
$$

对于卷积序列$\left \langle c_m \right \rangle$有
$$
c_m=\sum_{i=0}^m\binom{n}{i}\binom{s}{m-i}
$$
而对于
$$
\left[z^m\right]A(z)B(z)
$$
因为$A(z)B(z)=(1+z)^{s+n}$根据二项式定理有
$$
\left[z^m\right]A(z)B(z)=\binom{s+n}{m}
$$
那么有恒等式
$$
\sum_{i=0}^m\binom{n}{i}\binom{s}{m-i}=\binom{s+n}{m}
$$
上述即为范德蒙德卷积。

我们来看另一个序列

$$
\left \langle (-1)^n\binom{r}{n}\right\rangle=\left\langle\binom{r}{0},-\binom{r}{1},\binom{r}{2},…\right\rangle
$$

其生成函数
$$
G(z)=\sum_{k}\binom{n}{k}(-1)^kz^k=\sum_k(-z)^k=(1-z)^r
$$
而有
$$
(1+z)^r(1-z)^r=(1-z^2)^r
$$
让两边$z^n$相等
$$
\sum_{i=0}^{n}\binom{r}{i}\binom{r}{n-i}(-1)^i=(-1)^{n/2}\binom{r}{n/2}
$$
($n$为偶数时,当$n$为奇数时值为0)

特殊恒等式(重要)

$$
\frac{1}{(1-z)^{n+1}}=\sum_{k≥0}\binom{k+n}{k}z^k
$$
($n≥0$)
$$
\frac{z^n}{(1-z)^{n+1}}=\sum_{k≥0}\binom{n}{k}z^k
$$

($n≥0$)

证明:

对于等式一可以通过反转上指数进行处理

等式一:
$$
\begin{aligned}
\frac{1}{(1-z)^{n+1}}&=(1-z)^{-n-1}\\
&=\sum_{k}\binom{-n-1}{k}(-z)^k\\
&=\sum_{k≥0}\binom{k-(-n-1)-1}{k}z^k(-1)^{2^k}\\
&=\sum_{k≥0}\binom{k+n}{k}z^k\\
&=\sum_{k≥0}\binom{k+n}{n}z^k
\end{aligned}
$$
对于等式二:
$$
\frac{z^n}{(1-z)^{n+1}}=\sum_{k≥0}\binom{k+n}{n}z^{n+k}
$$
令$k’=n+k$有
$$
\frac{z^n}{(1-z)^{n+1}}=\sum_{k’≥0}\binom{k’}{n}z^{k’}
$$

当$n=0$时有
$$
\frac{1}{1-z}=1+z+z^2+z^3+z^4+....=\sum_{k≥0}z^k
$$
序列$\left\langle 1,1,1,1,....\right\rangle$的生成函数,也被称为几何级数。

与任一序列$\left\langle a_n\right\rangle$的卷积为

$$
c_n=\sum_{i=0}^na_i
$$

$\left\langle c_n\right\rangle$的生成函数即为
$$\frac{A(z)}{1-z}$$
其中$A(z)$为$\left\langle a_n\right\rangle$的生成函数



活动打卡代码 AcWing 1152. 格雷码

wxy_
1个月前
#include <iostream>
#include <vector>

using namespace std;

typedef unsigned long long ull;

unsigned long long n,k;

vector<int> a;

ull power(int x){
    ull ans = 1;
    ull a = 2;
    for (; x;x >>= 1){
        if (x & 1) ans = ans * a;
        a = a * a;
    }
    return ans;
}


void solve(ull n,ull k){
    if (n == 1){
        if (k == 0) a.push_back(0);
        else a.push_back(1);
    }else{
        if (k < ull(power(n) / 2)){
            a.push_back(0);
            solve(n - 1,k);
        }
        if (k >= ull(power(n) / 2)){
            a.push_back(1);
            solve(n - 1,power(n) - k - 1);
        }
    }
}


int main(){

    cin >> n >> k;

    solve(n,k);

    for (int i = 0; i < a.size(); i++){
        cout << a[i];
    }

    return 0;
}