#P15431. [蓝桥杯 2025 国 Python B] 派对邀请方案

[蓝桥杯 2025 国 Python B] 派对邀请方案

说明

蓝桥公司坐落在云端之城,拥有 20252025 名员工,每位员工都有一个唯一的编号,从 1120252025。每年,公司都会举办一场盛大的派对,邀请部分员工参加,以增强团队凝聚力。

在公司的组织结构中,对于每个编号为 xx 的员工,他的直属上司的编号是 2x2x。为保持派对的轻松氛围,公司规定:若员工 xx 受邀参加派对,则其直属上司 2x2x 不得受邀。这一规则源于去年的派对,一位员工与其上司同时出现,导致了尴尬的“汇报式聊天”,破坏了派对的欢乐气氛。

现在,你的任务是计算有多少种邀请方案,使得对于任何被邀请的员工 xx,其直属上司 2x2x 未被邀请。由于答案可能很大,你只需给出其对 109+710^9 + 7 取余后的结果即可。邀请方案指选择员工参加派对的组合(不受邀请顺序影响),满足上述规则。例如:

  • 邀请 {1,3,5,7,9}\{1, 3, 5, 7, 9\} 是合法方案,因为员工 1,3,5,7,91, 3, 5, 7, 9 的上司均未被邀请。
  • 邀请 {1,2}\{1, 2\} 不合法,因为员工 11 的上司 22 被邀请了。
  • 不邀请任何员工(空集)也是合法方案,因为无员工被邀请,规则自然满足。

输出格式

这是一道结果填空题,你只需要算出结果后提交即可。本题的结果为一个范围在 00109+610^9 + 6 的整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。