题解、Writeup、游记和碎碎念
有些人在社交网络中使用过许多的密码，我们通过将各种形式的信息转化为 01 信号，再转化为整数，可以将这个人在一段时间内使用过的密码视为一个长度为 n 的非负整数序列 A_1,A_2,...,A_n 。一个人相邻几次在社交网络中使用的密码很有可能是类似的，这使得密码并不是足够安全。为了检验某些人在某些时间段内是否可能受到不安全的影响，我们需要计算上述序列的复杂程度。
的值，这将作为我们评估密码复杂程度的一个部分。由于答案可能很大，你只需要给出答案对 10^9+61 取模的值即可。
菩萨为行，福慧双修，智人得果，不忘其本。
——唐朠立《大慈恩寺三藏法师传》
有才而知进退，福慧双修，这才难得。
——乌雅氏
如何福慧双修？被太后教导的甄嬛徘徊在御花园当中。突然，她发现御花园中的花朵全都是红色和蓝色的。她冥冥之中得到了响应：这就是指导她如何福慧双修的！ 现在御花园可以看作是有 N 块区域，M 条小路，两块区域之间可通过小路连接起来。现在甄嬛站在 1 号区域，而她需要在御花园中绕一绕，且至少经过 1 个非 1 号区 域的区域。但是恰好 1 号区域离碎玉轩最近，因此她最后还是要回到 1 号区域。由于太后教导她要福慧双修，因此，甄嬛不能走过任何一条她曾经走过的路。但是， 御花园中来往的奴才们太多了，而且奴才们前行的方向也不一样，因此甄嬛在走某条小路的时候，方向不同所花的时间不一定一样。天色快暗了，甄嬛需要尽快知道 至少需要花多少时间才能学会如何福慧双修。如果甄嬛无法达到目的，输出“-1”。
给出一个长度为 N 由 B、W、X 三种字符组成的字符串 S，你需要把每一个 X 染成 B 或 W 中的一个。
对于给出的 K，问有多少种染色方式使得存在整数 a,b,c,d 使得:
1<=a<=b<c<=d<=N
Sa,Sa+1,...,Sb 均为 B
Sc,Sc+1,...,Sd 均为 W
其中 b=a+K-1,d=c+K-1
由于方法可能很多，因此只需要输出最后的答案对 109+7 取模的结果。
农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。
问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第 n 个月有多少只兔子？
聪明的你可能已经发现，第 n 个月的兔子数正好是第 n 个 Fibonacci(斐波那契)数。栋栋不懂什么是 Fibonacci 数，但他也发现了规律：第 i+2 个月的兔子数等于第 i 个月的兔子数加上第 i+1 个月的兔子数。前几个月的兔子数依次为：
1 1 2 3 5 8 13 21 34 …
栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋在第一个月初买了一对小兔子开始饲养。
每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每 k 对兔子围成一圈，最后剩下的不足 k 对的围成一圈，由于兔子特别害怕孤独，从第三个月开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。
我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。例如，当 k=7 时，前几个月的兔子数依次为： 1 1 2 3 5 7 12 19 31 49 80 …
给定 n，你能帮助栋栋计算第 n 个月他有多少对兔子么？由于答案可能非常大，你只需要告诉栋栋第 n 个月的兔子对数除 p 的余数即可。
小 A 想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小 A 只有一棵结点数为 N 的树，结点的编号为 1,2,…,N，其中结点 1 为根；我们称这颗树为模板树。小 A 决定通过这棵模板树来构建一颗大树。构建过程如下：（1）将模板树复制为初始的大树。（2）以下(2.1)(2.2)(2.3)步循环执行 M 次（2.1）选择两个数字 a,b，其中 1<=a<=N，1<=b<=当前大树的结点数。（2.2）将模板树中以结点 a 为根的子树复制一遍，挂到大树中结点 b 的下方(也就是说，模板树中的结点 a 为根的子树复制到大树中后，将成为大树中结点 b 的子树)。（2.3）将新加入大树的结点按照在模板树中编号的顺序重新编号。例如，假设在进行 2.2 步之前大树有 L 个结点，模板树中以 a 为根的子树共有 C 个结点，那么新加入模板树的 C 个结点在大树中的编号将是 L+1,L+2,…,L+C；大树中这 C 个结点编号的大小顺序和模板树中对应的 C 个结点的大小顺序是一致的。下面给出一个实例。假设模板树如下图：
根据第(1)步，初始的大树与模板树是相同的。在(2.1)步，假设选择了 a=4，b=3。运行(2.2)和(2.3)后，得到新的大树如下图所示
现在他想问你，树中一些结点对的距离是多少。
给出正整数 N（可能有前导 0），请求出 N!最右非零的数位的值。
单点加，矩阵查询。
采药人的药田是一个树状结构，每条路径上都种植着同种药材。
采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。
采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。
敌方有 n 台人形兵器，每台的攻击力为 Ai，护甲值为 Di。我方只有一台人形兵器，攻击力为 ATK。战斗看作回合制， 每回合进程如下：
·1 我方选择对方某台人形兵器并攻击，令其护甲值减少 ATK，若护甲值<0 则被破坏。
·2 敌方每台未被破坏的人形兵器攻击我方基地造成 Ai 点损失。
但是，在第一回合开始之前，某两台敌方的人形兵器被干掉了(秒杀）。问最好情况下，我方基地会受到多少点损 失。
外面有一圈 N 个结点，中心有一个结点与 N 个结点都相连，总共就是 条边，删除 N 条边，使 N+1 个点连通，旋转相同视为等价，问有多少种情况。