tdpc 题面翻译

题解先鸽着。

一套 atcoder 的~~老少咸宜~~的 dp 题，题目比较有代表性~~（就是比较裸的意思）~~

A - コンテスト(contest)

一场比赛有 $n$ 道题，第 $i$ 道题分数为 $a_i$，你现在可以选择做一个子集的题（可以为空），得到的总分为这个子集中的题目分数之和，求总分有多少种

$1\le n\le100,1\le a_i\le100$

B - ゲーム(game)

两个数组 $a,b$，分别有 $n,m$ 项，有两个玩家轮流进行操作，每次操作玩家可以取走一个非空数组内的第一个元素，两个玩家都希望自己的得分最大，问先手的得分

$1\le n,m,a_i,b_i\le1000$

C - トーナメント(tournament)

有 $2^k$ 个人进行淘汰赛，流程如下：

第一轮 $1$ 和 $2$ 比赛，$3$ 和 $4$ 比赛，$5$ 和 $6$ 比赛，$\cdots$
第二轮 $1$ 和 $2$ 中的胜者与 $3$ 和 $4$ 中的胜者比赛，$5$ 和 $6$ 中的胜者与 $7$ 和 $8$ 中的胜者比赛，$\cdots$
第三轮 (($1$ 和 $2$ 中的胜者)与($3$ 和 $4$ 中的胜者))中的胜者与(($5$ 和 $6$ 中的胜者)与($7$ 和 $8$ 中的胜者))中的胜者比赛，$\cdots$
经过 $k$ 轮后剩下的那个人是 shengzhe

每个人有一个能力值 $r_i$，如果能力值为 $a$ 与 $b$ 的两个人比赛，则能力值为 $a$ 的人获胜的概率为 $1/(1+10^{(a-b)/400})$，求第 $i$ 个人成为 shengzhe 的概率

$1\le k\le10,0\le r_i\le4000$

D - サイコロ(dice)

将一个 $6$ 面的骰子扔 $n$ 遍，求最后所有点数的乘积是 $D$ 的倍数的概率

$1\le n\le100,1\le D\le10^{18}$

E - 数(number)

求小于 $N$ 的正整数中数字和是 $D$ 的倍数的数的个数，答案对 $10^9+7$ 取模

$1\le N\le10^{10000},1\le D\le100$

F - 準急(semiexp)

一条电车线上有 $n$ 个站点，你现在要选择一些电车停靠的站点，需要满足以下两个要求：

必须在 $1$ 和 $n$ 停靠
不能在连续的 $k$ 站都停靠

$2\le k\le n\le10^6$

G - 辞書順(lexicographical)

将小写字母串 $s$ 的所有非空子序列按字典序从小到大排序，求第 $k$ 个，如果不存在则输出 Eel

$1\le|s|\le10^6,1\le k\le10^{18}$

H - ナップザック(knapsack)

有 $n$ 个物品，第 $i$ 个物品重量为 $w_i$，价值为 $v_i$，颜色为 $c_i$，你需要选择其中的一部分物品放入背包，使得背包中的物品重量之和不超过 $W$，颜色种数不超过 $C$，求最大的价值和

$1\le n\le100,1\le W\le10000,1\le C\le50,1\le w_i,v_i\le10000,1\le c_i\le50$

I - イウィ(iwi)

给定一个只包含 i 与 w 的字符串 $s$，每次操作你可以删掉一个连续的 iwi，问最多能操作多少次。

$1 \le |s| \le 300$。

J - ボール(ball)

你现在有 $n$ 个东西，第 $i$ 个在坐标 $x_i$ 的位置。你要投球来砸中这 $n$ 个东西，如果你尝试向坐标为 $x$ 的地方投球，那么会等概率砸中 $x-1, x, x+1$ 中的一个位置。求在最佳策略下（你可以根据之前的落球点来进行决策），将所有东西都砸到的期望最小投球次数。

$1 \le n \le 16, 0 \le x_i \le 15$。$x_i$ 互不相同。

K - ターゲット(target)

