题解：P15998 [ICPC 2020 NAC] All Kill

· · 题解

题意简述

第 i 道题需要连续编码 x_i 分钟，其思路在 1 到 t 中等概率、相互独立地出现。每分钟总是优先编码编号最小的可编码题目。求所有题按时完成且每道题均未被打断的思路出现时刻方案数，对 998244353 取模。

解题思路

先将编码过程改写成停车过程。把 t 分钟依次看作 t 个位置，第 i 道题看作长度为 x_i 的车，其思路出现时刻就是首选位置。车辆按题号依次处理，从首选位置向右找到第一个尚未占用的位置，并尝试占据从这里开始的连续 x_i 个位置。

若这段位置中出现了空隙，说明原编码过程会在中途被编号更小的题打断。反之，车辆成功占据连续位置，就对应这道题连续编码完成。因此，题目所求恰好是所有车辆均成功停车的首选位置序列数。

下面计算更一般的模型。共有 m 辆车，长度依次为 a_1,a_2,\dots,a_m。设停车完成后还剩 z-1 个空位，则位置总数为：

\sum_{i=1}^{m}a_i+z-1

在停车场末端再补一个边界空位。它与原来的 z-1 个空位合计形成 z 个根，每辆车则形成一个普通结点。

对车辆 i 考察其首选位置。若该位置落在更早处理的车辆 j<i 的最终区间内，就令 i 指向 j。车辆 j 的区间中共有 a_j 种偏移，因此这条边的权值为 a_j。

否则，车辆 i 会直接从首选位置开始停车。从其左侧跨过连续的早期车辆后，最先遇到的对象只能是一个根或一辆编号更大的车辆，令 i 指向这个对象。这时首选位置由边界唯一确定，边权为 1。

沿边不断移动，最终一定到达某个空位根。反过来，给定这样的带权有根森林，可以按编号顺序恢复每辆车的位置；指向较小编号车辆的边权选择同时恢复首选位置在该车辆区间内的偏移。于是合法首选序列与这些森林一一对应。

将 z 个根合并为一个超级根。根据有向矩阵树定理，森林权值和等于矩阵 Q 的行列式，其中：

Q_{i,j}= \begin{cases} z+\displaystyle\sum_{k<i}a_k+m-i, & i=j \\ -a_j, & j<i \\ -1, & j>i \end{cases}

接下来直接消元计算这个行列式。先把第 m 列替换为所有列之和。因为 Q 的每一行元素和均为 z，新的第 m 列全部为 z。

再从上到下，将第 i 行替换为原第 i 行减去原第 i+1 行，其中 1\le i<m。记前缀长度为：

A_i=\sum_{j=1}^{i}a_j

变换后的第 i 行在第 i 列为 z+m-i+A_i，在第 i+1 列为其相反数，其余相关位置均为 0。最后一列除末行外也全部变为 0。

沿最后一列展开，剩余子式是上三角矩阵，所以：

\det Q=z\prod_{i=1}^{m-1}(z+m-i+A_i)

回到原题，设总代码时间为：

S=\sum_{i=1}^{n}x_i

停车后剩余 t-S 个位置，所以 z=t-S+1。最终答案为：

(t-S+1)\prod_{i=1}^{n-1}\left(t-S+1+n-i+\sum_{j=1}^{i}x_j\right)\pmod {998244353}

维护 x_i 的前缀和即可在线性时间内计算。时间复杂度为 O(n)，空间复杂度为 O(n)。

正确性证明

停车模型中，车辆 i 的首选位置等于思路出现时刻，第一个空位等于它第一次获得编码机会的分钟。车辆从该处连续占据 x_i 个位置，当且仅当这道题连续编码 x_i 分钟且在比赛结束前完成。因此所有车辆成功与题目要求的两个事件同时发生等价。

森林构造对每个合法停车方案给出唯一的父结点和边权选择。反向恢复时，根与较大编号父结点确定车辆区间左边界，较小编号父结点及边权选择确定首选位置的具体偏移，所以映射可逆。矩阵树定理计算的森林权值和就是合法首选位置序列数。

列替换与相邻行相减均不改变行列式。变换后沿最后一列展开，得到的上三角子式对角元依次为 z+m-i+A_i，故乘积公式成立。代入 m=n、a_i=x_i 和 z=t-S+1，代码计算的正是题目所求。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=100005;
const int mod=998244353;
int sum[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,t;
    cin>>n>>t;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        sum[i]=sum[i-1]+x;
    }
    int c=t-sum[n]+1;
    ll ans=c;
    for(int i=1;i<n;i++)ans=ans*(c+n-i+sum[i])%mod;
    cout<<ans<<'\n';
    return 0;
}