思路

关键在于分类讨论 要把所有可能性考虑到

看注释吧！

C++ 代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>

typedef long long LL;
using namespace std;

const long long MOD = 1000000009;
const int maxN = 100005;

int n, k;
vector<LL> pos, neg;//保存正数和负数的列表
LL ans;

/**
 * 将数组a中[start,end]区间内的数连乘起来
 * @param a
 * @param start
 * @param end
 * @param flag
 * @return
 */
LL mul(vector<LL> a, int start, int end) {
    LL ans = 1;

    for (int i = start; i <= end; ++i) {
        ans = ans * a[i] % MOD;
    }
    return ans;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        LL x;
        cin >> x;
        if (x > 0)pos.push_back(x);
        if (x < 0)neg.push_back(x);//只处理正数和负数，0不处理
    }
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());
/*===========下面开始分类讨论=========*/
    unsigned long sizeSum = pos.size() + neg.size();
//    1.正数和负数的个数不足k，必然有0的存在
    if (sizeSum < k) {
        ans = 0;
    }
//    2.正数和负数的个数恰好为k
    else if (sizeSum == k) {
//      2.1 k与n相等，必须选这k个数，没有0
        if (k == n) {
            ans = mul(pos, 0, pos.size() - 1) * mul(neg, 0, neg.size() - 1) % MOD;
        }
//      2.2 k<n，有0的存在
        else {
//          2.2.1 可得正数解当且仅当:正数全部选中，负数全部选中且为偶数个
            if (neg.size() % 2 == 0) {
                ans = mul(pos, 0, pos.size() - 1) * mul(neg, 0, neg.size() - 1) % MOD;
            } else {
//          2.2.2 负数是奇数个，全部选中结果为负数，不全部选中可得0，结果就是0
                ans = 0;
            }
        }
    } else {
//    3.正数和负数的个数大于k，情况比较复杂
//    sum>k
//      3.1 没有正数,负数和0中选k个
        if (pos.size() == 0) {
            if (k % 2 == 0) {//k是偶数
                ans = mul(neg, 0, k - 1);//正向选k个
            } else {
                if (sizeSum < n)//有0
                    ans = 0;
                else//没有0，必须从所有负数中选奇数个数=》连乘绝对值小的
                    ans = mul(neg, neg.size() - k, neg.size() - 1);//逆向选k个
            }
//      3.2 没有负数
        } else if (neg.size() == 0) {
            ans = mul(pos, pos.size() - k, pos.size() - 1);//逆向选k个
//      3.3 有正数也有负数
        } else {
            int posStart;int negEnd;
            if(k>=pos.size()) {//正数不足k个
    //          假定正数全部选中，剩余偶数个负数，等会再来挪动标尺
                if ((k - pos.size()) % 2 == 0) {
                    negEnd = k - pos.size() - 1;//负数选择的截止下标
                    posStart = 0;//正数选择的起始下标
                } else {
    //          剩余个数是奇数，正数先少选一个
                    posStart = 1;//正数选择的起始下标
                    negEnd = k - pos.size();//负数选择的截止下标
                }
            }else{//正数多余k个，假定从正数中先选最大的k个
//                if(k%2==0){ //k是偶数
                    negEnd=-1;
                    posStart = pos.size()-k;
//                }else{//k是奇数，先少选一个
//                    negEnd=-1;
//                    posStart = pos.size()-1-k;
//                }
            }
//          双标尺移动
            while (negEnd + 2 < neg.size() && posStart + 2 < pos.size() &&
                   neg[negEnd + 1] * neg[negEnd + 2] > pos[posStart] * pos[posStart + 1]) {
                negEnd += 2;
                posStart += 2;
            }
            ans = mul(neg,0,negEnd)*mul(pos,posStart,pos.size()-1)%MOD;
        }
    }
    cout<<ans<<endl;
    return 0;
}