Training Records 3

Estelle-N / 2024-10-05 / 原文

9.30

CSP 7

A

link

题目描述

给定 $5$ 个长度为 $n$ 的整数序列 $A,B,C,D,E$，求

\[\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^l\sum_{m=1}^n med(A_i,B_j,C_k,D_l,E_m) \mod 998244353 \]

其中，$med(a,b,c,d,e)$ 为 $a,b,c,d,e$ 的中位数。

枚举中位数，计算即可。

B

link

题目描述

给定一个 $n$ 个点 $m$ 条边的有向图。不保证不存在重边自环。

记 $f(x,y,k)$ 表示从 $x$ 到 $y$ 经过恰好 $k$ 条边的不同路径数量，两条路径不同当且仅当存在存在某个 $i$ 使得两条路径的第 $i$ 条边不同。

称一个有向图是有趣的，当且仅当存在 $x,y$，不存在任何正整数 $M$，使得 $k \ge M$ 时 $f(x,y,k)$ 为一常数，也即 $\lim\limits_{⁡k\to+ \infty} f(x,y,k)$ 不存在。

你需要判断给定的有向图是不是有趣的。

仔细分析，如果有长度 $\ge 2$ 的环，那么是有趣的。

如果两个自环可以互相到达，那么也是有趣的。

注意一个点有两个自环的情况。

否则就是无趣的。

C

link

题目描述

有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$个，$A$ 和 $B$ 玩游戏，$A$ 先手，每次操作可以进行以下操作：

选定一个还有石子的石子堆 $i$，记剩下的石子为 $a_i'$。
选定一个 $1\le x\le a_i'$，将该堆中的 $x$ 个石子移走。
选定一个 $0\le y\le a_i'-x$，将该堆中的 $y$ 个石子以任意方式分配到剩余的非空石子堆中。

第一个不能操作者输，问 $A$ 是否有必胜策略，多测。

如果所有数出现次数都为偶数则为必败态。

如果没有石子，那么所有数出现次数为偶数，此时为必败态。
对于一个必胜态，一定能转移到必败态。

设出现次数为奇数的点从小到大排序为 $a_1,\cdots,a_m$。如果 $m$ 是奇数，可以用 $a_m$ 把 $a_x$ 补成 $a_{x+1}$，$x<m$ 且为奇数。最后剩下的 $a_m$ 拿走。如果 $m$ 是偶数，可以用 $a_m$ 把 $a_x$ 补成 $a_{x+1}$，$x<m$ 且为偶数，$a_m$ 留下 $a_1$ 颗石子，最后剩下的 $a_m$ 拿走。
对于一个必败态，一定只能转移到必胜态。

所有数去重后从小到大排序为 $a_1,\cdots,a_m$。如果拿走 $a_t$，那么第 $a_t$ 的出现次数就是奇数，需要用 $a_x(x < t)$ 去把 $a_t$ 补成偶数出现次数。这时候 $a_x$ 的出现次数又变成奇数了，以此类推。最终 $a_1$ 出现次数是奇数，只能用拿走部分后剩下的 $a_t'$ 去补。这时候发现总和是不变的，但是要求每一步至少总和 $-1$，所以是不能转移到必败态的。

D

link

题目描述

你有一个奇怪的计数器，计数器上有一个数字 $x$，每次你可以做如下操作：

选择一个 $x=\overline{b_kb_{k-1}\cdots b_1b_0}_{(10)}$中的一个数位 $b_i$。将 $x$ 变为 $x+b_i$ 或者 $x-b_i$。

例如，当 $x=(616)_{10}$ 时，你可以选择 $b=1$，然后让 $x$ 变为 $x−b=(615)_{10}$。

你想要通过最少步数把 $x$ 变成 $y$，问最少步数是多少。

分治。对于区间 $[l,r]$，找到中间的 $9$ 个数 $x,\cdots,x+8$。

由于每次最多走 $9$ 个数，所以任意两个跨过中间数的点，在 $[x, x+8]$ 中，一定停留至少一个点。

