小沙的算数--并查集 (联通块)_小沙的算术

题目

小沙不会计数，所以他想从小学数学开始学起，今天老师布置了一大堆算数题，但爱耍小聪明的小沙发现这么多的算数题中，他们中间的符号都是+++或者×\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的值

输出描述:

对于每次查询，回答出整个算式的答案 每个答案占一行

（本题中的每次查询均不独立，也就是说每次查询修改之后的数，都会永远的修改）

样例输入

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<stdio.h>
#include<iostream>
#include<cstring>
#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<<sum%mod<<endl;
        mu[xx] = (mu[xx]*qmi(a[x],mod-2,mod)%mod)*y%mod;//换联通块的值 
        a[x] = y%mod;//换原数组的值 
    }
   return 0;
}