思路：

//By SiriusRen #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int mod=1000000007; int cases,n,maxval,a[44][44],C[44][44],f[44],val[44],X,g[44]; int top2,top,bgn,half,cnts2[22],allnum[44],Ans,T; struct Node{int wei,num;Node(){}Node(int x,int y){wei=x,num=y;}}s[5+(1<<20)],s2[5+(1<<20)]; bool operator<(Node a,Node b){return a.wei<b.wei;} int pow(ll x,int y){ll res=1;while(y){if(y&1)res=res*x%mod;x=x*x%mod,y>>=1;}return (int)res; } int Gauss(int n){int f=1;for(int i=1;i<=n;i++){int j=i;while(!a[i][j]&&j<=n)j++;if(j==n+1)return 0;if(j!=i){for(int k=1;k<=n;k++)swap(a[i][k],a[j][k]);f*=-1;}int t=pow(a[i][i],mod-2);for(int j=i+1;j<=n;j++){int ww=1ll*a[j][i]*t%mod;for(int k=i;k<=n;k++)a[j][k]=(a[j][k]-1ll*ww*a[i][k]%mod+mod)%mod;}}ll ans=1;for(int i=1;i<=n;i++)ans=ans*a[i][i]%mod;if(f==-1)ans=(mod-ans)%mod;return ans; } void Kirchhoff(int x){memset(a,0,sizeof(a));for(int i=1;i<=n;i++)if(i<=x)for(int j=max(i+1,X+1);j<=n;j++)a[i][j]--,a[j][i]--,a[i][i]++,a[j][j]++;else for(int j=i+1;j<=n;j++)a[i][j]--,a[j][i]--,a[i][i]++,a[j][j]++; } bool cmp(int x,int y){return x>y;} void dfs(int x,int wei,int deep){!T?s[top++]=Node(wei,deep):s2[top2++]=Node(wei,deep);for(int i=x;i>bgn;i--)if(wei+val[i]<=maxval)dfs(i-1,wei+val[i],deep+1); } signed main(){for(int i=0;i<=40;i++){C[i][0]=C[i][i]=1;for(int j=1;j<i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;}scanf("%d",&cases);while(cases--){memset(allnum,0,sizeof(allnum));memset(cnts2,0,sizeof(cnts2));top=top2=X=bgn=Ans=T=0;scanf("%d%d",&n,&maxval);for(int i=1;i<=n;i++){scanf("%d",&val[i]);if(~val[i])X++;}half=(X+1)/2;for(int i=0;i<=X;i++)Kirchhoff(i),f[i]=g[i]=Gauss(n-1);for(int i=X;~i;i--)for(int j=i+1;j<=X;j++)f[i]=((f[i]-1ll*C[X-i][j-i]*f[j])%mod+mod)%mod;sort(val+1,val+1+n,cmp),random_shuffle(val+1,val+1+X);dfs(half,0,0),sort(s,s+top);T=1,bgn=half,dfs(X,0,0),sort(s2,s2+top2);for(int i=0;i<top2;i++)cnts2[s2[i].num]++;for(int i=0,j=top2-1;i<top;i++){while(s[i].wei+s2[j].wei>maxval)cnts2[s2[j].num]--,j--;for(int k=0;k<=X-half;k++)(allnum[k+s[i].num]+=cnts2[k])%=mod;}for(int i=0;i<=X;i++)Ans=(Ans+1ll*f[X-i]*allnum[i])%mod;printf("%d\n",(Ans+mod)%mod);} }

?

轉載于:https://www.cnblogs.com/SiriusRen/p/7050565.html

總結

以上是生活随笔為你收集整理的51nod1446 Kirchhoff矩阵+Gauss消元+容斥+折半DFS的全部內容，希望文章能夠幫你解決所遇到的問題。

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