对于中间的点分别对于区间 $[l,r]$ 跑最短路，处理区间 $[l,r]$ 的点到中间点的最短路和中间点到 $[l,r]$ 的最短路。

向下分治 $[l,x-1]$ 和 $[x+9,r]$ 即可。

询问时找到对应区间，枚举中间停留点即可。

10.1

CSP 8

A

link

题目描述

至少删掉多少数使得任意区间和 $< S$。

如果总不能满足，那么删掉所有数。

如果 $S \le 0$，那么把所有 $\ge S$ 的数删掉。

如果 $S > 0$，考虑从前向后加入数，维护最大后缀，如果 $\ge S$，那么弹出最大后缀中的最大数。

可以使用 multiset 维护。

但是弹出后 multiset 可能维护的就不是最大后缀了。

如果 multiset 维护的是正数就不会有这种情况。

遇到正数的时候只在 multiset 中加入。

遇到负数时，先把应该删掉的数删掉，使得最大后缀和 $< S$。

如果最大后缀加上当前数仍然 $\le 0$，那么 multiset 清空。

否则，一直找到 multiset 中的最小数抵消 $a_i$ 的影响，使 $a_i$ 为正，然后在 multiset 中加入 $a_i$。

代码

#include <set>
#include <cstdio>
#include <algorithm>

#define int long long

using namespace std;

const int N = 1000005;

int n, m, ans, sum, a[N], vis[N];

multiset <int> s;

signed main()
{
    freopen("score.in", "r", stdin);
    freopen("score.out", "w", stdout);

    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= n; ++ i)
        scanf("%lld", &a[i]);

    if(m <= 0)
    {
        for(int i = 1; i <= n; ++ i)
            ans += a[i] >= m;
        printf("%lld\n", ans);
        return 0;
    }

    for(int i = 1; i <= n; ++ i)
    {
        if(a[i] >= 0)
        {
            sum += a[i], s.insert(a[i]);
            while(sum >= m)
                sum -= *prev(s.end()), ++ ans, s.erase(prev(s.end()));
        }
        else
        {
            if(sum + a[i] > 0)
            {
                sum += a[i];
                while(a[i] < 0 && s.size())
                    a[i] += *s.begin(), s.erase(*s.begin());
                s.insert(a[i]);
            }
            else
                sum = 0, s.clear();
        }
    }
    printf("%lld\n", ans);

    return 0;
}

B

link

题目描述

大切题这个游戏的完整地图，可以看做是一棵 $n$ 个节点的树，树根为 $1$，节点编号 $1$ 到 $n$。

每次任务可以抽象为从一个题单 $u$ 开始，不断向上切题升级（只能向上走），一直到题单 $v$ 为止。（保证 $v$ 是 $u$ 的祖先）。

在一次任务开始的时候，你会得到一个板子，码风优秀度为 $c$，然后每一关都有一个板子宝箱，宝箱中的板子有一个码风优秀度 $a_i$。如果宝箱中板子的码风优秀度高于你手中的，你就会选择用这个板子替换手中的板子。

这样的任务总共有 $q$ 个。给出每一个关卡中板子的码风优秀度，以及 $q$ 次任务的起点与终点，以及任务初始时板子的码风优秀度。

现在想知道，对于每个任务，你会更换多少次板子。

倍增预处理每个点向上更换多少次板子后能到达哪个点。

C

link

题目描述

该国有 $N$ 个编号为 $1$ 到 $N$ 的城市，由 $N-1$ 条无向道路连接，第 $i$ 条道路连接城市 $i+1$ 和城市 $a_i$ ，经过道路 $i$ 的费用为 $v_i$。

小 $D$ 想在这个国家进行一次旅行。出于他的强迫症，行程有如下限制：

旅行必须在城市 $1$ 开始和结束。如果城市形成的树上有 $m$ 片叶子结点，那么旅行的天数必须是 $m+1$ 。每天结束时，除最后一天外，小 $D$ 必须住在叶子城市的某家酒店。在整个行程中，小 $D$ 必须在所有叶子结点城市只停留一次。在整个行程中，该国的所有道路必须正好经过两次。除第一天和最后一天外，小 $D$ 需要自行支付的费用为旅行期间发生的单日最大总通行费。剩余的通行费将由凉心出题人承担。

