countdp

P2602, P2606, P3746, P3914, P4827, P6006, P6009, P6075, P6146, P6144

P6075 [JSOI2015]子集选取

n=1    x
n=2    x**2
n=3    x**3
n      x**n

k=2    4**n

P2606 [ZJOI2010]排列计数

有根树的拓扑序列的数量

n! / 每一个子树的大小

f[x] = f[2 * x] * f[2 * x + 1] * (s[x]! / s[x] / s[2 * x]! / s[2 * x + 1]!)

p <= 1e9
n <= 1e9
输入 n ，输出 n! % p
没有特别简单的做法

分块打表，打表，每隔 1000000 打一个数字

f[i][j]

从i节点到i子树中的某个节点，路径长度%3 == j的方案数。

有f[x][0]个0
有f[x][1]个1
有f[x][2]个2
从中选取2个数字，和为0的方案数是多少？
（减去选的2个数字在同一个子树的情况）

P3914 染色计数
f[i][j]
子树i的情况，点i染成了颜色j，的方案数

g[i] 子树i的情况，所有染色方案之和

枚举i的孩子x，
f[i][j] *= sum(k != j, f[x][k])
显然不能枚举求和
f[i][j] *= sum(f[x][k]) - f[x][j]

P3478 [POI2008]STA-Station 一次方的特殊情况
P4827 [国家集训队] Crash 的文明世界
spoj TREESUM
hdu 4625 JZPTREE

S是距离的集合

已知
a0 = S中所有数字0次方的和
a1 = S中所有数字1次方的和
a2 = S中所有数字2次方的和
...
ak = S中所有数字k次方的和

b0 = S中所有数字+1之后0次方的和
b1 = S中所有数字+1之后1次方的和
b2 = S中所有数字+1之后2次方的和
...
bk = S中所有数字+1之后k次方的和

b0 = a0
b1 = a1 + a0
b2 = a2 + 2 a1 + a0
b3 = a3 + 3 a2 + 3 a1 + a0

bk = C(k,k) ak + C(k,k-1) a(k-1) + ... + C(k,0) a0

O(n k^2)

已知
a0 = S中所有数字x C(x, 0)的和
a1 = S中所有数字x C(x, 1)的和
a2 = S中所有数字x C(x, 2)的和
...
ak = S中所有数字x C(x, k)的和

b0 = S中所有数字x C(x+1, 0)的和
b1 = S中所有数字x C(x+1, 1)的和
b2 = S中所有数字x C(x+1, 2)的和
...
bk = S中所有数字x C(x+1, k)的和

b0 = a0
b1 = a1 + a0
b2 = a2 + a1
b3 = a3 + a2

bk = ak + a(k-1)

对于每个点x，求的是所有距离d C(d, 0..k) 并不是 d**k

第二类Stirling数
S(k, j) 把k个不同元素分成j个非空集合的方案数

x**k = sum(1 <= j <= k, S(k, j) * j! * C(x, j))
左边是 k 个不同球，放入 x 个不同的盒子的方案数
右边换一种方法数
假设放入之后，有j个盒子有球
首先 k 个不同的球分成 j 组 S(k, j)
从 x 个盒子中选出 j 个盒子 C(x, j)
把分成的 j 组和 j 个盒子配对 j!

P4187 [USACO18JAN]Stamp Painting G

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

题目描述

Bessie has found herself in possession of an $N$ -unit long strip of canvas ( $1 \leq N \leq 10^6$ ), and she intends to paint it. However, she has been unable to acquire paint brushes. In their place she has $M$ rubber stamps of different colors ( $1 \leq M \leq 10^6$ ), each stamp $K$ units wide ( $1 \leq K \leq 10^6$ ). Astounded by the possibilities that lie before her, she wishes to know exactly how many different paintings she could conceivably create, by stamping her stamps in some order on the canvas.

