我们做的网站是优化型结构,广州海珠建网站,医疗网站建设方案,服务平台名称大全正题 题目大意 nnn个数的一个集合#xff0c;求一个有多少个子集使得这个子集的所有子集的权值和的和是mmm的倍数 解题思路
考虑dp#xff0c;选中集合中每一个数的贡献次数是2∣S∣−12^{|S|-1}2∣S∣−1#xff0c;设fi,j,kf_{i,j,k}fi,j,k表示选到第iii#xff0c;现…正题 题目大意
nnn个数的一个集合求一个有多少个子集使得这个子集的所有子集的权值和的和是mmm的倍数 解题思路
考虑dp选中集合中每一个数的贡献次数是2∣S∣−12^{|S|-1}2∣S∣−1设fi,j,kf_{i,j,k}fi,j,k表示选到第iii现在选了jjj个数摸上mmm的余数是kkk。显然这个无法通过
考虑对mmm进行分类如果mmm是一个偶数那么加入一个新元素时相当于整个集合包括以后加入的都得乘以222那么我们可以让m/2m/2m/2即可。
如果mmm是一个奇数那么考虑总和sumsumsum如果sum%m≠0sum\% m\neq 0sum%m0那么显然sum∗2k≠0(k∈N)sum*2_{k}\neq 0(k\in N)sum∗2k0(k∈N)。然后我们可以发现jjj的上界就是mmm拥有的222质因子个数如果再大那么显然没有意义。
而kkk的上界是m2j−1\frac{m}{2^{j-1}}2j−1m如果按照张上下界来进行枚举那么时间复杂度为O(nm)O(nm)O(nm) codecodecode
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N5100,XJQ1e97;
int n,m,a[N],p[N],f[2][14][N*2],ans,M;
int main()
{freopen(data.txt,r,stdin);scanf(%d%d,n,m);p[0]1;for(int i1;in;i)scanf(%d,a[i]);for(int im*2;!(i1);i1,M);f[0][0][0]1;for(int i1;in;i){for(int j0,wm*2;jM;j,w1)for(int k0;kw;k)f[i1][j][k]f[~i1][j][k];for(int j0,wm*2;jM;j,w1){int now(jM)?(j):(j1);int mod(jM)?(w):(w/2);for(int k0;kw;k)(f[i1][now][(ka[i])%mod]f[~i1][j][k])%XJQ;}}for(int i1;iM;i)ans(ansf[n1][i][0])%XJQ;printf(%d,ans);
}