请帮助小 $D$ 设计满足条件且费用尽可能少的旅行。

二份答案 $mid$。

设 $f_{u,a,b}$ 表示 $u$ 子树，去第一个叶子节点的费用为 $a$，最终回到 $u$ 点的费用为 $b$，中间距离 $\le mid$ 是否可行。

这样会有很多无用状态。考虑每个节点存满足条件的 $(a,b)$ 点对。对于不同点对 $(a,b), (c, d)$，如果 $a \le c,b\le d$，那么不需要记录 $(c,d)$ 点对。这样需要记录的点对最多有字数内叶子节点个数个。把这些点对按照 $a$ 从小到大排序，$b$ 一定是递减的。合并时可以双指针。

D

link

最小斯坦纳树板子。

不过这题 $n \le 100,m \le 500,k\le 10$。

最终一定是一棵树。

状压。$f_{i,S}$ 表示以 $i$ 为根的树，覆盖了 $S$ 中的点的最小距离。

先枚举 $S$。

如果 $i$ 点有不止一个子树，枚举子集 $T$：

\[f_{i,S} \leftarrow f_{i,T} + f_{i,S-T} \]

如果只有一个子树：

\[f_{i,S} \leftarrow f_{j,S} + w(j,i) \]

类似最短路松弛操作。

杂

link

10.3

accoder 1 $\color{white}waccjyt2024$

*D

题目描述

有一颗 $n$ 个点有标号的树，点从 $1 \sim n$ 标号，边从 $1 \sim n - 1$ 标号为 $u_i,v_i$。

现在他想在这棵树的基础上构造一些新的树。

具体的，他想知道在能构造出的所有 $n$ 个点有标号无根树中，恰好的有 $x$ 条边与原树相同的数量。并且对于每个 $x\in[0,n-1] \cap \Z$，输出答案 $\mod 10^9+7$。

$n \le 8000$。

Prüfer 序列，状压 DP 可以处理 $n$ 很小的点。

Cayley 定理

link

节点个数为 $n$ 的有标号无根树的个数为 $n^{n-2}$。

扩展 Cayley 定理 1

$n$ 个有标号节点形成一个 $s$ 棵无根树的森林，且 $s$ 个点所在树两两不同的方案数为 $sn^{n-s-1}$。

证明考虑数学归纳法。

扩展 Cayley 定理 2

$n$ 个点有标号无根树，已经添加了若干条边，目前的连通块大小为 $a_1,a_2,\cdots,a_m$，连成一棵树的方案数为 $n^{m-2}\prod a_i$。

证明使用 Matrix-Tree 定理。

二项式反演

\[\begin{aligned} f(n) = \sum_{i=0}^n (-1)^i {n \choose i} g(i) &&\Leftrightarrow&& g(n) = \sum_{i=0}^n (-1)^i {n \choose i} f(i)\\ f(n) = \sum_{i=0}^n {n \choose i} g(i) &&\Leftrightarrow&& g(n) = \sum_{i=0}^n(-1)^{n-i} {n \choose i} f(i)\\ f(n) = \sum_{i=n}^m {i \choose n} g(i) && \Leftrightarrow && g(n) = \sum_{i=n}^m(-1)^{i-n}{i \choose n} f(i) \end{aligned} \]

设 $f_{u,i,j}$ 表示 $u$ 子树，当前连通块大小为 $i$，选择相同的变数为 $j$ 的方案数。

每次讨论是否选择当前边。

选择这条边：

\[f_{u,i,j}\times f_{v,k,l} \to f_{u,i+k,j+l+1} \]

如果不选择：

\[nk\times f_{u,i,j} \times f_{v,k,l} \to f_{u,i,j+l} \]

要防止最后分好连通块后连边时，连上这条边，所以有转移：

\[- f_{u,i,j} \times f_{v,k,l} \to f_{u,i+k,j+l} \]

