题目

构造一个长度为 $n$ 的序列，每个数字大小必须满足 $l <= a[i] <= r$，且和被 3 整除，问有多少种方法？

Solution

题目

求 $n$ 个节点，高度不超过 $h$ 的二叉树的个数，结果模 $1e9 + 7$。

Solution

题意

给定一个长度为 $n$ 的数组，求长度为 $n-m$ 的不同子序列个数。（$1<=n<=1e5, m<=10$）

Solution

$dp[i][j]$ 表示长度为 $i$，删除 $j$ 个元素的子序列个数，不考虑重复的话，有 $dp[i][j] = dp[i-1][j] + dp[i-1][j-1]$（即已经删除了 $j$ 个和已经删除了 $j-1$ 个再删除这一个的情况）。

题意

给定一个由n个元素组成的序列 { a₁, a₂, a₃,…, a_n } ，她想知道其中有多少个子序列 { a_p1, a_p2, …, a_pm } $(1 ≤ m ≤ n, 1 ≤ p1 < p2 ,…, < pm ≤ n)$，满足对于所有的 $i, j$ $(1 ≤ i < j ≤ m)$, a_pi^pj < a_pj^pi成立。

Solution1

py + dp直接冲。

题意

给定一个长度为 $n$ 的字符串，求不同的子序列个数。

Solution

很经典的一道计数dp。我们用 $dp[i]$ 表示以前 $i$ 个字符中的不同子序列个数：