C. 奇奇怪怪的魔法陣

題意：

n個點m條邊，定義集合S為獨立集，當且僅當任意x,y∈S，x與y之間沒有邊。空集也是獨立集
現在對于每一個點的集合T，有多少子集為獨立集
設N=0,1,…,n-1,$A_T={\sum }_{S?T}[S是獨立集]$。對于每一個T?N，求出$A_T$
1<=n<=26

題解：

看這個數據范圍就很明顯，復雜度是(1<<26)，正好1s內
而且肯定是dp轉移，但是還是不知道咋做，看了題解恍然大悟

設dp[msk]表示msk的子集內獨立集的個數。開始考慮轉移，在msk中隨便選一個元素i。對于元素i有兩種情況，考慮i在不在獨立集里，如果不在的話，i號點對其他點是沒有影響的，那么直接從dp[msk^(1<<i)]轉移。如果在，i號點的所有鄰居都不能在獨立集里，設i號點及其鄰居的節點集合為$net[i]$,這種情況就從$dp[msk?net[i]]$轉移即可
以上這是官方題集，我現在還有很大的疑惑？等想明白繼續更新

代碼：

#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; int n,m,x,y,msk[55],dp[(1<<26)+10],fun[(1<<25)+10],id,ans; int main() {scanf("%d%d",&n,&m);for (int i=0;i<n;i++) msk[i]=1<<i;for (int i=1;i<=m;i++){scanf("%d%d",&x,&y);msk[x]|=(1<<y);msk[y]|=(1<<x);}for (int i=0;i<n;i++) fun[1<<i]=i;dp[0]=1;for (int i=1;i<(1<<n);i++){id=fun[i&(-i)];//獲取1的最低位 /*i^(1<<id)：當前i的狀態中去掉第id個 */ dp[i]=dp[i^(1<<id)]+dp[i^(i&msk[id])];if (dp[i]>=mod) dp[i]-=mod;}for (int i=(1<<n)-1;i>=0;i--) ans=(233ll*ans+dp[i])%mod;printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的C. 奇奇怪怪的魔法阵（未搞懂）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。