题解：P15998 [ICPC 2020 NAC] All Kill

· · 题解

题意简述

每道题的思路出现时刻独立且均匀。程序按题号从小到大优先编码。求按时完成全部题目，且每道题的编码时间连续的思路时刻方案数。

解题思路

设所有题目的总代码量为 s，再令：

c=t-s+1

把比赛的 t 分钟看成一排车位。第 i 道题是一辆长度为 x_i 的车，想法出现的分钟是其偏好起点。车辆按题号从小到大进入，并从偏好起点向后找到第一个空位。只有接下来连续 x_i 个车位均为空，车辆才能停入。

在原程序中，第 i 道题也从想法出现后的第一个可用分钟开始编码。若接下来不能连续编码 x_i 分钟，就对应停车失败。因此，所有车辆成功停入恰好满足题目的两个要求。

先给出加长车辆的停车计数式。各车长度依次为 a_1,\dots,a_m，停车后剩余 z-1 个空位。合法偏好序列的数量为：

z\prod_{i=1}^{m-1}\left(z+m-i+\sum_{j=1}^{i}a_j\right)

该式可以用带根森林计数。补上停车场末尾的一个虚拟空位，得到 z 个根；每辆车对应一个普通结点。若偏好位置落在更早车辆的区间内，就连向该车辆，并记录区间内偏移。否则，连向左侧遇到的第一个根或更晚车辆。这个过程与合法停车方案一一对应。

对应森林的加权拉普拉斯矩阵为：

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

取全 1 向量以及前 i 项为 1 的向量作为一组基。此时 Q 变为三角矩阵，对角元依次是：

z,z+m-1+a_1,z+m-2+a_1+a_2,\dots

由矩阵树定理，行列式就是上述乘积，计数式成立。

本题中 m=n、a_i=x_i、z=c，所以答案为：

c\prod_{i=1}^{n-1}\left(c+n-i+\sum_{j=1}^{i}x_j\right)

依次维护代码时间前缀和即可。

参考代码

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

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