算法题详解

美团前端笔试

快速幂

题面背景

给定长度为n的数组,和m个查询,

每次查询里面输入一个x,使得出第x外的数都翻倍

最后输出数组的和(模1e9 + 7)

1 <= n , m <= 1e5,1 <= x <=n,数组内的值 <= 1e9

分析

纯暴力,直接双重循环,n的平方的复杂度,时间肯定超时了

所以使用到快速幂,可以logn解决翻倍的问题,记得主要取模,不要越界就好了

个人题解

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e5 + 10,P = 1e9 + 7;

int q[N],cnt[N];

ll qmi(int x,int k)
{
	ll res = x % P,t = 2;
		
	while(k)
	{
		if(k & 1)res = (res * t) % P;
		
		t = (t * t) % P;
		k >>= 1;
	}
	
	
	return res;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n,m;
	cin>>n>>m;

	for(int i = 1; i <= n; i ++ )
	{
		cin>>q[i];
		cnt[i] = m;
	}
	
	while(m -- )
	{
		int x;
		cin>>x;
		cnt[x] --;
	}
	
	ll ans = 0;
	
	for(int i = 1; i <= n; i ++ )
	{
		ans = (ans + qmi(q[i],cnt[i])) % P;
		// cout<<qmi(1,4)<<endl;
	}

	cout<<ans;
	return 0;
}

test