给定一个 $n$ 个点，以 $1$ 为根的有根树，砍断第 $i$ 条边的代价为 $c_i$。有 $m$ 次询问，每次给出 $k_i$ 个关键点（保证关键点不含 $1$ 号节点），询问能够使 $1$ 号节点不能到达任何关键点，所要砍断边的代价和最小是多少。

数据范围：$n,m \leq 250000,\sum {k_i} \leq 5 \times 10^5$

有一个 $n$ 行 $m$ 列的棋盘，棋盘上可以放很多特殊的棋子，每个棋子的攻击范围是 $3$ 行 $p$ 列。输入数据用一个 $3 \times p$ 的矩阵给出了棋子攻击范围的模板，棋子被默认在模板中的第 [二] 行，第 [$k+1$] 列，模板中棋子能攻击到的位置标记为 1，不能攻击到的位置是 0 $(1 \leq p \leq m, 0 \leq k < p)$。输入数据保证模板中的第 [二] 行第 [$k+1$] 列是 1。

打开门的密码是这样的：在要求棋子互相不能攻击到的前提下，摆放棋子的方案数。注意什么棋子都不摆也算作一种可行方案。请求出方案对 $2^{32}$ 取余的结果即可。

给定一个 $n$ 个点， $m$ 条边的无向图。聪聪开始的时候在 S，可可在节点 T 处。以后的每个时间单位，可可都会选择去相邻的景点(可能有多个)中的一个或停留在原景点不动。而去这些地方所发生的概率是相等的。假设有 $P$ 个景点与景点 M 相邻，它们分别是景点 R、 景点 S，……，景点 Q，在时刻 $i$ 可可处在景点 M，则在 $i+1$ 时刻，可可有 $\frac{1}{1+P}$ 的可能在景点 R，有 $\frac{1}{1+P}$ 的可能在景点 S，……，有 $\frac{1}{1+P}$ 的可能在景点 Q，还有 $\frac{1}{1+P}$ 的可能停在景点 M。

当聪聪在景点 C 时，她会选一个更靠近可可的景点，如果这样的景点有多个，她会选一个标号最小的景点。如果走完第一次移动以后仍然没吃到可可，她还可以在本段时间内再向可可进行一次移动。

在每个时间单位，假设聪聪先走，可可后走。在某一时刻，若聪聪和可可位于同一个景点，则可怜的可可就被吃掉了。

请求出平均情况下，聪聪用几个时间单位就可能吃到可可。

给一个数字串 $s$ 和正整数 $d$ , 统计 $s$ 有多少种不同的排列能被 $d$ 整除（可以有前导 $0$ ）。

有 $n$ 家洗车店从左往右排成一排，每家店都有一个正整数价格 $p_i$ 。有 $m$ 个人要来消费，第 $i$ 个人会驶过第 $a_i$ 个开始一直到第 $b_i$ 个洗车店，且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于 $c_i$，那么这个人就不洗车了。

请给每家店指定一个价格，使得所有人花的钱的总和最大。

佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。

现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可 。

注意：每种变化最多只有一个值发生变化。

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度、并且能够拦截任意速度的导弹，但是以后每一发炮弹都不能高于前一发的高度，其拦截的导弹的飞行速度也不能大于前一发。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

在不能拦截所有的导弹的情况下，我们当然要选择使国家损失最小、也就是拦截导弹的数量最多的方案。但是拦截导弹数量的最多的方案有可能有多个，如果有多个最优方案，那么我们会随机选取一个作为最终的拦截导弹行动蓝图。

我方间谍已经获取了所有敌军导弹的高度和速度，你的任务是计算出在执行上述决策时，每枚导弹被拦截掉的概率。

小 $Y$ 最近在一家金券交易所工作。该金券交易所只发行交易两种金券：$A$ 纪念券（以下简称 $A$ 券）和 $B$ 纪念券（以下简称 $B$ 券）。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动，两种金券都有自己当时的价值，即每一单位金券当天可以兑换的人民币数目。我们记录第 $K$ 天中 $A$ 券 和 $B$ 券的价值分别为 $A_K$ 和 $B_K$（元/单位金券）。为了方便顾客，金券交易所提供了一种非常方便的交易方式：比例交易法。比例交易法分为两个方面：

