P4588 [TJOI2018] 数学计算
题目描述
小豆现在有一个数 \(x\)，初始值为 \(1\)。小豆有 \(Q\) 次操作，操作有两种类型：
1 m：将 \(x\) 变为 \(x \times m\)，并输出 \(x \bmod M\)
2 pos：将 \(x\) 变为 \(x\) 除以第 \(pos\) 次操作所乘的数（保证第 \(pos\) 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），并输出 \(x \bmod M\)。
输入格式
一共有 \(t\) 组输入。
对于每一组输入，第一行是两个数字 \(Q,M\)。
接下来 \(Q\) 行，每一行为操作类型 \(op\)，操作编号或所乘的数字 \(m\)（保证所有的输入都是合法的）。
输出格式
对于每一个操作，输出一行，包含操作执行后的 \(x \bmod M\) 的值。
输入输出样例 #1
输入 #1
1
10 1000000000
1 2
2 1
1 2
1 10
2 3
2 4
1 6
1 7
1 12
2 7
输出 #1
2
1
2
20
10
1
6
42
504
84
说明/提示
对于 \(20\%\) 的数据，\(1 \le Q \le 500\)。
对于 \(100\%\) 的数据，\(1 \le Q \le 10^5\)，\(t \le 5,1 \lt M \le 10^9\)，\(0 < m \leq 10^9\)。
题解
第一反应是直接模拟，直接把每次操作的数计算下来就好，然后操作二的时候直接除就好
然后发现你要除去的是真实的\(x\times m\)，你输出的是 \(x\times m \mod M\) ，如果只是单纯的记录 \(x\times m\) ，毫无疑问会爆 long long
当然我们可以直接上python，但是感觉出题人一样会把我们卡死
那使用乘法逆元直接去做似乎可以，然后发现 \(M\) 是输入的，没有保证一定是质数，也没有保证 \(x\mod M \neq 0\) ，乘法逆元也被出题人防死了
发现把每次操作看做一个位置，整个操作1的序列就是一个区间，当前操作就是要你维护类似整个区间的前缀积，然后我们就想到可以用类似线段树的方法维护
其实我开始根本看不出这和线段树有半根毛的关系
对于操作1 m， 将当前最尾部的操作位置的值设置为\(m\)，然后线段树上更新前缀积
对于操作2 pos,将操作序列第pos 位置的值改成1（这和除法操作等价），然后线段树上更新维护前缀积
这样子我们通过维护前缀积，避免了记录除法/乘法逆元的操作，这样在取模意义下也是合法的
代码
#include<bits/stdc++.h>
// #define mod 998244353
// #define int long long //由于作者比较懒，所以直接使用这个了
using namespace std;
typedef long long ll;
typedef __int128 ix;
typedef long double ldb;
const ll V = 2e5 + 100;
const int INF = 1e9 + 7;
void solve()
{int q,mod;cin >> q >> mod;vector<ll> mul(4 * q + 1);auto update = [&](int x) ->void{mul[x] = mul[2 * x] * mul[2 * x + 1] % mod;};auto build = [&](auto&& self,int now,int l,int r) ->void{if(l == r){mul[now] = 1;return ;}int mid = (l + r) >> 1;self(self,2 * now,l,mid);self(self,2 * now + 1,mid + 1,r);update(now);};auto modify = [&](auto&&self,int now,int l,int r,int x,int y,ll val) ->void{if(x <= l && r <= y){mul[now] = val % mod;return ;}int mid = (l + r) >> 1;if(x <= mid) self(self,2 * now,l,mid,x,y,val);if(mid + 1 <= y) self(self,2 * now + 1,mid + 1,r,x,y,val);update(now);};build(build,1,1,q);for(int i = 1;i <= q;++i){int opt,m;cin >> opt >> m;if(opt == 1) modify(modify,1,1,q,i,i,(ll)m);else modify(modify,1,1,q,m,m,1ll);ll ans = mul[1] % mod;cout << ans << "\n";}
}
signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int t;cin >> t;while(t--) solve();return 0;
}