To use a stamp, it must first be aligned with exactly $K$ neighboring units on the canvas. The stamp cannot extend beyond the ends of the canvas, nor can it cover fractions of units. Once placed, the stamp paints the $K$ covered units with its color. Any given stamp may be used multiple times, once, or even never at all. But by the time Bessie is finished, every unit of canvas must have been painted at least once.

Help Bessie find the number of different paintings that she could paint, modulo $10^9 + 7$ . Two paintings that look identical but were painted by different sequences of stamping operations are counted as the same.

For at least 75% of the input cases, $N,K \leq 10^3$ .

输入格式

The first and only line of input has three integers, $N$ , $M$ , and $K$ . It is guaranteed that $K \leq N$ .

输出格式

A single integer: the number of possible paintings, modulo $10^9 + 7$ .

样例 #1

样例输入 #1

3 2 2

样例输出 #1

提示

If the two stamps have colors A and B, the possible paintings are AAA, AAB, ABB, BAA, BBA, and BBB.

参考代码

#include <bits/stdc++.h>
using namespace std;
const int p = 1000000007;
int n, m, k;
long long f[1000020], ans;
int main()
{
	cin >> n >> m >> k;
	f[0] = 1;
	ans = 1;
	for (int i = 1; i <= n; i++)
	{
		f[i] = f[i - 1] * m % p;
		if (i == k)
		{
			f[i] -= m;
		}
		else if (i > k)
		{
			f[i] = (f[i] - f[i - k] * (m - 1) % p + p) % p;
		}
		ans = ans * m % p;
	}
	cout << (ans + p - f[n]) % p << endl;
}

题解

P4909 [USACO06MAR]Ski Lift G

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

题目描述

科罗拉多州的山脉是二维平面上的一条折线。这条折线由 $N$ 个端点， $N-1$ 段线段组成，第 $i$ 个端点的横坐标就是 $i$ ，纵坐标是 $H_i$ ，纵坐标代表高度，也可以称为海拔。

罗恩打算为奶牛建造一个滑雪场，为此要在山脉上规划一条缆车线路。缆线也是一条折线，由若干段缆绳组成，起点在山脉的第一个端点，终点在最后一个端点。每段缆绳可以贴着山脉的轮廓，也可以悬浮于空中，跳过山脉上几个海拔低的端点。每段缆绳的水平跨度有限制，不能超过给定的整数 $K$ 。罗恩需要在每段缆绳的端点处修建支柱，用来固定缆绳。

请帮助他规划一下，选择在山脉的哪些端点上修建，才能使得支柱数量最少？注意，根据题意，起点和终点上是一定要修建的。

输入格式

第一行：两个整数 $N$ 和 $K$ 。

第二行到第 $N + 1$ 行，第 $i+1$ 行有一个整数 $H_i$ 。

输出格式

一行一个整数表示最少需要修建的支柱数量。

样例 #1

样例输入 #1

样例输出 #1

提示

解释最优方案是把支柱设在 $1,5,7,9,13$ 。 $5$ 不能直接连 $9$ ，因为 $9$ 的海拔较高， $1$ 不能直接连 $7$ ，因为跨度超过了 $K$ 。

数据范围

$2 \le N \le 5000$ ， $1 \le K \le N - 1$ ， $0\le H_i \le 10^9$ 。

参考代码

题解

P5853 [USACO19DEC]Tree Depth P

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

题目背景

For the new year, Farmer John decided to give his cows a festive binary search tree
(BST)!

To generate the BST, FJ starts with a permutation $a=\{a_1,a_2,\ldots,a_N\}$
of the integers $1\ldots N$ , where $N\le 300$ . He then runs the following
pseudocode with arguments $1$ and $N.$

generate(l,r):
  if l > r, return empty subtree;
  x = argmin_{l <= i <= r} a_i; // index of min a_i in {a_l,...,a_r}
  return a BST with x as the root, 
    generate(l,x-1) as the left subtree,
    generate(x+1,r) as the right subtree;

