题目 小沙不会计数，所以他想从小学数学开始学起，今天老师布置了一大堆算数题，但爱耍小聪明的小沙发现这么多的算数题中，他们中间的符号都是+++或者×\times× 并且每个题+++和×\times×的位置都是一样的
小沙想要快点去玩耍，所以求助好哥哥你帮帮他快速的计算出答案。
由于答案数字过大 所以我们对100000000710000000071000000007取模
输入描述: 第一行 给定二个个数n代表有n个数进行计算 q代表有q次询问
(2≤n≤1062\leq n \leq 10^62≤n≤106,1≤q≤1051\leq q \leq 10^51≤q≤105) 第二行 给定一个一个长度为n-1的*+字符串 表示我们要进行的计算符号是什么 第三行 给定n个整数，代表这每个位置上的数字
随后q行每行两个数字x,y代表着将第x个数字改成y且x≤nx\leq nx≤n
本题所有数均为正整数，且小于100000000710000000071000000007
但并不保证计算过程中是否会出现大于100000000710000000071000000007的值
输出描述: 对于每次查询，回答出整个算式的答案 每个答案占一行
（本题中的每次查询均不独立，也就是说每次查询修改之后的数，都会永远的修改）
【ACM专题学习|小沙的算数--并查集 (联通块)】样例输入
5 3
++*+
1 1 3 1 1
4 2
1 7
5 6
样例输出
9
15
20
分析 观察可以发现，用乘号连在一起的数不受加号影响，那将乘号连起来的结点合并，将所有数相乘的结果存储在父结点。
用mu[i]表示以i作为父结点时该联通块相乘的结果，如果没有乘号连接，则mu[i]就等于a[i]的值。
当改变数时，对应的连通块值会改变，那就将所有结果先算出来放在sum里,最后再改变sum的值。因为计算过程中顺便取了模，所以要将mu[i]和a[i]放大后再运算，再缩小与sum相加。
除以用乘法逆元，结果+mod%mod保证为正数。
式子mu[xx]*qmi(a[x],mod-2,mod)是乘法逆元和放大操作，作用就是联通块的值除去a[x]
放大操作用快速幂进行快速放大
c*((mu[xx]*qmi(a[x],mod-2,mod))%mod)%mod
=y*((mu[xx]*qmi(a[x],mod-2,mod))%mod)%mod-a[x]*((mu[xx]*qmi(a[x],mod-2,mod))%mod)%mod
如果是有乘号的联通块，
就是sum加上(联通块除去被替换的数再乘上新的数)，减去(之前联通块的值)
如果是没有乘号的联通块，mu[xx]*qmi(a[x],mod-2,mod)的值为1
c*((mu[xx]*qmi(a[x],mod-2,mod))%mod)%mod=y-a[x]
代码
#include
#include
#include
#define ll long long
using namespace std;
const int mod = 1000000007;
ll fa[2000015];
ll mu[2000015];
ll a[2000015];
ll n,m,sum;
ll has[2000015];
string s;
ll find(ll x)
{
return x==fa[x]?x:fa[x] = find(fa[x]);
}
void mul(ll x,ll y)//乘
{
mu[find(x)] = (mu[find(x)]*mu[find(y)])%mod;
mu[find(x)]%=mod;
fa[find(y)] = find(x);
}
ll qmi(ll a, ll b, ll p)//快速幂
{
ll res = 1 % p;
a %= p;
while (b > 0)
{
if(b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int main(){
cin>>n>>m;
for(int i = 1;
i<=n+10;
++i)
fa[i] = i;
cin>>s;
for(int i = 1;
i<=n;
++i)
{
cin>>a[i];
a[i]%=mod;
mu[i] = a[i];
if(i>1&&s[i-2]=='*')
mul(i,i-1);
}
for(int i = 1;
i<=n;
++i)
{
if(!has[find(i)])
{
sum = (sum+mu[find(i)])%mod;
has[find(i)] = 1;
}
}
for(int i = 1;
i<=m;
++i)
{
ll x,y;
cin>>x>>y;
ll c = y-a[x];
ll xx = find(x);
//下面这条式子乘和加都适合
sum = (sum+mod+(c*((mu[xx]*qmi(a[x],mod-2,mod))%mod)%mod)%mod)%mod;
//修改总和
cout< 推荐阅读
- LeetCode编程题解法汇总|力扣解法汇总720-词典中最长的单词
- 蓝桥杯|蓝桥杯——1.5递归实现组合型枚举
- 东数西算加快云网与数据融合 天翼云架起云间高速
- BEEM061
- 图论|通信线路「分层图最短路」||「二分答案 + 巧妙的建图跑最短路」
- 学习记录|393. UTF-8 编码验证
- leetcode|leetcode 543（二叉树的直径）
- Codeforces|Fault-tolerant Network（连通块/贪心）
- 算法|K-means，K-means++方法详解-机器学习分类问题常见算法