Atcoder abc299

發表於 更新於 分類於 ， Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘
Ex(概率论,矩阵快速幂次)

https://atcoder.jp/contests/abc299/tasks

Ex - Dice Sum Infinity

6面骰子(1…6), 正整数R

每次投骰子, X=历史所有骰子的和, 如果 X-R是 1e9的倍数, 操作退出

求 退出时, Exp(次数C), mod 998244353

R [1,1e9)

2s

1024mb

我的思路

p(t,k)= t次 和=1e9 k + R, 且 < k的时刻没有达到等于

$\displaystyle ans = \sum_{t=1}^{\infty} \sum_{k\in [\frac{t-R}{10^9},\frac{6t-R}{10^9}]} p(t,k)t$

或者能否 p[s] = 和达到s的概率

这样看起来似乎可以矩阵转移，快速幂 合并？

题解

Ei = 初始为$R-X\equiv i\pmod{10^9}$ 到结束需要的期望次数

直到$X-R\ge k10^9$ 总是会经过$k10^9 - i, i\in[1,6]$ 中的一个状态

所以这根据依赖关系其实是解6个$E_i,i\in[1,6]$

子问题

给整数r, 每次r-骰子, 如果 r<=0 则终止

找 e(r)=次数

和p_{i=0,-1,-2,-3,-4,-5} 的概率

有 线性recurrence relation

对于给定r可以O(log r), 如果骰子d面，则$O(d^2 \log d \log r)$时间复杂度

然后可以预计算出Ei

$\displaystyle ans= e(R-6)+\sum _ {i=1} ^ 6E _ ip _ {i-6}(R-6)$

这里 例如 E3 => 那么它的可能是 走到R 停止, 或者不经过R走到下一处的E1~E6, 所以显然这是可以建立的

例如 E1对 E3的贡献就是, E3不经过R走到非E(为了不重复), 然后一步走到E1, 然后贡献为 (概率 * (E3) + exp 这一段的次数期望

所以核心变成实现 移动距离l的 期望和期望次数

代码

https://atcoder.jp/contests/abc299/submissions/42075457

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
int read(){int r;scanf("%d",&r);return r;}
const int MAX = 1'000'000'000;
const int D=6;
const mint INV = mint(1)/D;
using ppe=pair<mint,mint>; // {概率, 期望}
using mat=array<array<ppe, D>, D>;

ppe operator +(const ppe&A,const ppe&B){
  return {A.first + B.first, A.second + B.second};
}
ppe operator -(const ppe&A,const ppe&B){
  return {A.first - B.first, A.second - B.second};
}
ppe operator *(const ppe&A,const ppe&B){
  return make_pair(A.first * B.first, A.first * B.second + A.second * B.first);
}

mat operator *(const mat&A,const mat&B){ // 矩阵乘法
  mat C;
  rep(i,0,D) rep(j,0,D) C[i][j] = {0, 0};
  rep(i,0,D) rep(j,0,D) rep(k,0,D) C[i][k] = C[i][k] + A[i][j] * B[j][k];
  return C;
}

mat matpow(mat A, int N){ // 矩阵快速幂
  mat ans;
  rep(i,0,D) rep(j,0,D) ans[i][j] = {i==j, 0}; // 单位矩阵
  while (N > 0){
    if (N&1) ans = ans * A;
    A = A * A;
    N /= 2;
  }
  return ans;
}
ppe get(int N){ // 利用矩阵快速幂次 计算 走N的距离 的概率，次数的期望
  // p[i] = sum p[i+1..i+D]/D
  // e[i] = sum e[i+1..i+D]/D + sum p[i+1..i+D]/D
  mat A;
  rep(i,0,D) rep(j,0,D) A[i][j] = {0,0};
  rep(i,0,D-1) A[i][i + 1] = {1, 0};
  rep(i,0,D) A[i][0] = ppe{INV, INV}; // 1 step
  A = matpow(A, N);
  return A[0][0];
}

int main(){
  int R=read();
  vector A(D, vector<mint>(D+1, 0)); // 增广 矩阵M|B, D行D+1列, M * A = B, A=列向量(E0,E1,...,ED)
  rep(i,0,D){
    A[i][i]++;
    if (i == R) continue;
    if (i < R) A[i][D] += get(R - i).second; // i -> D(直接) 的期望步数
    rep(j,MAX-D,MAX) if (j != R){ // 一定 i < j
      ppe P1 = get(j - i); // 直接 i -> j
      if (i < R && R < j){ // i -> R -> j 不要经过R
        ppe P2 = get(R - i) * get(j - R);
        P1 = P1 - P2;
      }
      // i -> j 且不经过R
      P1 = P1 * ppe{INV, INV}; // 再走一步长k,   i0 -> 不经过R -> j -> 一步到i1, i0,i1 \in [0,D)
      rep(k,1,D+1) if (j + k >= MAX){ // 再走一步k, 对应上一行的 * ppe{INV,INV}
        A[i][j+k-MAX] -= P1.first; // Ei = sum (P1.first * E(i1=j+k-MAX) + P1.second)
        A[i][D] += P1.second;
      }
    }
  }

  rep(i,0,D){ // 高斯消元
    int p = i;
    rep(j,i,D) if (A[j][i] != 0) p = j;
    swap(A[i], A[p]);
    assert(A[i][i] != 0);
    mint x = A[i][i].inv();
    rep(j,i,D+1) A[i][j] *= x;
    rep(j,0,D) if (j != i) per(k,i,D+1) A[j][k] -= A[j][i] * A[i][k];
  }
  printf("%d\n",A[0][D].val());
  return 0;
}

总结

Ex

这个题意我就读错了…

后面读懂后，有想到 矩阵快速幂次，但是这里很显然的 就可以建立 矩阵去求解，竟然没想到

后续就是实现了

然后这个里 (p1,e1) * (p2,e2) = (p1p2,p1e2+p2e1) 感觉需要悟一悟, 第一次见

除了这个 p,e处理，其它的从道理上讲应该都要能想到，只想到了一部分，还是不应该

参考

官方题解