做字幕模板下载网站/营销策略手段有哪些

加法和乘法是适用同余模定理的，但除法不能。

原题连接：http://acm.fzu.edu.cn/problem.php?pid=2297

**首先我们看到题目中有取余的要求。

加法和乘法是适用同余模定理的，但除法不能。所以我们一般把除法转换成“被除数乘以除数的逆元”的乘法形式，但是同只有行列相同的矩阵才有逆矩阵一样，倘若那个“除数”与输入的“MOD（取余数）”不是互质数，那么这个逆元不存在，无法进行运算。所以这里不能用逆元解题。

这个时候，线段树的神秘作用就显现出来了。它的头结点承载的值（根节点-root）总是代表着下边所有节点“作用的总和”，比如说，加法中，root节点就是所有数据的和，最大最小值计算中，root节点承载所有数据的最大最小值，同样，我们把一个数拆成各种因子，放在线段树中，root节点自然有所有数的积，恰好出现的所有数只会被除一次，所以每一次除法就是把一个因数变成1使之失去作用。
那么这个题就有如下的思路：
准备好线段树建造函数（这里是construction（））和线段树单点修改函数(这里是quest_and_modify（））,由于一组数据只会有Q行操作，所以说这个线段树至多承载Q个数，所以对1-Q的数据建立线段树即可，初始化各点数据为1。
设当前输入到第line(i)行（1<=i<=Q）在乘法操作中，每输入一个数就调用单点修改函数在第line(i)个节点中乘上输入的数，此时它就是一个因子，对于除法操作，就是把指定位置的因子变成1。每次操作后直接输出ROOT节点（1号节点）承载的值即可。**

#include <iostream>
#include <cstdio>
//#include <bits/stdc++.h>
#include <map>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cmath>
#define DETERMINATION main
#define lldin(a) scanf("%lld",&a)
#define din(a) scanf("%d",&a)
#define printlnlld(a) printf("%lld\n",a)
#define printlnd(a) printf("%d\n",a)
#define printlld(a) printf("%lld",a)
#define printd(a) printf("%d",a)
#define reset(a,b) memset(a,b,sizeof(a))
const int INF=0x3f3f3f3f;
using namespace std;
const double PI=acos(-1);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod=1000000007;
///Schlacht von Stalingrad
/**Although there will be many obstructs ahead,
the desire for victory still fills you with determination..**/
struct node
{ll left,right,value;
}nodes[1000000];//结构体作节点来建树
ll query,modu;
void construction(ll current,ll left,ll right)//线段树建造函数
{nodes[current].left=left,nodes[current].right=right;if(left==right){nodes[current].value=1;return ;}ll mid=(left+right)>>1;construction(2*current,left,mid);construction(2*current+1,mid+1,right);nodes[current].value=(nodes[2*current].value*nodes[2*current+1].value)%modu;
//注意上式的取余.
}
void quest_and_modi(ll current,ll location,ll number)//线段树单点修改函数
{if(nodes[current].left==nodes[current].right){nodes[current].value=number;return ;}ll mid=(nodes[current].left+nodes[current].right)>>1;if(mid<location)quest_and_modi(2*current+1,location,number);elsequest_and_modi(2*current,location,number);nodes[current].value=(nodes[2*current].value*nodes[2*current+1].value)%modu;
}
int DETERMINATION()
{cin.ios::sync_with_stdio(false);//取消cin与scanf的同步，加快输入（不取消TLE，取消986ms（限时2000ms））ll t;cin>>t;while(t--){reset(nodes,0);cin>>query>>modu;construction(1,1,query);//cout<<"!"<<endl;for(int i=1;i<=query;i++){char com;cin>>com;ll key;cin>>key;if(com=='M'){quest_and_modi(1,i,key);cout<<nodes[1].value<<endl;//头节点的值就是题目给定的x当前的值}else{quest_and_modi(1,key,1);cout<<nodes[1].value<<endl;}}}return 0;
}

原文链接：https://blog.csdn.net/weixin_43874261/article/details/89533101