若圆 $C_1, C_2, \cdots, C_k$ 满足对于所有在 $[1, k - 1]$ 中的 $i$，圆 $C_i$ strictly 包含 $C_{i+1}$，则称它们是一个大小为 $k$ 的 target。给定 $n$ 个圆，第 $i$ 个圆圆心为 $(x_i,0)$，半径为 $r_i$，请选出一个子集，求能组成的最大 target 的大小。

$1\le n\le10^5,0\le x_i\le10^9,1\le r_i\le10^9$。

L - 猫(cat)

你现在有 $n$ 只猫，猫 $i$ 和猫 $j$ 的相配度是 $f_{i, j}$。一个猫的幸福度是跟它距离 $1$ 以内的猫跟它的相配度的和。你现在要把猫 $1$ 到猫 $n$ 在数轴上排列，若 $i$ 只猫的坐标为 $x_i$（$x_i$ 不一定为整数），则需要满足 $x_1<x_2<\cdots<x_n$，求最大的幸福值总和

$1\le n\le1000,|f_{i,j}|\le1000,f_{i,i}=0,f_{i,j}=f_{j,i}$

M - 家(house)

有一个 $H$ 层的房子，每层的构造都一样，有 $R$ 个房间，任意一层的第 $i$ 个房间与第 $j$ 个房间有双向通路当且仅当 $g_{i,j}=1$，每一个房间都有向下的楼梯，楼梯只能下不能上，求你从 $H$ 层的第 $1$ 个房间到达 $1$ 层的第 $1$ 个房间且不经过重复房间的方案数，答案对 $10^9+7$ 取模

$2\le H\le10^9,1\le R\le16,0\le g_{i,j}\le1,g_{i,i}=0,g_{i,j}=g_{j,i}$

N - 木(tree)

你要将一棵 $n$ 个节点的树描在纸上，第 $i$ 条边连接第 $a_i$ 个点与第 $b_i$ 个点，起初所有边没有被描出，你需要依次描出这些边，使得任何时刻所有已经描出的边都在一个连通块内，求有多少种合法的描边顺序，对 $10^9+7$ 取模

$2\le n\le1000,1\le a_i,b_i\le n$

O - 文字列(string)

~~经典咏流传~~

求满足以下条件的字符串个数，答案对 $10^9+7$ 取模：

a 恰好出现了 $freq_1$ 次，b 恰好出现了 $freq_2$ 次，$\cdots$，z 恰好出现了 $freq_{26}$ 次，且不包含其他字符
相邻的字符不能相同

$0\le freq_i\le10$，至少有一个 $freq_i$ 大于 $0$

P - うなぎ(eel)

有一棵 $n$ 个节点的树，求有多少选出 $k$ 条没有公共点的路径的方案（交换顺序算作相同），答案对 $10^9+7$ 取模

$2\le n\le1000,1\le k\le50$

Q - 連結(concatenation)

有 $n$ 个 $01$ 串 $w_1,w_2,\cdots,w_n$，你需要从中选择一些字符串并拼接成一个新的字符串（同一个字符串可以选择多次），问你总共能拼出多少本质不同的长度为 $L$ 的 $01$ 串（字符串相同但分法不同也算作一种）

$1\le n\le510,1\le|w_i|\le8,\le L\le100$，$w_i$ 互不相同

R - グラフ(graph)

一张 $n$ 个点的有向图，$g_{i,j}=1$ 表示 $i$ 到 $j$ 有一条有向边，起初所有点都是白色的，现在你要选择两条路径（不一定是简单路径），并将它们所经过的点全部染黑，求黑点最多有多少个

$1\le n\le300$

S - マス目(grid)

有一个 $h\times w$ 的矩形，你要将其中一个包含 $(1,1)$ 与 $(h,w)$ 的四连通块染成黑色，求方案数，答案对 $10^9+7$ 取模

$2\le h\le6,2\le w\le100$

T - フィボナッチ(sequence)

数列 $\{a_i\}$ 满足：

$a_1=a_2=\cdots=a_k=1$
$a_i=a_{i-1}+a_{i-2}+\cdots+a_{i-k}(i>k)$

求 $a_n\bmod10^9+7$

$2\le k\le1000,1\le k\le10^9$