#P13769. [2019年备战北大冬令营]飞机

    ID: 12977 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-SOS DP乘法原理容斥原理子掩码递推 (s-1)&mask秦九韶算法连续点值插值

[2019年备战北大冬令营]飞机

题目描述

飞机的关键部位数 pp 可以是 00 到 mm 中的任意一个整数。对于固定的 pp,将这些部位视为彼此可区分。有 nn 个彼此可区分的零件,每个零件可以被丢弃,或装在 pp 个部位中的任意一个。每个部位可以装多个零件,也可以空着。

飞机的上天值是所有已安装零件的权值按位或所得的结果。没有安装任何零件时,上天值为 00。求对所有 p=0,…,mp=0,\ldots,m 的方案中,上天值恰好为 tt 的方案总数。

输入格式

第一行四个整数 n,m,t,kn,m,t,k,其中 k−1k-1 是零件权值的最大可能值。第二行 nn 个整数,依次表示各零件的权值 aia_i。

输出格式

输出一行一个整数,表示答案对 998244353998244353 取模的结果。

数据范围

所有数据满足 n≤7000n\le7000,0≤m≤1090\le m\le10^9,k=2gk=2^g,0≤g≤210\le g\le21,0≤t,ai<k0\le t,a_i<k。

子任务 分值 附加限制
1 20 n,m≤15n,m\le15
2 n,m≤100n,m\le100,k≤128k\le128
3 m≤5000m\le5000
4 n≤3000n\le3000
5 无

原 PDF 题面 · 原 PDF 题解