考虑扩展 Cayley 定理 $2$ 中的式子 $\prod a_i$，是在每个连通块中选择一个点的方案数。

$f_{u,i,0/1}$ 表示 $u$ 子树，钦定选择 $i$ 条边，$u$ 点所在连通块是否选择点的方案数。

为了转移方便，这里不考虑最后是否连上了没有钦定选择的边，最后二项式反演即可。

由于空间开不下，使用 vector 维护，$O(n)$ 空间树上背包。

考虑求出 $f_{1}$ 数组的 $\text{OGF}$，即多项式 $F(x) = \sum_{i} f_{1,i,0}x^i$。

每次转移就是两个多项式相乘或者再乘点什么东西，于是可以代入 $n$ 个数，然后求出这 $n$ 个数的 $F$ 值，然后拉格朗日插值点值转系数。

拉格朗日插值点值转系数

时间复杂度 $O(n^2)$。

\[f(x)=\sum_{i=1}^n y_i(\prod_{j\not=i}\dfrac {x-x_j}{x_i-x_j}) \]

枚举 $i$，计算 $H_i = y_i\prod_{j\not=i}\frac 1 {x_i-x_j}$。

设 $F(x)=\prod_{i=1}^n(x-x_i)$，$G_i(x)=\frac {F(x)}{x-x_i}$。

\[\begin{aligned} \\ [x^0]F(x)&=-x_j[x^0]G_j(x)\\ [x^i]F(x)&=[x^{i-1}]G_j(x)-x_j[x^i]G_j(x)\quad (i>1) \end{aligned} \]

则

\[\begin{aligned} \\ [x^0]G_j(x)&=\dfrac{-[x^0]F(x)}{x_j}\\ [x^i]G_j(x)&=\dfrac{[x^{i-1}]G_j(x)-[x^i]F(x)}{x_j} \quad (i>1) \end{aligned} \]

$x_j=0$ 的情况要特殊判掉。

最终答案为

\[\sum_{i=1}^n H_iG_i(x) \]

代码

#include <cstdio>
#include <vector>
#include <algorithm>

#define int long long

using namespace std;

const int N = 8005;
const int mod = 1000000007;

vector <int> f[N][2];
int n, tot, inv, fac[N], ifa[N], head[N], siz[N], g[N][2];

struct Edge
{
    int to, nex;
};
Edge e[N << 1];

void add(int u, int v)
{
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}

int Pow(int x, int y)
{
    int r = 1;
    for(; y; y >>= 1, x = x * x % mod)
        if(y & 1)
            r = r * x % mod;
    return r;
}

void dfs(int u, int fa)
{
    siz[u] = 1;
    f[u][0].resize(5);
    f[u][1].resize(5);
    f[u][1][0] = f[u][0][0] = 1;
    for(int i = head[u], v; i; i = e[i].nex)
    {
        if((v = e[i].to) == fa)
            continue;
        dfs(v, u);
        for(int j = 0; j <= siz[u] + siz[v]; ++ j)
            g[j][0] = g[j][1] = 0;
        for(int j = 0; j < siz[v]; ++ j)
        {
            for(int k = 0; k < siz[u]; ++ k)
            {
                g[j + k + 1][1] = (g[j + k + 1][1] + f[u][0][k] * f[v][1][j] + f[u][1][k] * f[v][0][j]) % mod;
                g[j + k + 1][0] = (g[j + k + 1][0] + f[u][0][k] * f[v][0][j]) % mod;
                g[j + k][1] = (g[j + k][1] + f[u][1][k] * f[v][1][j] % mod * n) % mod;
                g[j + k][0] = (g[j + k][0] + f[u][0][k] * f[v][1][j] % mod * n) % mod;
            }
        }
        siz[u] += siz[v];
        f[v][0].clear();
        f[v][1].clear();
        f[v][0].shrink_to_fit();
        f[v][1].shrink_to_fit();
        f[u][0].resize(siz[u] + 5);
        f[u][1].resize(siz[u] + 5);
        for(int j = 0; j < siz[u]; ++ j)
            f[u][0][j] = g[j][0], f[u][1][j] = g[j][1];
    }
}