（a）卖出金券：顾客提供一个 $[0,100]$ 内的实数 $OP$ 作为卖出比例，其意义为：将 $OP%$ 的 $A$ 券和 $OP%$ 的 $B$ 券以当时的价值兑换为人民币；

（b）买入金券：顾客支付 $IP$ 元人民币，交易所将会兑换给用户总价值为 $IP$ 的金券，并且，满足提供给顾客的 $A$ 券和 $B$ 券的比例在第 $K$ 天恰好为 $Rate_K$ ；

注意到，同一天内可以进行多次操作。小 $Y$ 是一个很有经济头脑的员工，通过较长时间的运作和行情测算，他已经知道了未来 $N$ 天内的 $A$ 券和 $B$ 券的价值以及 $Rate$ 。他还希望能够计算出来，如果开始时拥有 $S$ 元钱，那么 $N$ 天后最多能够获得多少元钱。

为了庆祝 $NOI$ 的成功开幕，主办方为大家准备了一场寿司晚宴。小 $G$ 和小 $W$ 作为参加 $NOI$ 的选手，也被邀请参加了寿司晚宴。

在晚宴上，主办方为大家提供了 $n−1$ 种不同的寿司，编号 $1,2,3,⋯,n-1$ ，其中第种寿司的美味度为 $i+1$（即寿司的美味度为从 $2$ 到 $n$ ）。

现在小 $G$ 和小 $W$ 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 $G$ 品尝的寿司种类中存在一种美味度为 $x$ 的寿司，小 $W$ 品尝的寿司中存在一种美味度为 $y$ 的寿司，而 $x$ 与 $y$ 不互质。

现在小 $G$ 和小 $W$ 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数 $p$ 取模）。注意一个人可以不吃任何寿司。

小 $\text{G}$ 是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。

一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小 $\text{G}$ 给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小 $\text{G}$ 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小 $\text{G}$ 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的 $P$ 次方，而一个排版的不协调度为所有行不协调度的总和。

小 $\text{G}$ 最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。

你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块，你需要重复下面的操作 $k$ 次：

• 选择一个有超过一个元素的块（初始时你只有一块，即整个序列）
  • 选择两个相邻元素把这个块从中间分开，得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

有 $n$ 件物品，每件物品有三个属性 $a[i], b[i], c[i]$ , $(a[i] < b[i])$ 。

再给出 $q$ 个询问，每个询问由非负整数 $m$ , $k$ , $s$ 组成，问是否能够选出某些物品使得：

• 对于每个选的物品 $i$ ，满足 $a[i] \leq m$ 且 $b[i]>m+s$ 。

• 所有选出物品的 $c[i]$ 的和正好是 $k$ 。

可读版题意：

给定 $n$ 个仅包含大写字母的模板串，求所有的长度为 $M$ 且仅包含大写字母的不同字符串中，有多少个包含至少一个模板串。答案对 $10007$ 取模。

阿申准备报名参加 $GT$ 考试，准考证号为 $n$ 位数 $X_1X_2\cdots X_n(0\le X_i\le 9)$，他不希望准考证号上出现不吉利的数字。

他的不吉利数字 $A_1A_2\cdots A_m(0\le A_i\le 9)$ 有 $m$ 位，不出现是指 $X_1X_2\cdots X_n$ 中没有恰好一段等于 $A_1A_2\cdots A_m$，$A_1$​ 和 $X_1$ 可以为 $0$。

阿申想知道不出现不吉利数字的号码有多少种，输出模 $K$ 取余的结果。

HH 是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为 HH 是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。

现在给你学校的地图（假设每条路的长度都是一样的都是 $1$ ），问长度为 $t$ ，从给定地点 $A$ 走到给定地点 $B$ 共有多少条符合上述条件的路径。