列表

详情

NC227343. 奇奇怪怪的魔法阵

描述

小 L 有一个魔法阵，这个魔法阵是一个 个点 条边的无向图，无重边无自环。点的编号为 。

小 L 可以激活一些点，使魔法阵释放出强大的能量。一个激活的点的集合 能释放出强大的能量当且仅当 与 之间没有边，我们称这样的集合 为独立集。注意空集也为独立集。

现在小 L 想求对于每一个点的集合 ，有多少子集为独立集。设 ，。我们要对于每一个 ，求出 A_T 。

由于输出的数太多，你只需要输出对 数组哈希的结果就行了。

定义，我们要输出： 对 取模的结果。

输入描述

第一行两个数,，为点数和边数。

接下来  行，每行两个数，表示第 号节点和第 号节点有一条边，注意节点编号从开始数起。

保证给定的图没有自环和重边。

输出描述

输出仅一行一个数，即为  数组的哈希值。

示例1

输入: 

3 2
0 1
1 2

输出: 

102064182

说明:

独立集有 \emptyset,\{0\},\{1\},\{2\},\{0,2\}，所以A_{\emptyset}=1,A_{\{0\}}=2,A_{\{1\}}=2,A_{\{2\}}=2,A_{\{0,1\}}=3,A_{\{0,2\}}=4,A_{\{1,2\}}=3,A_{\{0,1,2\}}=5

答案为 233^0*1+233^1*2+233^2*2+233^3*3+233^4*2+233^5*4+233^6*3+233^7*5\equiv 102064182 ~ (mod~1e9+7)。

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 574ms, 内存消耗: 263032K, 提交时间: 2021-10-15 20:44:01 

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,ans,g[26],f[1<<26];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<26;i++)g[i]|=1<<i;
	for(int i=1,x,y;i<=m;i++){
		scanf("%d%d",&x,&y);
		g[x]|=1<<y;g[y]|=1<<x;
	}f[0]=ans=1;
	for(int s=1,pw=233;s<(1<<n);s++,pw=233ll*pw%mod){
		int x=__builtin_ctz(s),t=s^(1<<x);
		f[s]=f[s^(s&g[x])]+f[t];
		ans=(ans+1ll*pw*f[s])%mod;
	}printf("%d\n",ans);
}

pypy3 解法, 执行用时: 1686ms, 内存消耗: 560456K, 提交时间: 2021-11-28 09:30:33 

n,m=map(int,input().split())
dp=[0]*(1<<n)
nei=[1<<i for i in range(n)]
for _ in range(m):
    x,y=map(int,input().split())
    nei[x]|=1<<y
    nei[y]|=1<<x
dp[0]=1
c=1
ans=1
mod=10**9+7
f={}
for i in range(n):
    f[1<<i]=i
for i in range(1,1<<n):
    k=i&(-i)
    dp[i]=dp[i-k]+dp[i^(i&nei[f[k]])]
    c=(c*233)%mod
    ans=(ans+dp[i]*c)%mod
print(ans)

上一题

© 2024 nowcoder.com