int C(int n, int m)
{
    return fac[n] * ifa[m] % mod * ifa[n - m] % mod;
}

signed main()
{
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);

    scanf("%lld", &n);
    for(int i = 1, u, v; i < n; ++ i)
        scanf("%lld%lld", &u, &v), add(u, v), add(v, u);

    dfs(1, 0);

    fac[0] = ifa[0] = 1;
    for(int i = 1; i <= n; ++ i)
        fac[i] = fac[i - 1] * i % mod;
    ifa[n] = Pow(fac[n], mod - 2);
    for(int i = n - 1; i >= 1; -- i)
        ifa[i] = ifa[i + 1] * (i + 1) % mod;

    inv = Pow(n, mod - 2);
    for(int i = 0; i < n; ++ i)
        f[1][1][i] = f[1][1][i] * inv % mod;

    for(int i = 0; i < n; ++ i)
    {
        int ans = 0;
        for(int j = i; j < n; ++ j)
            ans = (ans + C(j, i) * f[1][1][j] % mod * (j - i & 1 ? mod - 1 : 1)) % mod;
        printf("%lld ", ans);
    }
    printf("\n");

    return 0;
}

10.4

联测 2

A

link

题目描述

给定一个序列 $a$，我们希望选出一个 $a$ 的子序列 $b$，其中 $a$ 中的第 $i$ 个元素有 $p_i$ 的概率被选中，每个元素是否被选中之间是相互独立的。

如果 $b$ 的异或和为 $s$，称它的权值为 $s^2$，求bb的权值的期望。

答案对 $10^9+7$ 取模。

设 $a_i$ 为二进制第 $i$ 位为 $0$ 或 $1$。答案为：

\[E{\Big(}{\big(}\sum_{i}2^ia_i{\big)}^2{\Big)}=E{\Big(}\sum_i\sum_j2^{i+j}a_ia_j{\Big)}=\sum_i\sum_j2^{i+j}E(a_ia_j) \]

DP。设 $f_{i,j,0/1,0/1}$ 表示结果二进制下第 $i$ 位为 $0/1$，第 $j$ 位为 $0/1$ 的概率。

B

link

题目描述

给定 $n,m$，对于每个 $1 \le k \le m$，计数满足以下条件的 $01$ 串数量：

长度为 $n$，且恰有 $m$ 个 $1$ 和 $n - m$ 个 $0$。
最长的 $1$ 连续段长度恰好为 $k$。

注意 $m \neq 0$，因此最长的 $1$ 连续段长度不可能是 $0$。

答案对 $10^9+7$ 取模。

共有 $n-m$ 个 $0$，这些 $0$ 把 $1$ 分成了 $n-m+1$ 段，每段可空。

如果不考虑最长连续段长度的限制，使用插板法，方案数为 ${m+(n-m+1)-1 \choose (n-m+1)-1}$。

转化题意为计算最长 $1$ 连续段长度 $\le k$，然后进行差分。

容斥，枚举钦定有多少段长度 $>k$，设有 $x$ 段，相当于 $1$ 的数量减去 $x(k+1)$，然后再在 $m$ 段中选 $x$ 段加上 $k+1$。

复杂度调和级数。

C

link

题目描述

在石头剪刀布中，一共有三种手势：$R(Rock),P(Paper),S(Scissors)$，其中 $R$ 能赢 $S$，$S$ 能赢 $P$，$P$ 能赢 $R$。

现在，我们定义 $w(x,y)$ 是 $x$ 和 $y$ 中获胜的手势，特别地，如果 $x$ 和 $y$ 相同(也就是平局)，那么 $w(x,y)$ 也和 $x,y$ 均相同。$x$ 和 $y$ 均为 $R,P,S$ 中的某一种。

