HBC212002致两千年后的你题解

想要成为编程高手？那就来试试全网最全C++题库，让您在练习中快速成长。

小宝给你了nnn个数 a1,2...na_{1,2...n}a1,2...n，同时他对于非空集合SSS，定义f0f_0f0表示其是否合法，其中f0f_0f0的值关乎于两个常数xxx 和PPP ， 形式化的说，集合SSS合法当且仅当存在一组系数ccc使得： ≡xbiggequiv xpmod P≡x 此时f0=1f_0=1f0=1，否则f0=0f_0=0f0=0 对于k≥1kge 1k≥1 ，定义fk=∑TS,T≠fk1f_k=sum_{Tsubseteq S,Tne varnothing} f_{k-1}fk=∑TS,T=fk1，即fkf_kfk为SSS的所有子集T{T}T 的 fk1f_{k-1}fk1的和， 现给定nnn个数a1...na_{1...n}a1...n，进行TTT 组查询，每次给定x,k,P{x,k,P}x,k,P ，求 fkf_kfk，其中U{U}U 表示全集，由于结果可能很大，答案需要对109+710^9+7109+7取模。

小宝给你了 nnn 个数 a1,2...na_{1,2...n}a1,2...n​，同时他对于非空集合 SSS ，定义 f0(S)f_0(S)f0​(S) 表示其是否合法，其中  f0(S)f_0(S)f0​(S) 的值关乎于两个常数  xxx  和  PPP  。 形式化的说，集合 SSS 合法当且仅当存在一组系数 ccc 使得： (∑i∈Sai×ci)≡x(modP)bigg(sum_{iin S} a_itimes c_ibigg)equiv xpmod P(∑i∈S​ai​×ci​)≡x(modP) 此时 f0(S)=1f_0(S)=1f0​(S)=1 ，否则 f0(S)=0f_0(S)=0f0​(S)=0  对于 k≥1kge 1k≥1  ，定义 fk(S)=∑T⊆S,T≠∅fk−1(T)f_k(S)=sum_{Tsubseteq S,Tne varnothing} f_{k-1}(T)fk​(S)=∑T⊆S,T​=∅​fk−1​(T)，即 fk(S)f_k(S)fk​(S) 为 SSS 的所有子集 T{T}T 的 fk−1(T)f_{k-1}(T)fk−1​(T) 的和。 现给定 nnn 个数  a1...na_{1...n}a1...n​，进行 TTT 组查询，每次给定 x,k,P{x,k,P}x,k,P ，求 fk(U)f_k(U)fk​(U)，其中 U{U}U 表示全集。由于结果可能很大，答案需要对 109+710^9+7109+7 取模。

标签： HBC212002致两千年后的你题解