loj#6072 苹果树(折半搜索，矩阵树定理，容斥)
题解时间
$ n le 40 $ 。
无比精确的数字。
很明显只要一个方案不超过 $ limits $ ，之后的计算就跟选哪个没关系了。
折半搜索排序来统计有i个果子是有用的情况下的方案数。
然后矩阵树求生成树个数，容斥乱搞。
#include<bits/stdc .h>
using namespace std;
template<typename TP>inline void read(TP &tar)
{
TP ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ret=ret*10 (ch-'0');ch=getchar();}
tar=ret*f;
}
namespace RKK
{
const int N=50,mo=1000000007;
void doadd(int &a,int b){if((a =b)>=mo)a-=mo;}
int add(int a,int b){return (a =b)>=mo?a-mo:a;}
int fpow(int a,int p){int ret=1;while(p){if(p&1)ret=1ll*ret*a%mo;a=1ll*a*a%mo,p>>=1;}return ret;}
struct pat{int x,y;bool operator < (const pat &p)const{return x<p.x;}};
int n,halfn,lim,val[N],msn;
pat l1[1145141];int tp1;
pat l2[1145141];int tp2;
void dfs1(int x=1,int sum=0,int cnt=0)
{
if(sum>lim) return;if(x>halfn){l1[ tp1]=(pat){sum,cnt};return;}
dfs1(x 1,sum,cnt);if(~val[x]) dfs1(x 1,sum val[x],cnt 1);
}
void dfs2(int x=halfn 1,int sum=0,int cnt=0)
{
if(sum>lim) return;if(x>n){l2[ tp2]=(pat){sum,cnt};return;}
dfs2(x 1,sum,cnt);if(~val[x]) dfs2(x 1,sum val[x],cnt 1);
}
int c[N][N];void init(){for(int i=0;i<=40;i ){c[i][0]=1;for(int j=1;j<=i;j )c[i][j]=add(c[i-1][j-1],c[i-1][j]);}}
int ma[N][N];
int calc(int sn)
{
memset(ma,0,sizeof(ma));
for(int i=1;i<=n;i )for(int j=i 1;j<=n;j )
{
if((i<=sn&&(j<=sn||j>msn))||i>msn||j>msn)
ma[i][i] ,ma[j][j] ,doadd(ma[i][j],mo-1),doadd(ma[j][i],mo-1);
}
int b=n-1;int f=1;
for(int l=1;l<=b;l )
{
int g=l;for(;g<=b&&!ma[g][l];g );if(g>b) return 0;
if(g!=l){for(int j=l;j<=b;j ) swap(ma[l][j],ma[g][j]);f=-f;}
for(g=l 1;g<=b;g )
{
int k=1ll*ma[g][l]*fpow(ma[l][l],mo-2)%mo;
for(int j=l;j<=b;j ) doadd(ma[g][j],mo-1ll*ma[l][j]*k%mo);
}
}
if(f==-1) f=mo-1;
for(int i=1;i<=b;i ) f=1ll*f*ma[i][i]%mo;
return f;
}
int cnt[N],sum[N];
int cnttmp[N];
int main()
{
read(n),read(lim),halfn=n 1>>1;
for(int i=1;i<=n;i ) read(val[i]),msn =(val[i]!=-1);
dfs1(),dfs2();init();
sort(l1 1,l1 tp1 1),sort(l2 1,l2 tp2 1);
for(int i1=tp1,i2=1;i1;i1--)
{
for(;i2<=tp2&&l1[i1].x l2[i2].x<=lim;cnttmp[l2[i2].y] ,i2 );
for(int j=0;j<=n;j ) doadd(cnt[l1[i1].y j],cnttmp[j]);
}
for(int i=0;i<=msn;i ) sum[i]=calc(i);
for(int i=1;i<=msn;i )for(int j=0;j<i;j )
doadd(sum[i],mo-1ll*c[i][j]*sum[j]%mo);
int ans=0;
for(int i=0;i<=msn;i ) doadd(ans,1ll*cnt[i]*sum[i]%mo);
printf("%dn",ans);
return 0;
}
}
int main(){return RKK::main();}