我们定义一个对长度为 $n$ 的字符串 $s$ 的操作 $f(s_1s_2\cdots s_n)=w(s_1,s_2)w(s_2,s_3)\cdots w(s_{n−1},s_n)$，也就是说操作结果是一个长度为 $n-1$ 的字符串，它的第 $i$ 位恰是 $w(s_i,s_{i+1})$，也就是 $s_i$ 和 $s_{i+1}$ 中获胜的手势。如 $f(RRRR)=RRR$，$f(RSPR)=RSP$。

我们定义一个长度为 $n$，且由 $R,P,S$ 组成的字符串的“最终胜者”是对这个字符串进行连续 $n-1$ 次 $f$ 操作得到的结果，它显然是某个长度为 $1$ 的字符串，并且是 $R,P,S$ 中的一种。

现在，给定一个长度为 $n$ 的字符串，你需要支持 $q$ 次操作，操作有两种：

1 k x：将这个字符串的第 $k$ 个字符修改为 $x$，$k$ 是 $1-n$ 之间的整数，$x\in R,P,S$。

2 l r：查询这个字符串的第 $l$ 个字符到第 $r$ 个字符形成的连续子串的“最终胜者”，$1 \le l \ le r$。

定义 $x>y$ 为 $x$ 手势可以赢 $y$ 手势。

一段连续的手势可以只留下一个，不影响结果。
如果 $a_i<a_{i-1},a_i<a_{i+1}$，可以只留下 $a_{i-1}$，不影响结果。

考虑全局询问。

使用栈维护这一操作。栈内元素 $s_{top} < s_{top - 1} < \cdots < s_1$。

若当前要加入 $a_i$ 元素，则 $s_{top} = a_{i-1}$。

如果 $a_i = a_{i-1}$，那么不加入当前元素。
如果 $a_i < a_{i-1}$，加入当前元素。
如果 $a_i > a_{i-1}$，由于 $s_{top - 1} > s_{top}$，可以只留下 $s_{top-1}$，弹栈。

如果栈中没有元素则加入当前元素。最终答案为栈底元素。

设 $f_i$ 表示加入 $a_i$ 后栈内的元素个数。

\[f_i = \begin{cases} f_{i-1}+1 & a_{i-1} > a_i\\ f_{i-1} & a_{i-1}=a_i\\ \max(1,f_{i-1}-1) & a_{i-1} < a_i \end{cases} \]

答案也就是最后的 $f_i = 1$ 的 $a_i$。

其实也可以把 $\max$ 去掉，就是 $f_i$ 最小的 $a_i$。

对于区间询问也是如此，找区间中 $f_i$ 最小的元素。可以使用线段树区间修改，区间求最小值维护。

*D

link

题目描述

给定一个序列 $m_1,m_2,\cdots,m_n$，对于每个 $1\le k \le \frac {n(n+1)} 2$，求满足以下条件的 $[1,2,...,n]$ 的排列 $p$ 个数：

对于每个 $l \le r \le m_l$，区间 $[p_l,p_{l+1},\cdots,p_r]$ 不是 $[l,l+1,\cdots,r]$ 的一个排列。
恰有 $k$ 组 $1 \le l \le r \le n$，使得区间 $[p_l,p_{l+1},\cdots,p_r]$ 是 $[l,l+1,\cdots,r]$ 的一个排列。

注意 $[p_1,p_2,\cdots,p_n]$ 始终是 $[1,2,\cdots,n]$ 的排列，$m$ 序列不一定递增。

答案对 $10^9+7$ 取模。

$1 \le n \le 40$。

定义合法区间为区间 $[p_l,p_{l+1},\cdots,p_r]$ 是 $[l,l+1,\cdots,r]$ 的一个排列。

定义本题中的本原连续段为不存在与之相交且不包含的合法区间。

合点的儿子一定是把它分成了若干段，且每个儿子都是析点。

析点可能没有儿子，或者若干区间之间不相邻，且 $l,r$ 处没有区间儿子，$l,r$ 处只能是叶子儿子。

设 $A_n$ 为只有 $[1,n]$ 合法的排列个数。

\[\begin{aligned} A_0 &= 1\\ A_1 &= 1\\ A_n &= (n - 1)\times A_{n-1} + \sum_{i=2}^{n-2} (i-1)\times A_i \times A_{n - i} \end{aligned} \]

