将 $n_1$ 个 $A$，$n_2$ 个 $B$，$n_3$ 个 $C$，$n_4$ 个 $D$ 排成一个序列。求问有多少种排列方案使得排成的序列任意相邻的两个字母不同。

兔子们在玩字符串的游戏。首先，它们拿出了一个字符串集合S，然后它们定义一个字
符串为“好”的，当且仅当它可以被分成非空的两段，其中每一段都是字符串集合S中某个字符串的前缀。
比如对于字符串集合 {“abc”,”bca”}，字符串 “abb”，”abab”是“好”的（”abb”=”ab”+”b”,abab=”ab”+”ab”），而字符串“bc”不是“好”的。

兔子们想知道，一共有多少不同的“好”的字符串。

给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。

对于一个非空集合{$a_i$},我们称一个集合是 $magical$ 的,当且仅当它满足以下两个条件。

1:$a_1$ & $a_2$ &…& $a_n$ =0(&表示 $and$)

2:{$a_i$} 的任意一个除它本身外的非空子集不满足1。

小 $A$ 有一个很大很大的集合。很显然这个集合的子集数量是一个天文数字。

小 $A$ 现在想要知道这个集合的 magical 的非空子集数量是多少。

为了防止不必要的麻烦,请将答案 $mod$ $1e9+7$ 后输出。

组合数表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1, 2, 3) $ 三个物品中选择两个物品可以有 $(1, 2)$， $(1, 3)$， $(2, 3)$ 这三种选择方法。
根据组合数的定义，我们可以给出计算组合数的一般公式：
$C_n ^ m = \frac{n!}{m!(n - m)!}$
其中 $n! = 1 \times 2 \times \cdots \times n$。
小葱想知道如果给定 $n$， $m$ 和 $k$，对于所有的 $0 \leq i \leq n$， $0 \leq j \leq \min(i, m)$ 有多少对 $(i, j)$ 满足是 $k$ 的倍数。

数位dp模板，记忆化搜索，dp[pos][pre][status]。
以不要62【hdu】为例

计算数字

题目描述

当连续写下从十进制整数 1 开始到某个整数 N 之间的所有整数时，能得到如下的数字序列：
12345678910111213141516171819202122 \cdots \cdots
编写一个程序，计算这个序列中的数字个数。

输入格式

输入的第一行且是唯一的一行包含：一个整数 N，1 \leq N \leq 100,000,000。

输出格式

输出的第一行且是唯一的一行应包含：由给定的整数所产生的序列的数字个数。

老旧的机器

题目描述

伟大的工程师阿克蒙德买了一台机器，为了维持这台机器的正常运作，他每年必须花费一定的费用来维修这台机器。但是随着这台机器的使用，机器会损坏更快以至于每年用来维修这台机器的费用都是上一年的 1.5 倍。已知第一年仅需花费 1 元。现在阿克蒙德想知道，如果他想用 n 年，他总共需要花费多少钱来维修这台机器。

没有上司的晚会

题目背景

poj2342

题目描述

Ural 大学有N 个职员，编号为 1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。

输入格式

第一行一个整数 N (1<=N<=6000)。
接下来 N 行，第i+1行表示i 号职员的快乐指数Ri(-128<=Ri<=127) 。
接下来 N-1 行，每行输入一对整数 L 和 K。表示 K 是 L 的直接上司
最后一行输入0 0。

输出格式

输出最大的快乐指数。

麻烦的聚餐

题目描述

为了避免餐厅过分拥挤，FJ要求奶牛们分3批就餐。每天晚饭前，奶牛们都会在餐厅前排队入内，按FJ的设想，所有第3批就餐的奶牛排在队尾，队伍的前端由设定为第1批就餐的奶牛占据，中间的位置就归第2批就餐的奶牛了。由于奶牛们不理解FJ的安排，晚饭前的排队成了一个大麻烦。
第i头奶牛有一张标明她用餐批次 D_i(1 <= D_i <= 3) 的卡片。虽然所有 N (1 <= N <= 30,000) 头奶牛排成了很整齐的队伍，但谁都看得出来，卡片上的号码是完全杂乱无章的。 在若干次混乱的重新排队后，FJ找到了一种简单些的方法：奶牛们不动，他沿着队伍从头到尾走一遍，把那些他认为排错队的奶牛卡片上的编号改掉，最终得到一个他想要的每个组中的奶牛都站在一起的队列，例如 111222333 或者 333222111。哦，你也发现了，FJ不反对一条前后颠倒的队列，那样他可以让所有奶牛向后转，然后按正常顺序进入餐厅。
你也晓得，FJ是个很懒的人。他想知道，如果他想达到目的，那么他最少得改多少头奶牛卡片上的编号。所有奶牛在FJ改卡片编号的时候，都不会挪位置。