Open it quickly

车的放置

有两个限制条件，考虑转化成一个，因此固定一个顺序，这就用转化的方法消除了一个限制。

因此我们算就好。

不 $Si^{?+}$ 则变成规则，因此分成 $a\times(b+d),c\times d$。

因为有地方重复计算减去就好。

车有编号，因此乘上顺序即可。

$$ans=\sum_{i=0}^k\binom{a}{i}\binom{b+d-(k-i)}{i}i! \binom{c}{k-i}\binom{d}{k-i}(k-i)!$$

方程的解

$g(x)$ 为固定的数，问题简单可以转化成模型。

$x_1+x_2+x_3+x_4+x_n=k$ 的正整数解的组数。

因此答案为：

$${g(x)-1 \choose n-1}$$

因为没有取模得用高精度。

但是 $\dotsb$，略。

[CQOI2014] 数三角形

首先给的是行列数，而我们求的是点上数量，因此先都 $+1$。

先不考虑不在一条直线上的，答案为 $\binom{n*m}{3}$

在考虑在一条线上的。

有如下三种情况：

• 同一行
• 同一列
• 同一对角线，双对角线是对称的 $\times 2$ 即可。

前两个好求分别是 $n\times \binom{m}{3},m\times \binom{n}{3}$。

第三个我们先考虑固定一个原点，在枚举一个点，两点确定一条直线，看这条直线上有多少个，然后剩下的如果不是在远点，那就是平移，运用乘法原理即可解决。

现在考虑对于同一直线的点的个数，首先我们固定的是 $(0,0),(i,j)$，那么 $y=\frac{i}{j}x，0<x\le i$，我们考虑枚举分母的倍数，前提是约分完毕，即$y=\frac{\frac{i}{\gcd(i,j)}}{\frac{j}{\gcd(i,j)}}x，0<x\le i$，那么定义域上满足在整点的个数为 $\frac{i}{\frac{j}{\gcd(i,j)}}$ 即 $\gcd(i,j)$，减去本身剩下任选即 $\gcd(i,j)-1$，平移有 $(n-i)\times(m-j)$ 种情况，因此我们对于每个点要减去的就是 $(n-i)\times(m-j)\times (\gcd(i,j)-1)$。

不过有个神奇的推式子法，$O(n)$ 做，是莫反。

链接

[SHOI2015] 超能粒子炮·改

求

$$\sum_{i=0}^k\binom{n}{i}\pmod{2333}$$

$10^5$ 次询问，$n,k\le 10^{18}$，$2333$ 是素数。

跟据 $Lucas$ 定理。

$$\binom{n}{m}\mod p=\binom{\frac{n}{p}}{\frac{m}{p}}\times \binom{n\mod p}{m \mod p}$$

设 $f_{n,k}=\sum_{i=0}^k\binom{n}{i}$。

$$f_{n,k}= \sum_{i=0}^k\binom{n}{i} \\ =\sum_{i=0}^k\binom{\frac{n}{p}}{\frac{i}{p}}\times \binom{n\mod p}{i \mod p}$$

因此我们可以发现这就是一个类似于整除分块的东西。

$$\binom{\frac{n}{p}}{0}\sum_{i=0}^{p-1}\binom{n \mod p}{i}+\dotsb+\binom{\frac{n}{p}}{\frac{k}{p}}\sum_{i=0}^{k\mod p}\binom{n \mod p}{i}$$

显然后面形式完整，先略去最后一项。

即

$$\sum_{i=0}^{p-1}\binom{n \mod p}{i}\sum_{j=0}^{\frac{k}{p}-1}\binom{\frac{n}{p}}{j}$$

代入 $f$ 即 $f_{n \mod p,p-1}\times f_{\frac{n}{p},\frac{k}{p}-1}$

在加上最后一项，完毕。

$$ans=f_{n \mod p,p-1}\times f_{\frac{n}{p},\frac{k}{p}-1}+\binom{\frac{n}{p}}{\frac{k}{p}}f_{n\mod p,k \mod p}$$

显然可以预处理 $[0,p-1]$ 范围内的所有需要的。

$O(p^2+T\log_{2333}^2 n)$

[SCOI2010] 生成字符串

转化为非降路径计数问题模型,即可解决。

$\color{red}{切记(C(n+m,m)-C(n+m,m-1)+p)\mod p要先加在模，毕竟是模意义下}$

Natasha, Sasha and the Prefix Sums

这题跟上面得一样，只不过需要一步转化。

设 $f_i$ 表示为最大前缀和等于 $i$ 的序列数量，显然答案为 $\sum_{i=1}^ni\times f_i$，但不好求就容斥。

设 $g_i$ 表示为最大前缀和大于等于 $i$ 的序列数量，这个好求。

那么 $f_i$ 就是差分一下，$f_i=g_{i-1}-g_i$。

求 $g_i$ 有两种情况。

$$g_i=\binom{n+m}{n}i\le n-m\\ g_i=\binom{n+m}{n-i},i\ge n-m$$

