[Leaf] [P4588] 数学计算

p4588-[tjoi2018]-数学计算---洛谷">P4588 [TJOI2018] 数学计算 - 洛谷

1. 题面梗概

中译中: 维护一个变量 xx（初值为 11）。有两种操作：一是将 xx 乘上一个数 mm；二是撤销第 pospos 次操作所乘的数（即除以那个数）。每次操作后都要输出 x mod Mx \bmod M。

难点: 模数 MM 不一定是质数，且不保证与乘数互质。这意味着逆元可能不存在，直接做除法会卡死。

2. 逻辑推导

在模运算前提下，除以一个数最直接的想法就是求解逆元。但 MM 不保证为质数，所以我们需要一种不需要逆元也能实现 撤销 逻辑的方法。

2.1 建模

  • 我们可以把 QQ 次操作看作是时间轴上的 QQ 个节点。
  • 操作 1 ：在第 ii 个节点放入一个乘数 mm。
  • 操作 2：将第 pospos 个节点的乘数变为 11。
  • 结论：当前的 xx 实际上就是这 QQ 个节点所有数字的乘积。

2.2 线段树

既然如此，这个问题就转化为了一个维护区间乘积，支持单点修改的数据结构问题，我们采用线段树来处理。

3. 代码实现

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e5 + 5;
ll mod;

struct Info {
    ll prod = 1;
    static Info merge( const Info& l, const Info& r ) {
        return { (l.prod * r.prod) % mod };
    }
};

struct Node {
    int l, r;
    Info info;
} tr[ maxn << 2 ];

#define ls (u << 1)
#define rs (u << 1 | 1)

void push_up( int u ) {
    tr[u].info = Info::merge( tr[ls].info, tr[rs].info );
}

void build( int u, int l, int r )
{
    tr[u].l = l, tr[u].r = r;
    if( l == r )
    {
        tr[u].info = { 1 };
        return;
    }
    int mid = (l + r) >> 1;
    build( ls, l, mid );
    build( rs, mid + 1, r );
    push_up( u );
}

void modify( int u, int pos, ll val )
{
    if( tr[u].l == tr[u].r )
    {
        tr[u].info.prod = val % mod;
        return;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if( pos <= mid ) modify( ls, pos, val );
    else modify( rs, pos, val );
    push_up( u );
}

void solve( )
{
    int Q;
    cin >> Q >> mod;
    build( 1, 1, Q );

    for( int i = 1; i <= Q; ++ i )
    {
        ll op, v;
        cin >> op >> v;
        if( op == 1 ) modify( 1, i, v );
        else modify( 1, v, 1 );
        cout << tr[1].info.prod << '\n';
    }

}

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int _t = 1;
    cin >> _t;
    while( _t -- )
    {
        solve( );
    }
    return 0;
}

4. 复盘

  • 复杂度: O(Qlog⁡Q)O( Q \log Q )。

  • 碎碎念: 这题的关键在于把除法转换成抹除历史操作。它不仅避开了逆元，还将动态的问题转化为了静态区间上的单点修改。

  • 关联笔记: 线段树基础理论 | 降维技巧 乘法逆元体系