題目

P4336 [SHOI2016]黑暗前的幻想鄉

做法

每種顏色恰好一條邊，有點難處理啊

根據套路，數據范圍這么小，容斥一下所有的情況就可以了

對每種顏色進行狀壓，表這次只能選這些顏色，做\(n-1\)的時候會加上多余的東西，就減去\(n-2......\)

剩下的交給矩陣樹，這題有模數，高斯消元的時候逆元

My complete code

#include<cstring> #include<string> #include<iostream> #include<algorithm> #include<cstdio> using namespace std; typedef long long LL; const LL maxn=19; const LL p=1e9+7; inline LL Read(){LL x(0),f(1); char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();return x*f; } LL n,ans; LL m[maxn],size[1<<maxn]; LL D[maxn][maxn],eu[maxn][maxn*maxn],ev[maxn][maxn*maxn]; inline LL Pow(LL base,LL b){LL ret(1);while(b){if(b&1)ret=(ret*base)%p;base=base*base%p;b>>=1;}return ret; } inline LL Solve(){LL N=n-1,tr=0;for(LL i=1;i<=N;++i){LL mx=i;for(LL j=i+1;j<=N;++j)if(D[mx][i]<D[j][i])mx=j;if(D[mx][i]==0)return 0;if(mx!=i){tr^=1;swap(D[mx],D[i]);}for(LL j=i+1;j<=N;++j){LL tmp=D[j][i]*Pow(D[i][i],p-2)%p;for(LL k=i;k<=N;++k)D[j][k]=(D[j][k]-tmp*D[i][k]%p+p)%p;}}LL ret(1);for(LL i=1;i<=N;++i)ret=(ret*D[i][i])%p;if(tr)ret=p-ret;return ret; } int main(){n=Read();for(LL i=1;i<n;++i){m[i]=Read();for(LL j=1;j<=m[i];++j)eu[i][j]=Read(),ev[i][j]=Read();}LL Up=1<<(n-1);for(LL i=1;i<Up;++i)size[i]=size[i>>1]+(i&1);for(LL i=1;i<Up;++i){memset(D,0,sizeof(D));for(LL j=1,bit=i;bit;bit>>=1,++j){if((bit&1)==0)continue;for(LL k=1;k<=m[j];++k){LL u(eu[j][k]),v(ev[j][k]);++D[u][u],++D[v][v],D[u][v]=(D[u][v]+p-1)%p,D[v][u]=(D[v][u]+p-1)%p;}}ans=(ans+(( ((n-1-size[i])&1)==0)?Solve():-Solve())+p)%p;}printf("%lld\n",ans);return 0; }

轉載于:https://www.cnblogs.com/y2823774827y/p/10265056.html

總結

以上是生活随笔為你收集整理的P4336 [SHOI2016]黑暗前的幻想乡的全部內容，希望文章能夠幫你解決所遇到的問題。

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