7.12 NOI模拟赛生成树装压dp vector装压

LINK：生成树

这场比赛我打的真失败 T3是比较容易的却一直刚那道"数论"

10分其实搜一下全排列。

30分容易想到对边进行装压dp。

不过存在一些细节可以对于一个连通块的壮大进行装压也就是每次需要联通两个块的时候使用关键边然后再这两个块之间加边知道加满需要其他边。

复杂度 \(2^{21}\cdot 21\cdot 6\) 可能能过或许是我的做法不太行？

值得一提的是这样是无标号的需要最后乘以一个阶乘.

可以发现之所以装压边是为了防止一些边的添加使得最小生成树变化。

可以考虑从小到大加边是关键边就连接两个连通块不是的话就添加到联通块的内部。

可以考虑对连通块进行装压可以发现所以可能的情况只有3e5左右种.

那么就有\(f_{i,j}\)表示加到i条边连通块的情况为j的方案数.

将边从小到大排序就不需要考虑且按照上述策略就一定不会改变最小生成树的形态.

当第i条边需要连接联通块的时候可以在状态中的两个联通块中选出两个连边就行辣这部分复杂度 \(n^3\)不过很大程度上是跑不满的。

当需要连到联通块的内部的时候那就预处理一下当前状态能在连通块中加多少条边即可。转移的复杂度为O(1).

因为每个状态最多连边一次所以

总复杂度\(n\cdot S+S\cdot n^3\)不过是跑不满的 n^3.

可以通过！

code

//#include<bits\stdc++.h>

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<cstring>

#include<string>

#include<ctime>

#include<cmath>

#include<cctype>

#include<cstdlib>

#include<queue>

#include<deque>

#include<stack>

#include<vector>

#include<algorithm>

#include<utility>

#include<bitset>

#include<set>

#include<map>

#define ll long long

#define db double

#define INF 10000000000000000ll

#define ldb long double

#define pb push_back

#define put_(x) printf("%d ",x);

#define get(x) x=read()

#define gt(x) scanf("%d",&x)

#define gi(x) scanf("%lf",&x)

#define put(x) printf("%d\n",x)

#define putl(x) printf("%lld\n",x)

#define gc(a) scanf("%s",a+1)

#define rep(p,n,i) for(RE int i=p;i<=n;++i)

#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])

#define fep(n,p,i) for(RE int i=n;i>=p;--i)

#define vep(p,n,i) for(RE int i=p;i<n;++i)

#define pii pair<int,int>

#define mk make_pair

#define RE register

#define P 1000000007

#define gf(x) scanf("%lf",&x)

#define pf(x) ((x)*(x))

#define uint unsigned long long

#define ui unsigned

#define EPS 1e-4

#define sq sqrt

#define S second

#define F first

#define mod 1000000007

#define V vector<int>

using namespace std;

char buf[1<<15],*fs,*ft;

inline char getc()

{

    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;

}

inline int read()

{

    RE int x=0,f=1;RE char ch=getc();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}

    return x*f;

}

const int MAXN=40010,maxn=40*40/2;

int f[maxn][MAXN];

V g[MAXN],now;

map<V,int>H;

int vis[maxn],w[MAXN];

int n,m,id;

inline void add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}

inline int mul(int x,int y){return (ll)x*y%mod;}

inline void dfs(int x,int res)

{

	if(!res)

	{

		H[now]=++id;g[id]=now;

		vep(0,now.size(),j)w[id]+=(now[j]*(now[j]-1))/2;

		return;

	}

	if(x>res)return;

	now.pb(x);

	dfs(x,res-x);

	now.pop_back();

	dfs(x+1,res);

}

int main()

{

	freopen("tree.in","r",stdin);

    freopen("tree.out","w",stdout);

	get(n);m=n*(n-1)/2;

	rep(1,n-1,i)vis[read()]=1;

	dfs(1,n);

	f[0][1]=1;

	rep(1,m,i)

	{

		rep(1,id,j)if(f[i-1][j])

		{

			if(vis[i])

			{

				vep(0,g[j].size(),l)

				vep(l+1,g[j].size(),r)

				{

					now.clear();

					vep(0,g[j].size(),k)if(k!=l&&k!=r)now.pb(g[j][k]);

					now.pb(g[j][l]+g[j][r]);

					sort(now.begin(),now.end());

					int ww=H[now],cc=mul(g[j][l],g[j][r]);

					add(f[i][ww],mul(cc,f[i-1][j]));

				}

			}

			else add(f[i][j],mul(f[i-1][j],w[j]-i+1));

		}

	}

	put(f[m][id]);return 0;

}

巴特西

7.12 NOI模拟赛生成树装压dp vector装压

最新文章

热门文章

巴特西

7.12 NOI模拟赛 生成树 装压dp vector装压

最新文章

热门文章

7.12 NOI模拟赛生成树装压dp vector装压