A Rikka with Lowbit
链接: https://ac.nowcoder.com/acm/contest/33551/A
题意:首先教会了你lowbit的概念和用法(其实并没有什么用)。有t组数据,对于每组数据,数组a有n个非负整数,有m个操作。题目定义了一个函数
f(x):如果x为0,则返回0。否则返回x-lowbit(x)或x+lowbit(x),返回这两种情况的概率都是二分之一。
接下来定义了两个操作:
- 对区间[L,R]的各个数都进行一遍f(x);
- 查询区间[L,R]的值((a[l]+a[l+1]+……+a[r]) * 2^(n*m))。
数据范围:
(1 ≤ t ≤ 3);
(1 ≤ n,m ≤ 1e5);
(1 ≤ Ai ≤ 1e8);
(1 ≤ L ≤ R ≤ n);
思路:不难发现,x不管经过几次f(x)的操作,其期望值永远不变,所以我们可以忽视操作1,只要输出操作2对应区间的值就行了。但是因为n和m的数据范围都是1e5,每次遍历一遍区间L到R,最坏情况时间复杂度是O(10e10),会TLE,所以用先用前缀和记录所有值之和,之后只要用O(m)的时间就可以完成。
知识点:前缀和,思维题,lowbit(吓唬你的)。
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ULL unsigned long long
#define endl '\n'
#define LL long long
#define PII pair<int,int>
const int N = 100010;
const LL mod = 998244353;
// #define x first
// #define y second
int t,n,m;
int a[N],s[N];
int fastpow(int a,int x){
int res=a,ans=1;
while(x){
if(x&1) ans=ans*res%mod;
res=res*res%mod;
x>>=1;
}
return ans;
}
signed main()
{
cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i];
int p,l,r;
for(int i=0;i<m;i++){
cin>>p>>l>>r;
if(p==2){
int w=(s[r]-s[l-1])%mod;
int ans=w*fastpow(2,n*m)%mod;
cout<<ans<<endl;
}
}
}
}