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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
| #include<bits/stdc++.h>
using namespace std;
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define reg register
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define pb push_back
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char IO;
int rd(){
int s=0;
int f=0;
while(!isdigit(IO=getchar())) if(IO=='-') f=1;
do s=(s<<1)+(s<<3)+(IO^'0');
while(isdigit(IO=getchar()));
return f?-s:s;
}
static const int N=20,INF=1e8+10;
int n,m,ans,L,R;
int cnt[N],id[N];
vector <int> G[N];
int GS[N];
vector <int> Layer[N];
int Calc_DAG() {
static int dp[1<<6];
int A=(1<<n)-1;
rep(i,0,A) dp[i]=0;
dp[0]=1;
rep(S,0,A-1) rep(i,0,n-1) if((~S&(1<<i)) && (S&GS[i+1])==GS[i+1]) dp[S|(1<<i)]+=dp[S];
return dp[A];
}
int ind[N];
struct Limited_Flow{
static const int M=300;
int S,T;
struct Edge{
int to,nxt,w;
} e[M];
int head[N],ecnt;
void clear(){
rep(i,1,n*2+4) head[i]=0;
ecnt=0;
}
#define erep(u,i) for(int i=head[u];i;i=e[i].nxt)
void AddEdge(int u,int v,int w) { e[ecnt]=(Edge){v,head[u],w},head[u]=ecnt++; }
void Link(int u,int v,int w){ AddEdge(u,v,w),AddEdge(v,u,0); }
int dis[N];
int Bfs(){
static queue <int> que;
rep(i,1,T) dis[i]=INF; dis[S]=0,que.push(S);
while(!que.empty()) {
int u=que.front(); que.pop();
erep(u,i) {
int v=e[i].to,w=e[i].w;
if(!w || dis[v]<=dis[u]+1) continue;
dis[v]=dis[u]+1,que.push(v);
}
}
return dis[T]<INF;
}
int Dfs(int u,int flowin){
if(u==T) return flowin;
int flowout=0;
erep(u,i) {
int v=e[i].to,w=e[i].w;
if(!w || dis[v]!=dis[u]+1) continue;
int t=Dfs(v,min(flowin-flowout,w));
e[i].w-=t,e[i^1].w+=t,flowout+=t;
if(flowin==flowout) break;
}
if(!flowout) dis[u]=0;
return flowout;
}
int Dinic(){
int ans=0;
while(Bfs()) ans+=Dfs(S,INF);
return ans;
}
int Check(){
erep(S,i) if(e[i].w) return 0;
erep(T,i) if(e[i^1].w) return 0;
return 1;
}
} Flow;
void Extend_Edge(int u,int v,int L,int R){
ind[u]-=L,ind[v]+=L;
Flow.Link(u,v,R-L);
}
int Check(){
rep(i,1,n*2+4) ind[i]=0;
Flow.clear();
rep(i,1,n) Extend_Edge(i*2-1,i*2,cnt[i],cnt[i]);
rep(i,1,n) if(id[i]==1) Extend_Edge(n*2+1,i*2-1,cnt[i],cnt[i]);
rep(u,1,n) for(int v:G[u]) Extend_Edge(u*2,v*2-1,1,INF);
rep(i,1,n) Extend_Edge(i*2,n*2+2,0,INF);
Extend_Edge(n*2+2,n*2+1,0,INF);
rep(i,1,n*2+2) {
if(ind[i]>0) Flow.Link(n*2+3,i,ind[i]);
if(ind[i]<0) Flow.Link(i,n*2+4,-ind[i]);
}
Flow.S=n*2+3,Flow.T=n*2+4;
Flow.Dinic();
return Flow.Check();
}
void Dfs_GetDAG(int p) {
if(p==n+1) {
int Ways=Calc_DAG();
if(Ways<L || Ways>R) return;
ans+=Check();
return;
}
if(id[p]==m) return Dfs_GetDAG(p+1);
int n=Layer[id[p]+1].size();
rep(S,0,(1<<n)-1) {
rep(i,0,n-1) if(S&(1<<i)) G[p].pb(Layer[id[p]+1][i]),GS[p]|=1<<(Layer[id[p]+1][i]-1);
Dfs_GetDAG(p+1);
G[p].clear(),GS[p]=0;
}
}
void Dfs_Getlayer(int num,int fir,int chosennumber){
if(chosennumber==n) {
m=num;
rep(i,1,m) Layer[i].clear();
rep(i,1,n) Layer[id[i]].pb(i);
Dfs_GetDAG(1);
return;
}
rep(i,fir,n) if(!id[i]) {
id[i]=num;
Dfs_Getlayer(num,i+1,chosennumber+1);
id[i]=0;
}
if(fir!=1) Dfs_Getlayer(num+1,1,chosennumber);
}
class CosmicBlocks {
public:
int getNumOrders(vector <int> a, int Min, int Max) {
L=Min,R=Max;
n=a.size(),ans=0; rep(i,0,n-1) cnt[i+1]=a[i];
Dfs_Getlayer(1,1,0);
return ans;
}
};
|
