P3794 签到题IV

    • 55通过
    • 353提交
  • 题目提供者 Created_equal1 管理员
  • 评测方式 云端评测
  • 标签 枚举,暴力 线段树 进制 洛谷原创 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    这场月赛好像其他题背景都很长,这题就不写背景了。

    题目描述

    给定一个长度为n的序列 $a_1,a_2...a_n$ ,其中每个数都是正整数。

    你需要找出有多少对(i,j), $1 \leq i \leq j \leq n$ 且 $gcd(a_i,a_{i+1}...a_j)~xor~(a_i~or~a_{i+1}~or~...~or~a_j)=k$ ,其中xor表示二进制异或,or表示二进制或。

    输入输出格式

    输入格式:

    第一行两个整数n、k。

    第二行n个整数 $a_1,a_2...a_n$ 。

    输出格式:

    输出合法的(i,j)的对数。

    输入输出样例

    输入样例#1: 复制
    5 6
    2 4 3 4 2
    输出样例#1: 复制
    8

    说明

    对于30%的数据, $n \leq 500$ 。

    对于60%的数据, $n \leq 100000$ 。

    对于100%的数据, $1 \leq n,a_i \leq 500000$ 。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。