Whisper-6's Blog!

题意：求长为 的逆序对数恰好为 的排列个数。

答案对 取模。

，时限 。

题意 : 设 表示排列 的逆序对数。如果 长度为 则有 给定两个正整数 ，和一个排列 ，定义一个长度为 的排列 的权值 为

对于 求

其中 是长度为 的排列。

，时限 。

题意：给定两个整数 和一个 次多项式，对 分别求

其中 是长度为 的错排。

，时限 。

题意：给定两个整数 和一个 次多项式，求

其中 是长度为 的错排。

，时限 。

题意：设 将长为 的排列 当成置换时所能分解成的循环个数。给定两个整数 和一个 次多项式，对 分别求：

其中 是长度为 且不存在位置 使得 的排列。

，，时限 。

题意：维护一个长度为 的数组，初始时全为 。

进行 次区间加操作，求最后数组中各个位置的值。

考虑使用线段树维护，每次区间加时打上懒标记（不下推），最后一并下推。

每次区间加操作的区间在 个区间中等概率随机，值在 中随机。

问最后推标记时，推标记的期望次数。（若当前节点的加法标记为 则不会触发推标记，反之则会触发）

答案对 取模，，时限 。

题意：有 个开关，每个开关有 两种状态，初始状态为 。

对某个开关进行操作可以使得其状态改变，由 变为 或由 变为 。

每个开关都有目标状态，记 为第 个开关的目标状态，当所有开关都达到目标状态，任务达成。

操作按照一定规则随机，具体地，第 个开关有权值 ，随机到的概率即为 。

求按上述规则随机操作时，完成任务所需的期望操作次数。

答案对 取模，，，时限 。

题意：给出一张 个点 条边的无向图。每个点有自己的颜色。

• 若点 到 的任意两条简单路径边不相交，则称 关于 互不影响。

• 若点 到节点 的任意简单路径边经过点 ，则称 必经 。

设 为满足下列条件的 元集合 的个数。

• 中所有点颜色相同，且与 的颜色不同。

• 对于任意 ， 必经 。

• 对于任意 ， 关于 互不影响。

给出参数 ，求下列式子的值：

答案对 取模，，，，时限 。

题意：给出一棵 个点的树 ，边编号为 。

保证对于任意一个节点 ，从 到 号点的简单路径都不经过任何编号小于 的点。

按照如下步骤生成一张包含 个节点的无向图 ：

选取一个 的排列 ，然后依次进行 次操作。

在进行第 次操作时，首先删除树 中编号为 的边 ，然后，记 和 分别为当前树 中与 联通的所有点中，编号最大的点，并在图 的 号点和 号点之间连一条边。

求对于给定的树 ，按上述方式一共可以生成多少种本质不同的图 。图 和 本质不同当且仅当存在 和 满足在 中不存在边 ，而 中存在。

答案对 取模，，时限 。

题意：定义一个括号串的 级偏值为将该括号串修改为合法括号串需要的最小操作数。

在某次操作中，可以添加或删除一个括号。

定义一个括号串的 级偏值为该串所有子串 的 级偏值之和。

现在你需要求出一个长度为 的括号串 的 级偏值。答案对 取模。

，时限 。