机动训练
题目描述
整个岛可以看作一片 n*m 的区域，每个格子有自己的地形。
一条路径由一系列八连通的格子组成，两个格子八连通当且仅当这两个格子拥有公共的
顶点。
定义一条“机动路径”如下：
1、它是一条不自交的路径，即路径上任意两个格子都不是同一个
2、它的起点和终点处于不同位置，换言之这条路径至少包含 2 个格子
3、从起点开始，任何一步只能向不远离终点的方向移动，这里不远离指的是 x 和 y 两
个方向都不远离
举例说明(字符画需要用等宽字体查看)：
1 | .....y ...... .---. |
图中加号和减号标明了与 x 八连通的所有格子，其中加号是“不远离 y”的方向
因此可以看出，如下路径是机动路径：
1 | ++++++y ......+y .......y |
而如下路径不是机动路径：
1 | \../---y .......y .x. |
需要注意的是，某些不合法的路径甚至比机动路径还要短，这是因为机动路径不是按照
长度来定义的。
接下来定义一条机动路径的地形，岛上的地形由一个矩阵给出，如
1 | .**. |
的地形序列就是”.**.”(不包含引号)
每条机动路径的权重就是与之拥有相同地形序列的机动路径数量之和，例如与这条路径
拥有相同地形序列的路径有
1 | ./-y y... ...x x-\. ./-x x... ...y y-\. |
共 8 条，注意回文时正反算两条，以及自己也算一条。
所以这条机动路径的权重是 8，同时所有这 8 条机动路径的权重都是 8。
现在你需要统计所有的机动路径权重之和。
如果对这种统计方式没有直观的感受，可以查看样例说明。
输入格式
第一行两个整数 n, m，表示岛的大小。
接下来 n 行，每行 m 个字符，表示岛的地形。
字符集随数据规模给出。
输出格式
仅一个数，表示所有机动路径的权重之和。
由于这个数可能很大，你只需要输出它对 1000000009 取模的结果。
样例输入 1
2 2
.
.
样例输出 1
72
样例输入 2
2 3
..
\.*
样例输出 2
418
样例输入 3
4 4
abba
baab
baab
abba
样例输出 3
44512
提示
说明
【样例解释 1】
用中括号括起来的一些数对表示一条机动路径，坐标先行后列
地形序列”.*”：[(1, 1), (1, 2)], [(1, 1), (2, 1)], [(2, 2), (2, 1)], [(2, 2),(1, 2)]，共 4 条，每条权重为 4，计 16
地形序列”*.”：[(1, 2), (1, 1)], [(2, 1), (1, 1)], [(2, 1), (2, 2)], [(1, 2),(2, 2)]，共 4 条，每条权重为 4，计 16
地形序列”..”：[(1, 1), (2, 2)], [(2, 2), (1, 1)]，共 2 条，每条权重为 2，计 4
地形序列”**”：[(1, 2), (2, 1)], [(2, 1), (1, 2)]，共 2 条，每条权重为 2，计 4
地形序列”.*.”：[(1, 1), (1, 2), (2, 2)], [(1, 1), (2, 1), (2, 2)], [(2, 2),(2, 1), (1, 1)], [(2, 2), (1, 2), (1, 1)]，共 4 条，每条权重为 4，计 16
地形序列”*.*”：[(1, 2), (1, 1), (2, 1)], [(2, 1), (1, 1), (1, 2)], [(1, 2),(2, 2), (2, 1)], [(2, 1), (2, 2), (1, 2)]，共 4 条，每条权重为 4，计 16
共计 16+16+4+4+16+16=72
【样例解释 2】
地形序列”.*”：7 条，每条权重为 7，计 49
地形序列”*.”：7 条，每条权重为 7，计 49
地形序列”..”：4 条，每条权重为 4，计 16
地形序列”**”：4 条，每条权重为 4，计 16
地形序列”..*”：2 条，每条权重为 2，计 4
地形序列”.*.”：10 条，每条权重为 10，计 100
地形序列”.**”：2 条，每条权重为 2，计 4
地形序列”*..”：2 条，每条权重为 2，计 4
地形序列”*.*”：10 条，每条权重为 10，计 100
地形序列”**.”：2 条，每条权重为 2，计 4
地形序列”.*.*”：6 条，每条权重为 6，计 36
地形序列”*.*.”：6 条，每条权重为 6，计 36
共计 49+49+16+16+4+100+4+4+100+4+36+36=418
【数据规模与约定】
对于 10%的数据，n * m ≤ 4.
对于 30%的数据，n, m ≤ 5.
对于 60%的数据，n, m ≤ 10.
另有 20%的数据，所有地形均为”6”。
对于 100%的数据，1 ≤ n, m ≤ 30，字符集由大小写字母，数字和”.”、”*”构成。
Solution
似乎不可做？
树的难题
题目描述
给你一棵 n 个点的无根树。
树上的每条边具有颜色。一共有 m 种颜色，编号为 1 到 m。第 i 种颜色的权值为 ci。
对于一条树上的简单路径，路径上经过的所有边按顺序组成一个颜色序列，序列可以划
分成若干个相同颜色段。定义路径权值为颜色序列上每个同颜色段的颜色权值之和。
请你计算，经过边数在 l 到 r 之间的所有简单路径中，路径权值的最大值。
输入格式
第一行，四个整数 n, m, l, r。
第二行，m个整数 c1, c2, ……, cm，由空格隔开。依次表示每个颜色的权值。
接下来 n-1 行，每行三个整数
输出格式
输出一行，一个整数，表示答案。
样例输入 1
5 3 1 4
-1 -5 -2
1 2 1
1 3 1
2 4 2
2 5 3
样例输出 1
-1
样例输入 2
8 4 3 4
-7 9 6 1
1 2 1
1 3 2
1 4 1
2 5 1
5 6 2
3 7 1
3 8 3
样例输出 2
11
Solution
树分治，被扫把图卡了。。
魔法咒语
问题描述
Chandra 是一个魔法天才。
从一岁时接受火之教会洗礼之后，Chandra 就显示出对火元素无与伦比的亲和力，轻而易举地学会种种晦涩难解的法术。这也多亏 Chandra 有着常人难以企及的语言天赋，让她能轻松流利地说出咒语中那些极其拗口的魔法词汇。
直到十四岁，开始学习威力强大的禁咒法术时，Chandra 才遇到了障碍。
根据火之魔法规则，禁咒的构成单位是 N 个基本词汇。施法时只要凝聚精神力，说出一段用这些词语组成的长度恰好等于 L 的语言，就能释放威力超乎想象的火法术。过去的魔法师们总结了几种表达起来最连贯的组合方式，方便施法者以最快语速完成法术。
但具有魔法和语言双重天才的 Chandra 不满足于这几种流传下来的禁咒，因为她可以毫无困难地说出普通人几乎不可能表达的禁咒语句。然而，在实际施法时，Chandra 发现有些自创禁咒念出后不但没有预期效果，反而会使自己的精神力迅速枯竭，十分难受。
这个问题令 Chandra 万分不解。她大量阅读典籍，到处走访魔法学者，并且不顾精神折磨一次又一次尝试新咒语，希望找出问题的答案。
很多年过去了，在一次远古遗迹探险中，Chandra 意外闯进了火之神艾利克斯的不知名神殿。根据岩土特征分析，神殿应该有上万年的历史，这是极其罕见的。Chandra 小心翼翼地四处探索，沿着魔力流动来到一间密室。她看见密室中央悬浮着一本书籍。在魔法保护下书籍状况完好。精通上古语言的 Chandra 读过此书，终于解开了多年的困惑。
禁咒法术之所以威力强大，是因为咒语借用了火之神艾利克斯的神力。这本书里记载了艾利克斯生平忌讳的 M 个词语，比如情敌的名字、讨厌的植物等等。使用禁咒法术时，如果语言中含有任何忌讳词语，就会触怒神力而失效，施法者也一并遭受惩罚。
例如，若 ”banana” 是唯一的忌讳词语，“an”、”ban”、”analysis” 是基本词汇，禁咒长度须是 11，则“bananalysis” 是无效法术，”analysisban”、”anbanbanban”是两个有效法术。注意：一个基本词汇在禁咒法术中可以出现零次、一次或多次；只要组成方式不同就认为是不同的禁咒法术，即使书写形式相同。
谜题破解，Chandra 心情大好。她决定计算一共有多少种有效的禁咒法术。
由于答案可能很大，你只需要输出答案模 1,000,000,007 的结果。
输入格式
第一行，三个正整数 N, M, L。
接下来 N 行，每行一个只含小写英文字母的字符串，表示一个基本词汇。
接下来 M 行，每行一个只含小写英文字母的字符串，表示一个忌讳词语。
输出格式
仅一行，一个整数，表示答案（模 10^9+7）。
样例输入 1
4 2 10
boom
oo
ooh
bang
ob
mo
样例输出 1
14
样例输入 2
3 1 3
a
ab
aba
aaa
样例输出 2
3
样例输入 3
3 1 14
ban
an
analysis
banana
样例输出 3
15
提示
【样例解释 1】
有效的禁咒法术共有 14 种：boom/bang/oo，oo/oo/oo/oo/oo，oo/oo/ooh/ooh，
oo/ooh/oo/ooh，oo/ooh/ooh/oo，ooh/oo/oo/ooh，ooh/oo/ooh/oo，
ooh/ooh/boom，ooh/ooh/oo/oo，ooh/ooh/bang，ooh/bang/ooh，
bang/oo/oo/oo，bang/ooh/ooh，bang/bang/oo。
【样例解释 2】
有效的禁咒法术有 a/ab, ab/a, aba 共三种。注意，ab/a 和 aba 算成两种不同的禁咒法术。
Solution
AC自动机上DP