牛客网暑期ACM多校训练营(第十场)A(Rikka with Lowbit)

2024-01-14 21:48

本文主要是介绍牛客网暑期ACM多校训练营(第十场)A(Rikka with Lowbit),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


题目描述

Today, Rikka is going to learn how to use BIT to solve some simple data structure tasks. While studying, She finds there is a magic expression in the template of BIT. After searching for some literature, Rikka realizes it is the implementation of the function .

is defined on all positive integers. Let a1...am be the binary representation of x while a1 is the least significant digit, k be the smallest index which satisfies ak = 1. The value of is equal to 2k-1.

After getting some interesting properties of , Rikka sets a simple data structure task for you:

At first, Rikka defines an operator f(x), it takes a non-negative integer x. If x is equal to 0, it will return 0. Otherwise it will return or , each with the probability of .

Then, Rikka shows a positive integer array A of length n, and she makes m operations on it.

There are two types of operations:
1. 1 L R, for each index i ∈ [L,R], change Ai to f(Ai).
2. 2 L R, query for the expectation value of . (You may assume that each time Rikka calls f, the random variable used by f is independent with others.)

输入描述:

The first line contains a single integer t(1 ≤ t ≤ 3), the number of the testcases.The first line of each testcase contains two integers n,m(1 ≤ n,m ≤ 105). The second line contains n integers Ai(1 ≤ Ai ≤ 108). And then m lines follow, each line contains three integers t,L,R(t ∈ {1,2}, 1 ≤ L ≤ R ≤ n).

输出描述:

For each query, let w be the expectation value of the interval sum, you need to output . It is easy to find that w x 2nm must be an integer.

输入

1
3 6
1 2 3
1 3 3
2 1 3
1 3 3
2 1 3
1 1 3
2 1 3

输出

1572864
1572864
1572864

题意:(签到题)给出一个数组,两种操作。

1,修改一个区间的数,如果a[i]=0,a[i]=0。否则有1/2几率变为a[i]+lowbit(a[i]),有1/2几率变为a[i]-lowbit(a[i])。

2,求区间期望和。

思路:因为是求期望所以每一个点上的数期望为(1/2)*(x+lowbit(x))+(1/2)*(x-lowbit(x))=x,期望相当于没变,那么题意也就转化成了只求最初的数组区间和了。(水题)

代码:

#include<bits/stdc++.h>
#define PI acos(-1)
#define ll long long
#define inf 0x3f3f3f3f
#define ull unsigned long long
using namespace std;
const ll mod=998244353;
ll sum[100005];
long long qpow(long long a,long long b)
{
    a=a%mod;
    long long ans=1;
    while(b)
    {
        if(b&1)
        {
            ans=(ans*a)%mod;
            b--;
        }
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
int main()
{
    int T;
    ll n,m;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld",&n,&m);
        sum[0]=0;
        for(int i=1;i<=n;i++)
        {
            ll x;
            scanf("%lld",&x);
            sum[i]=(sum[i-1]+x)%mod;
        }
        ll op,l,r;
        int y=m;
        while(y--)
        {
            scanf("%lld%lld%lld",&op,&l,&r);
            if(op==1) continue;
            else if(op==2)
            {
                ll ans=(sum[r]-sum[l-1])%mod;
                ans=ans*qpow(2,n*m)%mod;
                cout<<(ans+mod)%mod<<endl;
            }
        }
    }
}

这篇关于牛客网暑期ACM多校训练营(第十场)A(Rikka with Lowbit)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/606635

相关文章

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

暑期学习总结

iOS学习 前言无限轮播图换头像网络请求按钮的configuration属性总结 前言 经过暑期培训,完成了五个项目的仿写,在项目中将零散的内容经过实践学习,有了不少收获,因此来总结一下比较重要的内容。 无限轮播图 这是写项目的第一个难点,在很多项目中都有使用,越写越熟练。 原理为制造两个假页,在首和尾分别制作最后一页和第一页的假页,当移动到假页时,使用取消动画的方式跳到

代码训练营 Day26 | 47.排序II | 51. N-皇后 |

47.排序II 1.跟46题一样只不过加一个树层去重 class Solution(object):def backtracking(self,nums,path,result,used):# recursion stopif len(path) == len(nums):# collect our setresult.append(path[:])return for i in range(

代码随想录训练营day37|52. 携带研究材料,518.零钱兑换II,377. 组合总和 Ⅳ,70. 爬楼梯

52. 携带研究材料 这是一个完全背包问题,就是每个物品可以无限放。 在一维滚动数组的时候规定了遍历顺序是要从后往前的,就是因为不能多次放物体。 所以这里能多次放物体只需要把遍历顺序改改就好了 # include<iostream># include<vector>using namespace std;int main(){int n,m;cin>>n>>m;std::vector<i

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

牛客小白月赛100(A,B,C,D,E,F三元环计数)

比赛链接 官方讲解 这场比较简单,ABC都很签到,D是个不太裸需要预处理的 B F S BFS BFS 搜索,E是调和级数暴力枚举,F是三元环计数。三元环考的比较少,没见过可能会偏难。 A ACM中的A题 思路: 就是枚举每个边变成原来的两倍,然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2,比如 1 4 8 这组数据,也不能只给第二短边乘 2 2 2,比

代码随想录算法训练营Day37|完全背包问题、518.零钱兑换II、377. 组合总和 Ⅳ、70. 爬楼梯(进阶版)

完全背包问题                  和01背包最大区别就是一个物品可以重复放多次,因此遍历空间时可以从前往后。 import java.util.*;public class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt

【代码随想录训练营第42期 续Day52打卡 - 图论Part3 - 卡码网 103. 水流问题 104. 建造最大岛屿

目录 一、做题心得 二、题目与题解 题目一:卡码网 103. 水流问题 题目链接 题解:DFS 题目二:卡码网 104. 建造最大岛屿 题目链接 题解:DFS  三、小结 一、做题心得 也是成功补上昨天的打卡了。 这里继续图论章节,还是选择使用 DFS 来解决这类搜索问题(单纯因为我更熟悉 DFS 一点),今天补卡的是水流问题和岛屿问题。个人感觉这一章节题对于刚

【转载】ACM感悟

今天看了一篇我们学校前辈的ACM的感悟,觉得写的十分有道理,这里转载,文章还会不断的改进和更新。 原文链接:http://www.cnblogs.com/Chierush/p/3760870.html?ADUIN=1339764596&ADSESSION=1401536826&ADTAG=CLIENT.QQ.5329_.0&ADPUBNO=26349 声明:本文是写给弱校ACM新手的一点