Xiao Sha's arithmetic problem solving report

label ： Inverse element

Topic link

source ： Cattle from

Their thinking ：

Start with an example ,
Give the formula 1+1+3 * 1+1 * 6 * 7;
We can divide the formula into 1,1,3 * 1,1 * 6 * 7, Four parts exist num 1~4 in
Set the pointer number to mark the group to which each number belongs , Remember that the sum at this time is ans;
When we Jiang's sixth digit 6 Change it to 7 when ,
First of all, from the ans Subtract from num[4], Ran Ling num[4] / 6 * 7, Re order ans += num[4] that will do
Then I found myself digging

Inverse element

The problem is that the subject data is too large and modular operation is carried out , The order of modulo and division cannot be changed
For example, we give the title mod Reduce to 5
Calculate according to the above method
num[4]=((16%5)7)%5=2
After change num[4]=2 / 6 * 7 % 5 =
2/6 In addition, the problems are exposed To prevent this, we use the inverse element
I am also a beginner of inverse yuan , Is not very good , Don't understand
I mainly refer to the following article
https://zhuanlan.zhihu.com/p/378728642
According to Fermat's theorem When a And b Coprime ：

Apply it to the above example to find 6 The inverse element of is 216;
num[4]=2216%57%5=4;
num[4]=7*7%5=4;
That's right
We can make bold guesses 1e9+7 Prime number , Get by fast power a model b Inverse element

Code implementation ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int N = 1e6+8;
char s[N];
ll num[N],pos[N],n,q,a[N];
ll ksm(ll a, ll b) {
    ll ans = 1;
    while(b){
		if (b & 1) (ans *= a) %= mod;
		(a *= a) %= mod; 
		b >>= 1;
	}
    return ans;
}
int main()
{
    cin>>n>>q;
    scanf("%s",s+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    int cnt=1;
    num[1]=a[1];
    pos[1]=1;
    for(int i=2;i<=n;i++){
        if(s[i-1]=='*'){
            pos[i]=cnt;
            num[cnt]=num[cnt]*a[i]%mod;
        }
        else{
            num[++cnt]=a[i];
            pos[i]=cnt;
        }
    }
    ll ans = 0,x=0,y=0;
    for(int i=1;i<=cnt;i++)  (ans+=num[i]) %= mod;
    while(q--){
        cin>>x>>y;
        ans=(ans-num[pos[x]]+mod)%mod;
        num[pos[x]]=num[pos[x]]*ksm(a[x],mod-2)%mod*y%mod;
        ans=(ans+num[pos[x]])%mod;
        a[x]=y;
        cout<<ans<<endl;
    }
}