其实就是求得与 $y=i$ 交的路径数量，这是好求的。

这题与上题的区别就是那题是时时刻刻满足 $n \le m$，而这题则是有出现过一次就好。

剩下的具体图，我太懒了，先放一放。

[HNOI2009] 有趣的数列

非降序列，那我们求考虑固定顺序。

结论：任意时刻偶数位个数要满足 $\le$ 奇数位个数。

此题同上题，将问题转化后成为卡特兰数模板题。

还有就是模数可能不是质数，我们需要我们转化位整数分解形式约分求解。

因为众所周知费马小定理求逆元适用于模数为素数，扩展欧几里得适用于 $\gcd(a,p)=1$。

除分解质因数还可以通过求 $1-n$ 阶乘种素数个数来求解。

例如，对于素数 $p$，$1-n$ 中有 $\frac{n}{p}+\frac{n}{p^2}+\frac{n}{p^k},0< k <\log_pn$。

[JLOI2016] 成绩比较

这题绝对是好题，是道基础容斥题。

前置拉格朗日差值。

求恰好被碾压的人数为 $k$ 显然不好求。

那么考虑容斥。

钦定 $f_i$ 为恰好有 $i$ 个人被碾压。

设 $g_i$ 为至少有 $i$ 个人被碾压。

$g$ 好求，钦定有 $i$ 个人被撵压，然后对于每一科在剩下的 $n-1-i$ 个人中选出没有被 $D$ 神碾压但是这一科比他低的 $n-r_i-i$ 个人，然后枚举 $D$ 神分数，并计算所有人可选的分数的情况的方案数。
即

$$g_i=\binom{n-1}{i}\prod_{j=1}^m\Bigg(\binom{n-1-i}{n-r_j-i}\sum_{k=1}^{u_j}k^{n-r_j}(u_j-k)^{r_j-1}\Bigg)$$

但是由于 $u$ 太大，我们考虑求和变幻。

$$\begin{aligned} S&=\sum_{k=1}^{u_i}k^{n-r_j}(u_j-k)^{r_j-1}\\ &=\sum_{k=1}^{u_i}k^{n-r_j}\sum_{l=0}^{r_j-1}\binom{r_j-1}{l}u_j^{r_j-1-l}(-k)^l\\ &=\sum_{l=0}^{r_j-1}\binom{r_j-1}{l}u_j^{r_j-1-l}(-1)^l\sum_{k=1}^{u_i}k^{n-r_j+l} \end{aligned}$$

$$\sum_{k=1}^{u_i}k^{n-r_j+l}$$

该式是一个 $n-r_j+l+1$ 次多项式，可以使用拉格朗日差值 $O(n)$ 求解。

具体证明看上方链接。

那么答案为 $f_k=\sum_{i=k}^{n-1}(-1)^{i-k}\binom{i}{k}g_i$。

