[ABC270Ex] add 1 Solution

更好的阅读体验戳此进入

题面

给定序列 $A_n$$A_n$，存在 $n$$n$ 个初始为 $0$$0$ 的计数器，每次可以进行如下操作：选定一个计数器使其变为 $0$$0$ 并使得其它所有计数器 $+1$$+1$。求期望的使对于每个 $i$$i$ 满足第 $i$$i$ 个计数器的数值不小于 $A_i$$A_i$ 的操作次数。对 $998244353$$998244353$ 取模。

Solution

大概是一道没有什么高端的算法，仅靠推式子的难度评黑的题。

首先我们不难想到，如果设当前计数器的值为 $C_i$$C_i$，那么我们的目的就是要满足所有 $A_i-C_i\le 0$$A_i - C_i \le 0$。

然后不太严谨地思考一下不难发现，我们每次是使除了选择的其它的计数器都加一，所以拖后腿的一定是 $max\{A_i-C_i\}$$\max\{A_i - C_i\}$，令 $k=max\{A_i-C_i\}$$k = \max\{A_i - C_i\}$ 则状态将仅与 $k$$k$ 相关。

于是此时不难想到一个较为简单的状态：令 $F(k)$$F(k)$ 表示状态为 $k$$k$ 时的期望操作次数。

显然 $F(0)=0$$F(0) = 0$，考虑转移，不难发现状态 $k$$k$ 肯定对应这一个或者一段 $A$$A$，因为序列 $A$$A$ 是不降的，所以我们假设第一个对应的前一个为 $A_{idx}$$A_{idx}$，显然对于前 $idx$$idx$ 个的操作都会使 $k\leftarrow k-1$$k \leftarrow k - 1$，对于 $idx$$idx$ 之后的操作都会使当前的 $k$$k$ 变为新的 $A_i$$A_i$，所以转移显然为：

转化一下：

现在不难发现即较小的都在左侧，较大的都在右侧，不过这个转移仍然不行，也就是我们是已知 $F(0)$$F(0)$ 然后想要求 $F(A_n)$$F(A_n)$，但是这个式子却是需要反过来转移的，所以需要优化。

考虑令 $G(k)$$G(k)$ 表示从状态 $0$$0$ 转移到状态 $k$$k$ 的期望次数，所以显然有 $G(k)+F(k)=F(A_n)$$G(k) + F(k) = F(A_n)$。移个项然后带进去 $F$$F$，显然有：

显然 $F(A_n)$$F(A_n)$ 抵消了，则：

类比一下之前的推出来：

显然：$G(A_n)=0$$G(A_n) = 0$，我们要求 $G(0)$$G(0)$，符合转移。

不难发现对于固定的 $k$$k$ 一定对应着固定的 $idx$$idx$，也就是 ${\displaystyle \frac{N-\sum _{i=idx+1}^{N}G(A_i)}{idx}}$$\dfrac{N - \sum_{i = idx + 1}^N G(A_i)}{idx}$ 可以认为是一个常数，令其为 $C$$C$，若再令 $B={\displaystyle \frac{N}{idx}}$$B = \dfrac{N}{idx}$，所以有 $G(k-1)=B\times G(k)+C$$G(k - 1) = B \times G(k) + C$，属于较为简单的转移，考虑矩乘优化，构造矩阵的过程也是平凡的，得到：

对于 $[A_i,A_{i+1}]$$[A_i, A_{i + 1}]$ 之间的部分的所有 $k$$k$ 显然 $B$$B$ 和 $C$$C$ 是相同的，这一部分用矩阵快速幂优化一下即可，最后复杂度应为 $O(2^{3}n\log A_i)$$O(2^3 n \log A_i)$。

Code

xxxxxxxxxx
89
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (998244353ll)
23

24
template < typename T = int >
25
inline T read(void);
26

27
struct Matrix2{
28
    ll v00, v01, v10, v11;
29
    friend Matrix2 operator * (const Matrix2 &a, const Matrix2 &b){
30
        return Matrix2{
31
            (a.v00 * b.v00 % MOD + a.v01 * b.v10 % MOD) % MOD,
32
            (a.v00 * b.v01 % MOD + a.v01 * b.v11 % MOD) % MOD,
33
            (a.v10 * b.v00 % MOD + a.v11 * b.v10 % MOD) % MOD,
34
            (a.v10 * b.v01 % MOD + a.v11 * b.v11 % MOD) % MOD
35
        };
36
    }
37
};
38
Matrix2 base{1, 0, 0, 1};
39

40
ll qpow(ll a, ll b){
41
    ll ret(1), mul(a);
42
    while(b){
43
        if(b & 1)ret = ret * mul % MOD;
44
        b >>= 1;
45
        mul = mul * mul % MOD;
46
    }return ret;
47
}
48
ll inv(ll v){return qpow(v, MOD - 2);}
49
Matrix2 qpow(Matrix2 a, ll b){
50
    Matrix2 ret(base), mul(a);
51
    while(b){
52
        if(b & 1)ret = ret * mul;
53
        b >>= 1;
54
        mul = mul * mul;
55
    }return ret;
56
}
57

58
int N;
59
ll A[210000];
60

61
int main(){
62
    N = read();
63
    for(int i = 1; i <= N; ++i)A[i] = read < ll >();
64
    Matrix2 ans{0, 1, 0, 0};
65
    ll cur(0);
66
    for(int i = N - 1; i >= 1; --i){
67
        ll B = N * inv(i) % MOD, C = (N - cur) * inv(i) % MOD;
68
        ans = ans * qpow(Matrix2{B, 0, C, 1}, A[i + 1] - A[i]);
69
        (cur += ans.v00) %= MOD;
70
    }printf("%lld\n", (ans.v00 % MOD + MOD) % MOD);
71
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
72
    return 0;
73
}
74

75
template < typename T >
76
inline T read(void){
77
    T ret(0);
78
    int flag(1);
79
    char c = getchar();
80
    while(c != '-' && !isdigit(c))c = getchar();
81
    if(c == '-')flag = -1, c = getchar();
82
    while(isdigit(c)){
83
        ret *= 10;
84
        ret += int(c - '0');
85
        c = getchar();
86
    }
87
    ret *= flag;
88
    return ret;
89
}

UPD

update-2023_01_27 初稿