证明：

P4566 证明

这个定义的是只有 $[1, n]$ 是连续段的方案数。

\[\begin{aligned} A_0 &= 1\\ A_1 &= 2\\ A_n &= (n - 1)\times A_{n-1} + \sum_{i=2}^{n-2} (i-1)\times A_i \times A_{n - i} \end{aligned} \]

如果原排列满足条件，只要 $n$ 不在 $n-1$ 的右边就满足条件。
如果原排列不满足条件，一定有且仅有一个极长不合法的区间，设区间长度为 $i$，区间值域不能包括 $n-1$，否则插入 $n$ 后这还是一个连续段。这样的区间值域有 $n-i-1$ 种选择方法。

原排列中，只有这一个极长的不合法区间，设这个区间值域为 $[x, x + i - 1]$，看成一个点。那么原排列的方案数为 $A_{n-i}$。

把 $n$ 插入这个极长区间，这个区间长度变为 $i$，打破了之前排列的所有不合法区间。把 $n$ 看成 $i + 1$，原排列看成值域 $[1, i]$。相当于原排列的所有连续段都跨过最大值的方案数。原排列的逆排列 $b_{a_i} = i$。原排列的连续段下标 $[i,j]$，值域 $[l,r]$，对应逆排列中连续段下标 $[l,r]$，值域 $[i,j]$，一一对应关系。由于 $r = i + 1$，所以在逆排列中，每个连续段都是一个后缀。因此方案数为 $A_i$。

如果原排列是合法的，那么原排列 $i \to a_i$ 连边，这些置换环不会占据一个区间。则新插入 $n$ 在任意置换环的边上都合法。方案数 $(n - 1) A_{n - 1}$。
如果原排列不合法。考虑原排列的析合树。因为新加入 $n$ 只能打破一个不合法区间。所以 $[1,n]$ 的节点只能是析点，且析点只有一个区间节点。枚举这个区间节点的长度 $i \in [1,n-3]$，值域有 $n-i-2$ 种可能的取值。

这个区间的值域确定，那么所在位置确定。剩下的 $n-i-1$ 个点需要不构成其他合法区间，方案数为 $A_{n-i-1}$。

这个区间长度为 $i$，仿照 P4566 证明，考虑逆排列，相当于所有合法区间在逆排列上都过最后一点的方案数，方案数为 $A_{i+1}$。

建立本题的析合树，定义和原析合树定义不同。

合点的儿子一定是把它分成了若干段，且每个儿子都是析点。

析点可能没有儿子，或者若干区间之间不相邻，且 $l,r$ 处没有区间儿子，$l,r$ 处只能是叶子儿子。

设 $f_{l,r,x,y}$ 表示将 $[l,r]$ 合并成一个合点，$[l,r]$ 内是 $[l,r]$ 的一个排列。只考虑 $[l,r]$ 的部分，共有 $x$ 个合法区间，有 $y$ 个儿子的方案数。

设 $g_{l,r,x,y}$ 表示将 $[l,r]$ 合并成一个析点，$[l,r]$ 内是 $[l,r]$ 的一个排列。只考虑 $[l,r]$ 的部分，共有 $x$ 个合法区间，有 $y$ 个叶子儿子的方案数。

合点转移每次枚举最后一个析点。设原来有 $v$ 个析点，新加的析点和之前的析点会新增加 $v$ 个合法区间。合点最开始初始化为一个析点。

析点转移，相当于每次添加一个叶子或一个区间再加一个叶子。设有 $v$ 个叶子，叶子间的排列方案数为 $A_v$。

这样的复杂度是 $O(n^8)$ 的。使用拉格朗日插值优化 $x$ 一维，复杂度 $O(n^6)$。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

#define int long long

using namespace std;

const int N = 41;
const int mod = 1e9 + 7;

int n, C[N], A[N], B[N], G[N][N], F[N][N], g[N][N][N], f[N][N][N], P[825][825];
int m, a[825], b[825], c[825], d[825], e[825], inv[825];

