#3160. 集合划分计数 暂未评定

时间限制:7000 ms 内存限制:514 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

这是一道模板题。比此题更加模板的在这里

给定一个集合 和一个 上的集合族

一个划分 的一个子族,满足 中所有集合的并为 ,任意两个集合不相交。

求大小不大于 的划分的数量

两个划分 不同,当且仅当存在 使 不同当且仅当

输入格式

行:

行: 二进制第 位为 表示 ,为 表示

输出格式

个非负整数,表示大小不大于 的划分的数量

样例

样例输入

4 8 2
7 10 8 11 5 15 4 5

样例输出

5

数据范围与提示

子任务

  1. (16 分)
  2. (20 分)
  3. (14 分)
  4. (25 分)
  5. (25 分)没有附加限制