如今走过这世间 题解

· · 题解

[D] 如今走过这世间 题解

更新：感谢 @Alphas 指出复杂度笔误。

Subtask 0

样例解释中说每种以 v 开头的视频发布序列是等可能的。因此，考虑枚举每种可能的序列。

时间复杂度：O(t^n)。

Subtask 2

只有一种视频，只能一直发布它，故总收益 P 可以表示为：

P = {{b_1 \times k \times d_{1,1}^n} \over {d_{1,1} - 1}}

时间复杂度：O(1)。

Subtask 4

设 dp_{i,state,p} 表示到达第 i 个视频，当前类型为 state，已经进行了 p 次折半（d_{i,j} = 0.5）的期望收益，即可进行 O(n^2 \times t^2) 的转移。

时间复杂度：O(n^2 \times t^2)。

Subtask 5

每个视频的收益保持不变，计算平均收益后乘以视频总数即可。注意第一个视频是特殊的。

时间复杂度：O(t)。

Subtask 6

考虑构造 2t \times 2t 的矩阵分别转移期望收益和期望粉丝数，用矩阵快速幂求解即可。

时间复杂度：O(t^3 \log n)。注意 8 倍常数。

Subtask 7

从 Subtask 4 的思路出发，注意到正着 dp 会受到粉丝数的影响，考虑从后往前 dp。粉丝数的倍数变化相当于之后的收益都将乘以该倍数，倒着 dp 即可。

令第 i 个视频发布时获得利润的系数（即忽视 [1,i-1] 的视频与粉丝数）为 1，当前视频类型为 j，则：

dp_{i,j} = b_j + {{ \sum_{k=1}^t {(d_{j,k} \times dp_{i+1,k})} } \over t}

边界条件 dp_{n,j} = 1， 最终答案即为 dp_{1,v} \times k。

时间复杂度：O(n \times t^2)。

Subtask 8

注意到 Subtask 7 的式子事实上只有加法和乘法，因此考虑构造矩阵。初始（边界条件）时矩阵（位置从 0 开始计数）如：

\begin{bmatrix} 1 & 1 & \dots & 1 \end{bmatrix}

注意共 t+1 列，因为第 0 列有特殊用途：让所有值能够加上 b_i。

变换矩阵形如：

\begin{bmatrix} 1 & b_1 & b_2 & \dots & b_t \\ 0 & d_{1,1} & d_{2,1} & \dots & d_{t,1} \\ 0 & d_{1,2} & \ddots & & d_{t,2} \\ 0 & \vdots & & \ddots & \vdots \\ 0 & d_{1,t} & d_{2,t} & \dots & d_{t,t} \end{bmatrix}

注意要把输入的行列反一下（即将输入的 d 矩阵转置），因为我们在倒推。

时间复杂度：O(t^3 \log n)。

代码

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

inline void train() {
       ios::sync_with_stdio(false);
       cin.tie(0);
       cout.tie(0);
}

constexpr int N = 103;
using value_type = long long;
constexpr long long MODER = 998244353;
long long timing;

long long inved[N][N];

struct matrix {
    matrix(int d1, int d2) : d1(d1), d2(d2) {
        for (int i = 0; i < d1; i++) {
            for (int j = 0; j < d2; j++) {
                va[i][j] = 0;
            }
        } 
    }
    int d1, d2;
    value_type va[N][N];
};

matrix unit_gen(int s) {
    matrix ans = matrix(s,s);
    for (int i = 0; i < s; i++) {
        ans.va[i][i] = 1;
    }
    return ans;
}

matrix operator * (const matrix &a, const matrix &b) {
    int d1 = a.d1, d2 = b.d2, p = a.d2;
    if (p != b.d1) {
        throw exception();
    }
    matrix ans = matrix(d1, d2);
    for (int r1 = 0; r1 < d1; r1++) {
        for (int r2 = 0; r2 < d2; r2++) {
            for (int rp = 0; rp < p; rp++) {
                ans.va[r1][r2] = (ans.va[r1][r2] + (a.va[r1][rp] * b.va[rp][r2]) % MODER) % MODER;
            }
        }
    }
    return ans;
}

long long fastpow(long long a, long long b) {
    if (b <= 0) return 1ll;
    else if (b&1) return a * fastpow(a, b-1) % MODER;
    else {
        long long v = fastpow(a, b>>1);
        return v * v % MODER;
    }
}

matrix fastpow(matrix x, long long val) {
    int s = x.d1;
    if (x.d2 != s) {
        throw exception();
    }

    matrix src = unit_gen(s);
    while (val) {
        if (val & 1) {
            src = src * x;
        }
        x = x * x;
        val >>= 1;
    }

    return src;
}

long long n;
int t,k,v,g;
long long b[N], d[N][N];

int main() {

    train();

    timing = fastpow(100, MODER-2);

    cin>>n>>t>>k>>v>>g;
    matrix last(1, t+1), transform(t+1, t+1);
    last.va[0][0] = 1;
    transform.va[0][0] = 1;
    for (int i = 1; i <= t; i++) {
        cin>>b[i];
        last.va[0][i] = b[i];
        transform.va[0][i] = b[i];
    }

    long long tdiv = fastpow(t, MODER-2);

    for (int i = 1; i <= t; i++) {
        for (int j = 1; j <= t; j++) {
            cin>>d[i][j];
            d[i][j] = d[i][j] * timing % MODER;
        }
    }

    for (int i = 1; i <= t; i++) {
        for (int j = 1; j <= t; j++) {
            transform.va[j][i] = d[i][j] * tdiv % MODER;
        }
    }

    matrix res = last * fastpow(transform, n-1);
    cout<<res.va[0][v] * k % MODER<<endl;
    //cout<<flush;

    return 0;
}