NC17507. 发电
描述
输入描述
第一行有2个正整数n，m，分别表示发电机数量和操作数。
接下来m行，每行有3个正整数，x, y, z。
x=1时，HtBest镶嵌为第y台发电机镶嵌了一个等级为z的神力水晶，
x=2时，HtBest为第y台发电机拆掉了一个等级为z的神力水晶，
x=3时，HtBest想知道[y,z]的发电机效率的乘积。
输出描述
对于每个x=3的操作，输出一行，表示[y,z]的发电机的效率的乘积。
由于输出过大，你需要对输出结果模1000000007（1e9+7）。
示例1
输入:
4 4 1 2 3 3 1 4 2 2 3 3 1 4
输出:
3 1
说明:
操作1之后，每台发电机效率：1 3 1 1示例2
输入:
4 4 1 2 2 1 2 3 1 3 4 3 1 4
输出:
24
说明:
操作1之后，每台发电机效率：1 2 1 1C++14(g++5.4) 解法, 执行用时: 386ms, 内存消耗: 20316K, 提交时间: 2020-10-13 21:00:05
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1000005;
vector<int>c(maxn,1);
int n,m,op,x,y;
ll qpow(ll x,ll y){
ll res = 1;
while(y){
if(y&1) res = res*x%mod;
x = x*x%mod;
y >>= 1;
}
return res;
}
int lowbit(int x){return x&(-x);}
void mult(ll x,ll lev){
while(x <= n){
c[x] = c[x]*lev%mod;
x += lowbit(x);
}
}
ll query(ll x){
ll res = 1;
while(x){
res = res*c[x]%mod;
x -= lowbit(x);
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
while(m--){
scanf("%d%d%d",&op,&x,&y);
if(op == 1) mult(x,y);
if(op == 2) mult(x,qpow(y,mod-2));
if(op == 3) printf("%lld\n",query(y)*qpow(query(x-1),mod-2)%mod);
}
}
C++11(clang++ 3.9) 解法, 执行用时: 406ms, 内存消耗: 4956K, 提交时间: 2018-08-18 19:43:16
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000005
#define ll long long
#define P 1000000007
int t[MAXN],n,m,i,j,k,x,y;
int Pow(int x,int y)
{
int s=1;
for(;y;y>>=1,x=(ll)x*x%P)if(y&1)s=(ll)s*x%P;
return s;
}
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)t[i]=1;
while(m--)
{
scanf("%d%d%d",&i,&j,&k);
if(i==1)for(;j<=n;j+=j&-j)t[j]=(ll)t[j]*k%P;
else if(i==2)for(k=Pow(k,P-2);j<=n;j+=j&-j)t[j]=(ll)t[j]*k%P;
else
{
for(x=y=1;k;k^=k&-k)x=(ll)x*t[k]%P;
for(j--;j;j^=j&-j)y=(ll)y*t[j]%P;
x=(ll)x*Pow(y,P-2)%P;
printf("%d\n",x);
}
}
return 0;
}