牛牛的奇偶子序列

[编程题]牛牛的奇偶子序列

热度指数：419 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛有一个长度为 $\mathit n$ 的数组，牛妹给出 $\mathit m$ 个询问，询问有 $\text 2$ 种类型：
$\text 1~ l ~r$ :询问区间 $\text [l,r]$ 内有多少子序列的乘积为奇数

$\text 2~ l~ r$ :询问区间 $\text [l,r]$ 内有多少子序列的乘积为偶数

某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。

输入描述:

第一行个整数,表示数组长度和询问个数。
接下来一行给出个空格隔开的数。
接下来行每行三个整数表示操作类型。
。

输出描述:

输出行，每行表示对应询问的答案，因为答案可能很大，输出对取模的结果。

示例1

输入

输出

3
4

说明

第一个询问中合法的子序列为:{1},{3},{1,3}。第二个询问中合法的子序列为：{2},{1,2},{2,3},{1,2,3}

算法知识视频讲解

JavaScript

努力成为程序媛啊

var readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})
let count = 0;
let n , m;
let charu = [];
let f = [];
rl.on('line',function(line){
    count++;
    if(count == 1){
        let arr = line.split(' ').map(Number);
        n = arr[0];
        m = arr[1];
    }else if(count == 2){
        let arr2 = line.split(' ').map(Number);
        for(let i = 0; i < n; i++){
            f.push(arr2[i] % 2);  // 具体是什么数字不重要，只是为了辨别奇偶
        }
    }else if(count >= 3 && count < 2 + m){
        charu.push(line);
    }else if(count == 2 + m){
        charu.push(line);
        const g = new Array(n + 1)
        g[0] = 0;
        for(let i = 1; i <= n; i++) {
            g[i] = g[i - 1] + f[i - 1];
        }
        for(let i = 0; i < m; i++){
            let temp = charu[i].split(' ').map(Number);
            let l = temp[1];
            let r = temp[2];
            let odd = g[r] - g[l - 1];
            if(temp[0] == 1){
                let res = mypow(2,odd) - 1
                console.log(res);
            }else{
                let even = mypow(2, r - l + 1) - mypow(2, odd)
                if (even < 0) {
                    even = even + 1000000007;
                }
                console.log(even)
            }
        }
    }
})
function mypow (basic,exp){
    let res = 1;
    while(exp > 0){
        res = (res * basic) % 1000000007;
        exp--;
    }
    return res;
}

编辑于 2022-04-18 21:34:20 回复(1)