牛牛的奇偶子序列

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

热度指数：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}

算法知识视频讲解

桜吹雪

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int cal(int a, int n) {
    int ans = 1;
    while (n) {
        if (n & 1) {
            ans = ((long long)ans * a) % MOD;
            //if (ans < 0) ans += MOD;
        }
        a = (long long)a * a % MOD;
        //if (a < 0) a += MOD;
        n >>= 1;
    }
    return ans;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> f;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        f.push_back(a % 2);
    }
    vector<int> g(n + 1);
    for (int i = 1; i <= n; i++) {
        g[i] = g[i - 1] + f[i - 1];
    }
    for (int i = 0; i < m; i++) {
        int op, l, r;
        cin >> op >> l >> r;
        int odd = g[r] - g[l - 1];
        //cout << "odd =" << " " << odd << endl;

        if (op == 1) {
            cout << cal(2, odd) - 1 << endl;
        }
        else {
            int even = cal(2, r - l + 1) - cal(2, odd);
            if (even < 0) even += MOD;
            cout << even << endl;
        }
    }
    return 0;
}

发表于 2022-04-18 17:23:35 回复(0)

JCoder

乘积为奇数的子序列一定是全都是奇数，所以是 2^(奇数数量) - 1

求 [l,r] 内有多少个奇数可以将所有数字模2，然后求前缀和

如果就是求奇数，直接输出

求偶数就再求一个全部子序列的数量：2^(r - l + 1) - 1，再减去乘积为奇数的子序列数量

至于求2的多少次幂可以O(n)预处理，也可以快速幂

发表于 2021-08-12 19:28:42 回复(0)

牛客350575121号

这道题可不可以看成是求子集然后看子集乘积的奇偶

发表于 2023-03-07 18:08:48 回复(0)

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)