{"problem":{"name":"[蓝桥杯 2018 省 B] 乘积最大","description":{"content":"给定 $N$ 个整数 $A_1, A_2,\\cdots, A_N$。请你从中选出 $K$ 个数，使其乘积最大。   请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 $1000000009$（即 $10^9+9$）的余数。   注意，如果 $X<0$， 我们定义 $X$ 除以 $1000000009$ 的余数是 $0-((0-x)\\bmod 1000000009)$。 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8669"},"statements":[{"statement_type":"Markdown","content":"给定 $N$ 个整数 $A_1, A_2,\\cdots, A_N$。请你从中选出 $K$ 个数，使其乘积最大。  \n\n请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 $1000000009$（即 $10^9+9$）的余数。  \n\n注意，如果 $X<0$， 我们定义 $X$ 除以 $1000000009$ 的余数是 $0-((0-x)\\bmod 1000000009)$。\n\n## Input\n\n第一行包含两个整数 $N$ 和 $K$。\n\n以下 $N$ 行每行一个整数 $A_i$。  \n\n## Output\n\n一个整数，表示答案。\n\n[samples]\n\n## Note\n\n对于 $40\\%$ 的数据，$1\\le K\\le N\\le 100$。\n\n对于 $60\\%$ 的数据，$1\\le K \\le 1000$。\n\n对于 $100\\%$ 的数据，$1\\le K\\le N\\le 10^5$，$-10^5\\le A_i\\le 10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8669","tags":["贪心","2018","蓝桥杯省赛","分类讨论"],"sample_group":[["5 3 \n-100000   \n-10000   \n2   \n100000  \n10000","999100009"],["5 3 \n-100000   \n-100000   \n-2   \n-100000  \n-100000","-999999829"]],"created_at":"2026-03-03 11:09:25"}}