杭州微信建站,郑州网站制作价格,广州商砼建站规范,dw做网站需要数据库么C. 奇奇怪怪的魔法阵
题意#xff1a;
n个点m条边#xff0c;定义集合S为独立集#xff0c;当且仅当任意x,y∈S#xff0c;x与y之间没有边。空集也是独立集 现在对于每一个点的集合T#xff0c;有多少子集为独立集 设N0,1,…,n-1,AT∑S⊂T[S是独立集]A_{T}\sum_{S⊂T}[S…C. 奇奇怪怪的魔法阵
题意
n个点m条边定义集合S为独立集当且仅当任意x,y∈Sx与y之间没有边。空集也是独立集 现在对于每一个点的集合T有多少子集为独立集 设N0,1,…,n-1,AT∑S⊂T[S是独立集]A_{T}\sum_{S⊂T}[S是独立集]AT∑S⊂T[S是独立集]。对于每一个T⊂N求出ATA_TAT 1n26
题解
看这个数据范围就很明显复杂度是(126)正好1s内 而且肯定是dp转移但是还是不知道咋做看了题解恍然大悟
设dp[msk]表示msk的子集内独立集的个数。开始考虑转移在msk中随便选一个元素i。对于元素i有两种情况考虑i在不在独立集里如果不在的话i号点对其他点是没有影响的那么直接从dp[msk^(1i)]转移。如果在i号点的所有邻居都不能在独立集里设i号点及其邻居的节点集合为net[i]net[i]net[i],这种情况就从dp[msk⨁net[i]]dp[msk⨁net[i]]dp[msk⨁net[i]]转移即可 以上这是官方题集我现在还有很大的疑惑等想明白继续更新
代码
#includebits/stdc.h
using namespace std;
const int mod1e97;
int n,m,x,y,msk[55],dp[(126)10],fun[(125)10],id,ans;
int main()
{scanf(%d%d,n,m);for (int i0;in;i) msk[i]1i;for (int i1;im;i){scanf(%d%d,x,y);msk[x]|(1y);msk[y]|(1x);}for (int i0;in;i) fun[1i]i;dp[0]1;for (int i1;i(1n);i){idfun[i(-i)];//获取1的最低位 /*i^(1id)当前i的状态中去掉第id个 */ dp[i]dp[i^(1id)]dp[i^(imsk[id])];if (dp[i]mod) dp[i]-mod;}for (int i(1n)-1;i0;i--) ans(233ll*ansdp[i])%mod;printf(%d\n,ans);return 0;
}