int Pow(int x, int y)
{
    int r = 1;
    for(; y; y >>= 1, x = x * x % mod)
        if(y & 1)
            r = r * x % mod;
    return r;
}

signed main()
{
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);

    scanf("%lld", &n);
    for(int i = 1; i <= n; ++ i)
        scanf("%lld", &C[i]);

    A[0] = A[1] = 1;
    for(int i = 2; i <= n; ++ i)
    {
        A[i] = (A[i] + (i - 1) * A[i - 1]) % mod;
        for(int j = 2; j <= i - 2; ++ j)
            A[i] = (A[i] + (j - 1) * A[j] % mod * A[i - j]) % mod;
    }

    for(int i = 0; i <= n; ++ i)
        B[i] = Pow(A[i], mod - 2);

    for(int i = 1; i <= n * (n + 1) / 2 + 1; ++ i)
    {
        P[i][0] = 1;
        for(int j = 1; j <= n * (n + 1) / 2 + 1; ++ j)
            P[i][j] = P[i][j - 1] * i % mod;
    }

    for(int i = 1; i <= n * (n + 1) / 2 + 1; ++ i)
    {
        memset(f, 0, sizeof(f));
        memset(g, 0, sizeof(g));
        memset(F, 0, sizeof(F));
        memset(G, 0, sizeof(G));
        for(int x = 1; x <= n; ++ x)
        {
            g[x][x][1] = i;
            if(C[x] < x)
                G[x][x] = f[x][x][1] = i;
        }
        for(int len = 2; len <= n; ++ len)
        {
            for(int l = 1, r = len; r <= n; ++ l, ++ r)
            {
                if(r > C[l])
                {
                    for(int v = 1; v <= len; ++ v)
                    {
                        for(int x = l + 1; x <= r; ++ x)
                            f[l][r][v] = (f[l][r][v] + f[l][x - 1][v - 1] * G[x][r] % mod * P[i][v - 1]) % mod;

                        F[l][r] = (F[l][r] + f[l][r][v]) % mod;
                    }
                }
                for(int v = 1; v <= len; ++ v)
                {
                    for(int x = l + 1; x <= r; ++ x)
                    {
                        if(x == r)
                            g[l][r][v] = (g[l][r][v] + g[l][x - 1][v - 1] * B[v - 1] % mod * A[v]) % mod;
                        else
                            g[l][r][v] = (g[l][r][v] + g[l][x - 1][v - 1] * B[v - 1] % mod * A[v] % mod * (G[x][r - 1] + F[x][r - 1])) % mod;
                    }
                    if(r > C[l])
                        G[l][r] = (G[l][r] + g[l][r][v]) % mod;
                }
                f[l][r][1] = G[l][r];
            }
        }
        a[i] = (F[1][n] + G[1][n]) % mod;
    }

    m = n * (n + 1) / 2 + 1;
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= m; ++ i)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;

    for(int i = 1; i <= m; ++ i)
    {
        b[i] = a[i];
        for(int j = 1; j < i; ++ j)
            b[i] = b[i] * inv[i - j] % mod;
        for(int j = i + 1; j <= m; ++ j)
            b[i] = - b[i] * inv[j - i] % mod;
    }

    c[0] = 1;
    for(int i = 1; i <= m; ++ i)
    {
        for(int j = i; j >= 1; -- j)
            c[j] = (c[j - 1] - i * c[j]) % mod;
        c[0] = - i * c[0] % mod;
    }

    for(int i = 1; i <= m; ++ i)
    {
        d[0] = - c[0] * inv[i] % mod;
        for(int j = 1; j <= m; ++ j)
            d[j] = (d[j - 1] - c[j]) % mod * inv[i] % mod;
        for(int j = 0; j <= m; ++ j)
            e[j] = (e[j] + d[j] * b[i]) % mod;
    }

    for(int i = 1; i <= n * (n + 1) / 2; ++ i)
        printf("%lld ", (e[i] + mod) % mod);
    printf("\n");

    return 0;
}