组合技巧

加法原理

乘法原理

1到10，选3个数字，可以重复
顺序不一样认为是不同方案 (1,2,3和3,2,1认为是不同的方案)
问有多少个方案
10 * 10 * 10 = 10^3 = 1000

有3个变量 x1 x2 x3
1 <= x1 <= 10
1 <= x2 <= 10
1 <= x3 <= 10
问 x1 x2 x3 有多少组解
（乘法原理）

排列数

1到10，选3个数字，不可以重复
顺序不一样认为是不同方案 (1,2,3和3,2,1认为是不同的方案)
问有多少个方案
10 * 9 * 8 = 720
P(10, 3)
（排列）

组合数

1到10，选3个数字，不可以重复
顺序不一样认为是相同的方案 (1,2,3和3,2,1认为是相同的方案)
（顺序不一样认为是相同的方案等价于要求不下降）
问有多少个方案
10 * 9 * 8 / 3 / 2 / 1 = 120
C(10, 3)

有3个变量 x1 x2 x3
1 <= x1 < x2 < x3 <= 10
问 x1 x2 x3 有多少组解，（等价于从1到10中选3个数字，赋值给x1 x2 x3）
（组合）

1到10，选3个数字，可以重复
顺序不一样认为是相同的方案 (1,2,3和3,2,1认为是相同的方案)
（顺序不一样认为是相同的方案等价于要求不下降）
问有多少个方案
10 * 11 * 12 / 3 / 2 / 1 = 220
C(10 + 3 - 1, 3)

有3个变量 x1 x2 x3
1 <= x1 <= x2 <= x3 <= 10
问 x1 x2 x3 有多少组解

设
y1 = x1
y2 = x2 + 1
y3 = x3 + 2

1 <= y1 < y2 < y3 <= 12
(转化为了上一个不能相等的问题)
（组合）

x1 <= x2 可以看作是 x1 < x2 + 1

数两次

交换求和符号

https://www.luogu.com.cn/problem/P1403
$\sum_{i=1}^n \sum_{j=1}^i [i \bmod j = 0]$

$\sum_{i=1}^n \sum_{j=1}^n [i \bmod j = 0]$

$\sum_{j=1}^n \sum_{i=1}^n [i \bmod j = 0]$

$\sum_{j=1}^n \lfloor n / j \rfloor$

进一步优化可以用除法分块
$n / j$ 商相同的 $j$ 一定是连续一段
连续一段一起处理

参考题目

P6146 [USACO20FEB]Help Yourself G

https://www.luogu.com.cn/problem/P6146

题目描述

在一个数轴上有 $N$ 条线段，第 $i$ 条线段覆盖了从 $l_i$ 到 $r_i$ 的所有实数（包含 $l_i$ 和 $r_i$ ）。

定义若干条线段的并为一个包含了所有被至少一个线段覆盖的点的集合。

定义若干条线段的复杂度为这些线段的并形成的连通块的数目。

现在 Bessie 想要求出给定 $N$ 条线段的所有子集（共有 $2^N$ 个）的复杂度之和对 $10^9+7$ 取模的结果。

你也许猜到了，你需要帮 Bessie 解决这个问题。但不幸的是，你猜错了！在这道题中你就是 Bessie，而且没有人来帮助你。一切就靠你自己了！

输入格式

第一行一个整数 $N$ （ $1 \leq N \leq 10^5$ ）。

接下来 $N$ 行，每行两个整数 $l_i,r_i$ ，描述一条线段。保证 $1 \leq l_i \lt r_i \leq 2N$ ，且任意两个端点都不在同一位置上。

输出格式

输出所求答案对 $10^9+7$ 取模的结果。

样例 #1

样例输入 #1

样例输出 #1

提示

样例解释

所有非空子集的复杂度如下所示（显然空集的复杂度为零）：
$\{[1,6]\} \implies 1, \{[2,3]\} \implies 1, \{[4,5]\} \implies 1$

$\{[1,6],[2,3]\} \implies 1, \{[1,6],[4,5]\} \implies 1, \{[2,3],[4,5]\} \implies 2$

$\{[1,6],[2,3],[4,5]\} \implies 1$

故答案为 $1+1+1+1+1+2+1=8$ 。

子任务

测试点 $2 \sim 3$ 满足 $N \leq 16$ ；
测试点 $4 \sim 7$ 满足 $N \leq 1000$ ；
测试点 $8 \sim 12$ 没有特殊限制。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int n, x, y, z, c;
int a[200020];
int b[200020];
int main()
{
	scanf("%d", &n);
	for (int i = b[0] = 1; i <= n; i++)
	{
		b[i] = b[i - 1] * 2 % mod;
	}
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &x, &y);
		a[x] = +1;
		a[y] = -1;
	}
	for (int i = 1; i <= 2*n; i++)
	{
		c += a[i];
		if (a[i] == 1)
		{
			z = (z + b[n - c]) % mod;
		}
	}
	printf("%d\n", z);
	return 0;
}

题解

http://www.usaco.org/index.php?page=viewproblem2&cpid=1018
c[i] is the number of segments cover the left endpoint of the i-th segment.
the i-th segment increases the answer by 2 ** (n-1-c[i])

CF1195D2 Submarine in the Rybinsk Sea (hard edition)