正題

luogu
AT3634

---

題目大意

給你一個圖，讓你給圖上的邊定方向，問1,2兩個點可以到同一個點的方案數

---

解題思路

直接求可以到同一個點不好求，可以用總方案數減去不合法方案數，即到不了同一個點的方案數

那么就是有若干點把1,2分開，設 $f_{1/2,i}$ 表示從 1/2 開始走，可以走到狀態 i 中的點，這一部分直接求也不好求，考慮容斥

先計算出 i 中的邊隨意定向的方案數（記為s），然后枚舉一個狀態 j，表示只能到 j 的方案數，對于補集中的邊隨便選（因為無法到補集中的任何一個點，所以里面的邊的方向不影響），那么有

$$f_{1/2,i}=2^{s_i}?\sum f_{1/2,j}\times 2^{s_{i\oplus j}}$$

得到 f 后枚舉1,2個點能到的點即可

---

code

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 400 #define M 100000 #define mod 1000000007 using namespace std; ll n,m,k,ans,X[N],Y[N],pw[N],s[M],f[3][M]; int main() {scanf("%lld%lld",&n,&m);k=(1<<n)-1;for(int i=1;i<=m;++i)scanf("%lld%lld",&X[i],&Y[i]);pw[0]=1;for(int i=1;i<=m;++i)pw[i]=pw[i-1]*2%mod;for(int i=0;i<=k;++i)for(int j=1;j<=m;++j)if((i&(1<<X[j]-1))&&(i&(1<<Y[j]-1)))s[i]++;for(int g=1;g<=2;++g)for(int i=0;i<=k;++i){if(!(i&(1<<g-1)))continue;f[g][i]=pw[s[i]];for(int j=i;j;j=(j-1)&i)f[g][i]=(f[g][i]-f[g][i^j]*pw[s[j]]%mod+mod)%mod;}ans=pw[m];for(int i=0;i<=k;++i)for(int j=k^i;j;j=(j-1)&(k^i))//點不能有交集if(s[i]+s[j]==s[i|j])//不存在邊直接相連ans=(ans-f[1][i]*f[2][j]%mod*pw[s[k^(i|j)]]%mod+mod)%mod;printf("%lld",ans);return 0; }

總結

以上是生活随笔為你收集整理的【DP】【容斥】Nice to Meet You（AT3634）的全部內容，希望文章能夠幫你解決所遇到的問題。

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