题目链接：https://qoj.ac/contest/474/problem/3164

题目大意：两个人在参加比赛，一个想题一个写题，比赛时间总长为 $t$，有 $n$ 道题目，每道题目有需要写的时间，想题人想出每道题目的时间都是 $[0,t)$ 中均匀随机的整数，写题人每分钟会选择编号最小的没写完的题目写一分钟。

问最后 AK 而且每道题目写的时间是一个连续段的概率是多少。

做法

看了题解，感觉自己唐完了。

显然的，问题可以转换成在从小到大摆问题，当问题在 $x$ 时刻想出来后，会找到这个位置往后的第一个空位置放置其写代码的区间，放不下就是不合法。

接下来，一个显然的想法是，先考虑 $n=t$ 的情况，即全部都是 $1$ 的情况，在这种特殊的情况下，我们不需要担心区间是否放得下，所以问题等价于要求在时间 $i$ 内想出来的题目不少于 $i$ 道。

需要注意到，这个问题可以类似于转换为在一个 $n+1$ 的环上进行上述放区间的过程，不过两者的数量转换有个比例。

具体来说，我们可以将原问题再变换一下：在 $t+1$ 个时间区间上摆区间，但是不可能在第 $0$ 时刻想出题，即 $[0,1]$ 始终不被占据，然后将头和尾连起来，形成一个环，这对应一个环方案，旋转一下，对应 $t+1$ 个的不同的链方案。

这种对应可不可逆呢？注意到，由于 $n=t$ ，所以进行上述操作后，环上恰好有一个空位，而假设这个空位就是刚刚说的开头，断链得到的链方案就是能对应到它的方案。

所以环上的数量除 $n+1$ 就是答案了。

尝试推广这个结论，在原问题上，一样的，在链方案前面加一个空格，拼接，旋转，对应得到 $t+1$ 个不同的链方案（不同说明没有重边），为了更加形象的说明，可以认为建立了方案数 $(t+1)$ 条边，现在尝试通过环方案构造出相同的边集，可以发现，从每个空格断开后，环方案都可以得到一个不同的合法的链方案，可以证明，这样找到了所有的边，即我们以边的数量为桥梁证明了： $\mathrm{链方案}(t+1)=\mathrm{环方案}*(t+1-\sum\limits_{x})$ 。

上述思考过程一个可能的心路历程是：我们想要找到的方案是前面想题多后面想题少的方案，而不想找的是前少后多的，这两种方案之间具有一定的对称性，或许有助于启发我们想到在环上重新考虑这个问题，但是如果直接拼成环，一个直接的问题就是，我们无法从环断成链，不知道从哪断，因此在开头添加一个无法占据的空格作为标识。不过感觉这个解释也有点牵强。

然后就可以开始考虑计算环的方案。

考虑一个经典的组合问题，如果不是在环上选好想出题目的时间后找到后面第一个空位，而是在原地直接尝试放区间，即如果在环上不相交的放下这些区间，那么答案是显然的：$(t+1)A^{n-1}_(t+1-\sum\limit_{i=1}^{n}(x_{i}-1))$ 。

考虑这玩意的组合意义，就是我们认为每个区间的 $x_{i}-1$ 的空间不是其占据得到的，而是其扩展得到的，也就是在放下的那一刻，瞬间在其后面生成这么多的空间，最后总空间为 $t+1$ ，现在稍稍改一下题目，因此也只需要稍稍改一下式子即可。

答案就是：$(t+1)\prod_{limits}_{i=2}^{n}(t+1-\sum\limits_{j=i+1}(x_{j}-1))$ 。

然后就做完了，时间复杂度：$O(n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
const LL mod = 998244353;
LL ksm(LL x, LL y){
    LL ans = 1ll;
    while(y){
        if(y & 1) ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans;
}
LL fc[N], nfc[N]; 
int n, t, a[N];
int main(){
    cin.sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> t;
    t++;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        t -= a[i] - 1;
    }
    LL ans = t - n;
    t += a[1] - 1;
    for(int i = 2; i <= n; i++){
        ans = ans * t % mod;
        t += a[i] - 1;
    }
    cout << ans << "\n";
    return 0;
}

说来也搞笑，第二部分的结论过于自然和优美，以至于我在复盘我的思考过程时，发现过程全错，但是结果是对的，乐麻了。

看了题解，后半部分计数的思路和题解基本一致。

非常好的一道计数题，太优美了。