复杂度 $O(nm^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#include<iostream>
using namespace std;
const int N=108;
const int mod=1e9+7;
int fac[N+1],inv[N+1];
int pre[N],suf[N];
int n,m,K;
int u[N],r[N];
int f,g[N];
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}
void init(int n){
    inv[1]=fac[1]=inv[0]=fac[0]=1;
    for(int i=2;i<=n;i++){
        fac[i]=1ll*fac[i-1]*i%mod;
    }
    inv[n]=qmi(fac[n],mod-2);
    for(int i=n-1;i>1;i--){
        inv[i]=1ll*inv[i+1]*(i+1)%mod;
    }
}
int C(int n,int m){
    return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int calc(int n,int k){
    pre[0]=1;
    suf[k+3]=1;
    for(int i=1;i<=k+2;i++){
        pre[i]=1ll*pre[i-1]*(n-i)%mod;
    }
    for(int i=k+2;i>=1;i--){
        suf[i]=1ll*suf[i+1]*(n-i)%mod;
    }
    int ans=0;
    int y=0;
    for(int i=1;i<=k+2;i++){
        y=(y+qmi(i,k))%mod;
        int res1=1ll*pre[i-1]*suf[i+1]%mod;
        int res2=1ll*fac[i-1]*fac[k+2-i]%mod*(((k+2-i)&1)?-1:1)%mod;
        ans=(ans+1ll*y*res1%mod*qmi(res2,mod-2)%mod)%mod;
    }
    return (ans+mod)%mod;
}
int lagrange[N][N];
int main(){
    cin>>n>>m>>K;
    for(int i=1;i<=m;i++){
        cin>>u[i];
    }
    for(int i=1;i<=m;i++){
        cin>>r[i];
    }
    init(n+2);
    for(int j=1;j<=m;j++){
        for(int l=0;l<=r[j]-1;l++){
            lagrange[j][l]=calc(u[j],n-r[j]+l);
        }
    }
    for(int i=1;i<=n-1;i++){
        int res1=1;
        for(int j=1;j<=m;j++){
            int res2=0;
            for(int l=0;l<=r[j]-1;l++){
                res2=(res2+1ll*C(r[j]-1,l)*qmi(u[j],r[j]-1-l)%mod*((l&1)?-1:1)%mod*lagrange[j][l]%mod)%mod;
            }
            res2=1ll*res2*C(n-1-i,n-r[j]-i)%mod;
            res1=1ll*res2*res1%mod;
        }
        g[i]=1ll*C(n-1,i)*res1%mod;
    }
    for(int i=K;i<=n-1;i++){
        f=(f+1ll*(((i-K)&1)?-1:1)*C(i,K)%mod*g[i]%mod)%mod;
    }
    cout<<(f+mod)%mod<<endl;
    return 0;
}

对于球相同，盒不同，考虑不定方程计数模型，仅关心每个盒子分配的个体数量。

问题分解是分步还是分类

分步处理，要考虑选取顺序问题

在计数问题，特别区分选取是否有序

一下是一些简单题。

$m1,n0 ,m\le n$，每个 $1$ 后面至少有 $1$ 个 $0$ 方案数。

• 先放 $n$ 个 $0$ 只有一种方法，然后在 $0$ 之间 $n$ 个位置（除末尾）随便放 $m$ 个 $1$，$ans=\binom{n}{m}$。

• $10$ 看成整体 ，看成 $m$ 个隔板，$m+1$ 空，相当于

$$x_1+x_2+\dots +x_m+1=n-m$$

求解非负整数解个数 $\binom{n-m+m+1-1}{n-m}$。

$3$ 蓝球，$2$ 红球，$2$ 黄球，满足黄球不相邻的方案数。

解：

令 $S=\{3b,2r,2y\}$ ，该方案数为 $\frac{7!}{3!2!2!}$。

这是不考虑相不相邻，若相邻就是把两个黄球看成一个整体 $S=\{3b,2r,1y\}$，该方案数为 $\frac{6!}{3!2!}$。

相减就是答案。

$S=\{1a_1,1a_2,\dots, \infty a_{t+1},\dots,\infty a_{k} \}$，求其的 $r$ 组合数。

分成两集合处理。

$$\sum_{i=0}^r\binom{t}{i}\binom{k-t+r-i-1}{r-i}$$

$S=\{\infty 0,\infty 1,\infty 2 \}$ 种取 $n$ 个数，不允许相邻的两位置相同，问排列数？

固定住一个位置，剩下唯一。

$3\times 2^{n-1}$

容斥

多重集的组合数

考虑这个问题：设 $S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k,\}$ 表示由 $n_1$ 个 $a_1$，$n_2$ 个 $a_2$，…，$n_k$ 个 $a_k$ 组成的多重集。那么对于正整数 $r$，从 $S$ 中选择 $r$ 个元素组成一个多重集的方案数。

这样就限制了每种元素的取的个数。同样的，我们可以把这个问题转化为带限制的线性方程求解：

$$\forall i\in [1,k],\ x_i\le n_i,\ \sum_{i=1}^kx_i=r$$

于是很自然地想到了容斥原理。容斥的模型如下：

1. 全集：$\displaystyle \sum_{i=1}^kx_i=r$ 的非负整数解。
2. 属性：$x_i\le n_i$。

于是设满足属性 $i$ 的集合是 $S_i$，$\overline{S_i}$ 表示不满足属性 $i$ 的集合，即满足 $x_i\ge n_i+1$ 的集合（转化为上面插板法的问题三）。那么答案即为

$$\left|\bigcap_{i=1}^kS_i\right|=|U|-\left|\bigcup_{i=1}^k\overline{S_i}\right|$$

根据容斥原理，有：

$$\begin{aligned} \left|\bigcup_{i=1}^k\overline{S_i}\right| =&\sum_i\left|\overline{S_i}\right| -\sum_{i,j}\left|\overline{S_i}\cap\overline{S_j}\right| +\sum_{i,j,k}\left|\overline{S_i}\cap\overline{S_j}\cap\overline{S_k}\right| -\cdots\\ &+(-1)^{k-1}\left|\bigcap_{i=1}^k\overline{S_i}\right|\\ =&\sum_i\binom{k+r-n_i-2}{k-1} -\sum_{i,j}\binom{k+r-n_i-n_j-3}{k-1}+\sum_{i,j,k}\binom{k+r-n_i-n_j-n_k-4}{k-1} -\cdots\\ &+(-1)^{k-1}\binom{k+r-\sum_{i=1}^kn_i-k-1}{k-1} \end{aligned}$$

拿全集 $\displaystyle |U|=\binom{k+r-1}{k-1}$ 减去上式，得到多重集的组合数

$$Ans=\sum_{p=0}^k(-1)^p\sum_{A}\binom{k+r-1-\sum_{A} n_{A_i}-p}{k-1}$$

其中 A 是充当枚举子集的作用，满足 $|A|=p,\ A_i<A_{i+1}$。

Devu and Flowers

至于像这种容斥我们就应该考虑集合的所有子集去统计答案。

__END__