For example, the permutation $\{3,2,5,1,4\}$ generates the following BST:

Let $d_i(a)$ denote the depth of node $i$ in the tree corresponding to $a,$
meaning the number of nodes on the path from $a_i$ to the root. In the above
example, $d_4(a)=1, d_2(a)=d_5(a)=2,$ and $d_1(a)=d_3(a)=3.$

The number of inversions of $a$ is equal to the number of pairs of integers
$(i,j)$ such that $1\le i<j\le N$ and $a_i>a_j.$ The cows know that the $a$ that
FJ will use to generate the BST has exactly $K$ inversions
$(0\le K\le \frac{N(N-1)}{2})$ . Over all $a$ satisfying this condition, compute
the remainder when $\sum_ad_i(a)$ is divided by $M$ for each $1\le i\le N.$

题目描述

为了迎接新年，Farmer John 决定给他的奶牛们一个节日二叉搜索树！

为了生成这个二叉搜索树，Farmer John 从一个 $1 \dots N$ 的排列 $a= \{1,2, \dots ,N\}$ 开始，然后以参数 $l$ 和 $r$ 开始运行如下的伪代码：

generate(l,r):
  if l > r, return empty subtree;
  x = argmin_{l <= i <= r} a_i; // index of min a_i in {a_l,...,a_r}
  return a BST with x as the root, 
    generate(l,x-1) as the left subtree,
    generate(x+1,r) as the right subtree;

例如，排列 $\{ 3,2,5,1,4 \}$ 将产生如下的二叉搜索树：

令 $d_i(a)$ 表示节点 $i$ 在用排列 $a$ 生成的二叉搜索树中的深度。深度定义为这个节点到根节点的路径上的点数。在上述例子中， $d_4(a)=1,d_2(a)=d_5(a)=2,d_1(a)=d_3(a)=3$ 。

$a$ 中的逆序对数等于满足 $1 \le i<j \le N$ 且 $a_i>a_j$ 的数对 $(i,j)$ 的个数。奶牛们知道 Farmer John 用来生成二叉搜索树的排列 $a$ 中恰好有 $K$ 个逆序对。对于所有满足条件的 $a$ ，请计算对于每个 $1 \le i \le N$ ， $\sum_a d_i(a)$ 对 $M$ 取模后的结果。

输入格式

输入只有一行，包含三个整数 $N,K,M$ 。

输出格式

输出一行 $N$ 个整数，第 $i$ 个整数表示 $\sum_a d_i(a) \bmod M$ 。两个整数之间用一个空格隔开。

样例 #1

样例输入 #1

3 0 192603497

样例输出 #1

1 2 3

样例 #2

样例输入 #2

3 1 144408983

样例输出 #2

3 4 4

提示

样例解释 1

对于这个样例，唯一满足条件的排列为 $a=\{1,2,3\}$ 。

样例解释 2

对于这个样例，满足条件的两个排列分别为 $a=\{1,3,2\}$ 和 $a=\{2,1,3\}$ 。

数据范围

对于全部数据， $1\le N\le 300$ ， $0\le K\le \frac{N(N-1)}{2}$ ，保证 $M$ 是一个 $\left[ 10^8,10^9+9 \right]$ 范围中的质数。

对于测试点 $3,4$ ，满足 $N \le 8$ ；

对于测试点 $5-7$ ，满足 $N \le 20$ ；

对于测试点 $8-10$ ，满足 $N \le 50$ 。

