万网可以花钱做网站,昆明网站推广优化公司,公司推广咨询,wordpress主题音乐正题 题目大意
有nnn个箱子放了若干个玩具#xff0c;要求选择一些箱子使得mmm种玩具都有#xff0c;求方案总数。 解题思路
设fSf_SfS表示选择只有在集合为SSS的方案数。 然后答案考虑容斥#xff0c;那么答案就是∑S(2(f(∼S))−1)∗(−1)∣S∣\sum_S (2^{(f_{(\sim S…正题 题目大意
有nnn个箱子放了若干个玩具要求选择一些箱子使得mmm种玩具都有求方案总数。 解题思路
设fSf_SfS表示选择只有在集合为SSS的方案数。 然后答案考虑容斥那么答案就是∑S(2(f(∼S))−1)∗(−1)∣S∣\sum_S (2^{(f_{(\sim S)})}-1)*(-1)^{|S|}S∑(2(f(∼S))−1)∗(−1)∣S∣ 我们将集合的表示状压起来。 现在考虑如何快速求fff数组首先fScSf_Sc_SfScS(cSc_ScS表示集合是SSS的箱子个数)。 然后分治每次分治时rrr肯定是若干个111 比如当l0,r11111l0,r11111l0,r11111时左边边都是0XXXX0XXXX0XXXX而右边是1XXXX1XXXX1XXXX。也就是右边是左边第一位变成一。那么对于每个区间就有
fi∑mfi−ml−1(igt;m)f_i\sum_mf_{i-ml-1}(igt; m)fim∑fi−ml−1(im)
时间复杂度O(2mlog2m)O(2^m\ log\ 2^m)O(2m log 2m) codecodecode
#includecstdio
using namespace std;
const int M(120)10,XJQ1e97;
int n,m,f[M],w[M],p[M],ans,v[M],MS;
void apart(int l,int r)
{if(lr){f[l]v[l];return; } int m(lr)1;apart(l,m);apart(m1,r);for(int il;im;i)f[im-l1]f[i];
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){int z0,k;scanf(%d,k);while(k--){int x;scanf(%d,x);z|(1x-1);}v[z];}MS1m;for(int i0;iMS;i)w[i]w[i1]^(i1);p[0]1;for(int i1;in;i)p[i](p[i-1]1)%XJQ;apart(0,MS-1);for(int i0;iMS;i)(ans((w[i]?-1:1)*(p[f[MS-i-1]]-1)))%XJQ;printf(%d,(ansXJQ)%XJQ);
}
