【NOIAC31】MST

Source and Judge

NOIAC31

Record

3h

Analysis

请先思考后再展开

神仙题,%出题人
这道题我能非常认同其做法,但我深知不是我能自己想出来的范围内

如果我按顺序枚举每一条边,那么非树边一定连接同一个块,而树边连接不同两个块
因为每个节点都是一样的,用【每个大小的联通块数量】表示,这个状态总数是37338
用这个状态的出现编号作为hash,那么就可以用这个来线性dp
把状态按照【越大联通块是越前的关键字】排序,这样就能保证线性性
然后顺序枚举每个状态,往后继状态转移
为了方便找到对应的hash,建议用一个trie,因为map是其15倍(如果hash不稳……)

现在是 $O(n^4 \times 状态)$ 的,分情况加速
考虑树边,枚举两个联通块然后合并起来,在这个过程中显然和具体边无关
所以可以对于每个状态预处理,记录能否转移以及转移系数(这个自行推算)
考虑非树边,因为是一个完全图,我们需要知道有哪些地方还能加入边
注意到加入之后状态的表示没有变化,所以其实跟具体在哪个加入是没有关系的
所以说,可以动态维护一个全局num数组,表示每个状态在当前可以加入的空位数量
这个东西的维护可以自行推导

注意到一个重要的细节,也是我之前的疑惑之处
就是我原本认为这个num应当是状态的一部分,但显然这样会炸
其实你会发现,在外层枚举了边数之后,某个状态的num其实是确定的(从num的维护可以看出)

然后这道题就做了两天……

  1. 计数dp中,滚动数组用完要清零
  2. 注意各种边界
  3. 其实这个num是可以不用dp的,不过我不想再花n的时间去计算num,好像ozy会很快的方法,不管了……

时间复杂度的话,感觉是n三方的,而且个人感觉会跑满……
然而最后还是O(能过),可能会有更优秀的做法?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
int n;
//*******************State*******************
struct Nod{int num[41],pos;}p[40000];//pos用于还原
bool cmp(Nod a,Nod b)
{
for(int i=n;i>=1;i--) if(a.num[i]!=b.num[i]) return a.num[i]>b.num[i];
return 0;
}
void output(Nod a)
{
for(int j=1;j<=n;j++) printf("%d ",a.num[j]);
puts("");
}
//*******************Trie*******************
struct Trie
{
int hash;
int son[41];
void clear() {memset(son,0,sizeof son);}
}tr[1500000];
int id=0;
int findhash(Nod to)
{
int now=0;
for(int i=1;i<=n;i++)
{
int wt=tr[now].son[ to.num[i] ];
if(wt==0) return -1;
now=wt;
}
return tr[now].hash;
}
int cnt=0,a[50];
void addhash()
{
int now=0;
for(int i=1;i<=n;i++)
{
if(tr[now].son[a[i]]==0) tr[now].son[a[i]]=++id,tr[id].clear();
now=tr[now].son[a[i]];
}
p[++cnt].pos=now;
for(int i=1;i<=n;i++) p[cnt].num[i]=a[i];
}
void dfs(int num,int now)
{
if(now==0)
{
if(num==0) addhash();
return;
}
for(int i=0;i<=num/now;i++) a[now]=i,dfs(num-now*i,now-1);
}
//*******************prework*******************
const ll MOD=1e9+7;
int hou[40000];
struct Edge{int y,g;int xs,adnum;};//系数、可用边数量的增加
vector<Edge> e;//O(开的下)……
void prework()
{
e.push_back((Edge){0,0,0});//规避 编号0
for(int s=1;s<=cnt;s++)
{
Nod now=p[s];
for(int a=1;a<=n-1;a++) if(now.num[a]>0)
for(int b=a;a+b<=n;b++) if(now.num[b]>(a==b))
{
int xs=(ll)a*b%MOD;
if(a==b) xs=(ll)xs*(now.num[a]*(now.num[a]-1)/2)%MOD;
else xs=(ll)xs*now.num[a]*now.num[b]%MOD;//有序数对
Nod tmp=now;tmp.num[a]--;tmp.num[b]--;tmp.num[a+b]++;
int s2=findhash(tmp);if(s2<0) continue;
e.push_back( (Edge){s2,hou[s],xs,a*b-1} );hou[s]=e.size()-1;
}
}
}
//*******************dp*******************
bool istree[50*50];
int f[2][40000],num[2][40000];//num用来简便计算
void solve()
{
for(int i=1;i<=n-1;i++) {int t;scanf("%d",&t);istree[t]=1;}
f[0][cnt]=1;
for(int ln=1;ln<=n*(n-1)/2;ln++)
for(int s=1;s<=cnt;s++) if(f[(ln-1)&1][s])//01背包,自带滚动
{
if(istree[ln])
{
for(int k=hou[s];k>0;k=e[k].g)
{
int s2=e[k].y;
f[ln&1][s2]=(f[ln&1][s2]+(ll)e[k].xs*f[(ln-1)&1][s]%MOD)%MOD;
num[ln&1][s2]=num[(ln-1)&1][s]+e[k].adnum;//覆盖无影响
}
}
else
{
if(num[(ln-1)&1][s]>0)
{
f[ln&1][s]=(f[ln&1][s]+(ll)f[(ln-1)&1][s]*num[(ln-1)&1][s]%MOD)%MOD;
num[ln&1][s]=num[(ln-1)&1][s]-1;
}
else f[ln&1][s]=num[ln&1][s]=0;
}
f[(ln-1)&1][s]=num[(ln-1)&1][s]=0;
}
}
void main()
{
scanf("%d",&n);
tr[0].clear();dfs(n,n);sort(p+1,p+cnt+1,cmp);
for(int i=1;i<=cnt;i++) tr[p[i].pos].hash=i;
prework();solve();
printf("%d",f[(n*(n-1)/2)&1][1]);
}
};
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/381c.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%