USACO 2019 December 铂金组T3

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, l, mod;
int a[45000] = {1};
int z[300];
void mul(int b)
{
	for (int i = 1; i < l; i++)
	{
		a[i] = (a[i] + a[i - 1]) % mod;
	}
	for (int i = l - 1; i >= b; i--)
	{
		a[i] = (a[i] + mod - a[i - b]) % mod;
	}
}
void div(int b)
{
	for (int i = b; i < l; i++)
	{
		a[i] = (a[i] + a[i - b]) % mod;
	}
	for (int i = l - 1; i > 0; i--)
	{
		a[i] = (a[i] + mod - a[i - 1]) % mod;
	}
}
int main()
{
	cin >> n >> m >> mod;
	l = n * (n - 1) / 2;
	for (int i = 1; i <= n; i++)
	{
		mul(i);
	}
	for (int j = 1; j < n; j++)
	{
		div(j + 1);
		for (int i = 0; i < n - j; i++)
		{
			z[i] = (z[i] + a[n * (n - 1) / 2 - m]) % mod;
			z[i + j] = (z[i + j] + a[m]) % mod;
		}
		mul(j + 1);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d%c", (z[i] + a[m]) % mod, i == n - 1 ? '\n' : ' ');
	}
	return 0;
}

题解

笛卡尔树

P6280 [USACO20OPEN]Exercise G

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

题目描述

Farmer John（又）想到了一个新的奶牛晨练方案！
如同之前，Farmer John 的 $N$ 头奶牛站成一排。对于 $1\le i\le N$ 的每一个 $i$ ，从左往右第 $i$ 头奶牛的编号为 $i$ 。他告诉她们重复以下步骤，直到奶牛们与她们开始时的顺序相同。

给定长为 $N$ 的一个排列 $A$ ，奶牛们改变她们的顺序，使得在改变之前从左往右第 $i$ 头奶牛在改变之后为从左往右第 $A_i$ 头。
例如，如果 $A=(1,2,3,4,5)$ ，那么奶牛们总共进行一步。如果 $A=(2,3,1,5,4)$ ，那么奶牛们总共进行六步。每步之后奶牛们从左往右的顺序如下：

0 步： $(1,2,3,4,5)$
1 步： $(3,1,2,5,4)$
2 步： $(2,3,1,4,5)$
3 步： $(1,2,3,5,4)$
4 步： $(3,1,2,4,5)$
5 步： $(2,3,1,5,4)$
6 步： $(1,2,3,4,5)$
求所有正整数 $K$ 的和，使得存在一个长为 $N$ 的排列，奶牛们需要进行恰好 $K$ 步。

由于这个数字可能非常大，输出答案模 $M$ 的余数（ $10^8\le M\le 10^9+7$ ， $M$ 是质数）。

输入格式

输入的第一行包含 $N$ 和 $M$ 。

输出格式

输出一个整数。

样例 #1

样例输入 #1

5 1000000007

样例输出 #1

提示

样例解释：

存在排列使得奶牛需要进行 $1$ 、 $2$ 、 $3$ 、 $4$ 、 $5$ 以及 $6$ 步。因此，答案为 $1+2+3+4+5+6=21$ 。

对于 $100\%$ 的数据， $1\le N\le 10^4$ 。

共 $10$ 个测试点，其中 $1$ 为样例，其余性质如下：

测试点 $2\sim 5$ 满足 $N\le 10^2$ 。
测试点 $6\sim 10$ 没有额外限制。

出题人：Benjamin Qi

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, mod;
int p[10020], pc;
int isPrime(int x)
{
	if (x < 2)
	{
		return false;
	}
	for (int i = 2; i * i <= x; i++)
	{
		if (x % i == 0)
		{
			return false;
		}
	}
	return true;
}
ll f[10020];
int main()
{
	cin >> n >> mod;
	for (int i = 1; i <= n; i++)
	{
		if (isPrime(i))
		{
			p[pc++] = i;
		}
	}
	for (int i = 0; i <= n; i++)
	{
		f[i] = 1;
	}
	for (int i = 0; i < pc; i++)
	{
		for (int j = n; j > 0; j--)
		{
			for (int k = p[i]; k <= j; k *= p[i])
			{
				f[j] = (f[j] + f[j - k] * k) % mod;
			}
		}
	}
	printf("%lld\n", f[n]);
	return 0;
}

题解

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])