{"problem":{"name":"BZOJ2839 集合计数","description":{"content":"一个有 $N$ 个元素的集合有 $2^N$ 个不同子集（包含空集），现在要在这 $2^N$ 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 $K$，求取法的方案数，答案模 $10^9+7$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10596"},"statements":[{"statement_type":"Markdown","content":"一个有 $N$ 个元素的集合有 $2^N$ 个不同子集（包含空集），现在要在这 $2^N$ 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 $K$，求取法的方案数，答案模 $10^9+7$。\n\n## Input\n\n一行两个整数 $N,K$。\n\n## Output\n\n一行一个整数表示答案。\n\n[samples]\n\n## Background\n\n题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。\n\n## Note\n\n**【样例解释】**\n\n假设原集合为 $\\{A,B,C\\}$，则满足条件的方案为：$\\{AB,ABC\\}$，$\\{AC,ABC\\}$，$\\{BC,ABC\\}$，$\\{AB\\}$，$\\{AC\\}$，$\\{BC\\}$\n\n**【数据范围】**\n\n对于 $100\\%$ 的数据，$1\\leq N\\leq 1000000$，$0\\leq K\\leq N$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10596","tags":["O2优化","容斥原理"],"sample_group":[["3 2","6"]],"created_at":"2026-03-03 11:09:25"}}