luogu P4336 [SHOI2016]黑暗前的幻想乡

题面传送门这个(n)这么小肯定是拿来状压的。我们考虑设(F_{i})为仅用(i)种公司生成的树方案数。但是这个东西不是很好做，我们考虑设一个弱一点的状态：(G_i)表示用了(i)个公司的方案数。这个(G)显然可以状压在(O(n^32^n))时间内达到。然后考虑(G)怎么推出(F)假设我们(F_{1…i-1})都做好了，然后要推(F_i)这个考虑容斥，(F_i)总共有(C^{n}_{i})种，然后对于一个(j)总共有(C_{j}^{i})种，所以总共是两个乘起来。然后对于(j)有(C_{j}^{n})种可能，因为是均匀分布的就是除一下即可。code:

#include#define I inline#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define abs(x) ((x)>0?(x):-(x))#define re register#define ll long long#define db double#define N 17#define M 20000#define mod 1000000007#define eps (1e-7)#define U unsigned int#define it iterator#define Gc() getchar() #define Me(x,y) memset(x,y,sizeof(x))using namespace std;int n,m[N+5],tot,now,x[N+5][N*N+5],y[N+5][N*N+5];ll A[N+5][N+5],ans,frc[N+5],inv[N+5],W[N+5];I void insert(int x,int y){A[x][x]++;A[y][y]++;A[x][y]--;A[y][x]--;}I void swap(ll &x,ll &y){x^=y^=x^=y;}I ll calc(){re int i,j,h;ll ans=1;for(i=2;i<=n;i++){for(j=i+1;j<=n;j++){while(A[j][i]){now=mod-A[i][i]/A[j][i];for(h=i;h<=n;h++)A[i][h]=(A[i][h]+A[j][h]*now)%mod,swap(A[i][h],A[j][h]); ans*=-1;}}}for(i=2;i<=n;i++) ans=ans*A[i][i]%mod;return (ans+mod)%mod;}I ll mpow(ll x,int y=mod-2){ll ans=1;while(y) (y&1)&&(ans=ans*x%mod),y>>=1,x=x*x%mod;return ans;} int main(){freopen("1.in","r",stdin);re int i,j,h;scanf("%d",&n);for(i=1;i

这篇关于luogu P4336 [SHOI2016]黑暗前的幻想乡的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持