Codeforces #418 Div2 – Guanghao Ye

Finally, another China Round 😛 Solved A to C during the contest, and fail to submit problem D

A. An abandoned sentiment from past

We are required to use elements from B to replace zeros in A, to form an array that is not increasing. First, since all elements are unique, if the zero number is more than 2, there must be a solution. If we can form an increasing array but replace more or equal than 2 zeros. We can exchange them to form a valid one. So, what we need do is check if there are only one zero if it is valid.

//This sourcecode is under GPLv3
//http://yeguanghao.xyz
#include <bits/stdc++.h>
#define rep(name,start,end,step) for(int name=start;name<=end;name+=step)
using namespace std;
#define Pn(x) printf("%d\n",x)
#define Ps(x) printf("%d ",x)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define PROB
inline void R(int &x) {
	x=0; int f=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
void Redirect() {
	freopen(PROB".in","r",stdin);
#ifndef YGHDEBUG
	freopen(PROB".out","w",stdout);
#endif
}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n,m;
int a[105];
int cn=0;
int cnt[205];
bool check() {
	for(int i=1;i<=n;++i) {
		if(a[i]<a[i-1]) {
			return 1;
		}
	}
	return 0;
}
int main() {
	R(n); R(m);
	for(int i=1;i<=n;++i) {
		R(a[i]);
		if(!a[i]) cn++;	
	}
	for(int j=1;j<=m;++j) {
		int t;R(t);
		cnt[t]++;
	}
	for(int i=1;i<=n;++i) {
		if(a[i]) continue;
		int cur;
		for(int j=200;j;--j) {
			if(cnt[j]) {
				cur=j;
				cnt[j]--;
				break;
			}
		}
		a[i]=cur;
	}
	puts(((cn==m)&&check())?"Yes":"No");
	return 0;
}

//This sourcecode is under GPLv3

//http://yeguanghao.xyz

#include <bits/stdc++.h>

#define rep(name,start,end,step) for(int name=start;name<=end;name+=step)

using namespace std;

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

#define Ps(x) printf("%d ",x)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define PROB

inline void R(int &x) {

x=0; int f=1; char ch=getchar();

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

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

x*=f;

}

void Redirect() {

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

#ifndef YGHDEBUG

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

#endif

}

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

int n,m;

int a[105];

int cn=0;

int cnt[205];

bool check() {

for(int i=1;i<=n;++i) {

if(a[i]<a[i-1]) {

return 1;

}

return 0;

}

int main() {

R(n); R(m);

for(int i=1;i<=n;++i) {

R(a[i]);

if(!a[i]) cn++;

}

for(int j=1;j<=m;++j) {

int t;R(t);

cnt[t]++;

}

for(int i=1;i<=n;++i) {

if(a[i]) continue;

int cur;

for(int j=200;j;--j) {

if(cnt[j]) {

cur=j;

cnt[j]--;

break;

}

a[i]=cur;

}

puts(((cn==m)&&check())?"Yes":"No");

return 0;

}

B. An express train to reveries

You are given two different arrays which are both an element different from a permutation. You are asked to compute the original permutation. Since there are only one element different, so if there are different in the same position, we can just check which number is missing. Otherwise, we are choosing a number from two in each two positions. I used next_permutation and check to solve this problem.

//This sourcecode is under GPLv3
//http://yeguanghao.xyz
#include <bits/stdc++.h>
#define rep(name,start,end,step) for(int name=start;name<=end;name+=step)
using namespace std;
#define Pn(x) printf("%d\n",x)
#define Ps(x) printf("%d ",x)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define PROB
inline void R(int &x) {
	x=0; int f=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
void Redirect() {
	freopen(PROB".in","r",stdin);
#ifndef YGHDEBUG
	freopen(PROB".out","w",stdout);
#endif
}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n;
int a[1005];
int b[1005];
set<int> s;
vector<int> x[3];
bool check() {
	if(x[1]==x[0]) return 0;
	else if(x[2]==x[0]) return 0;
	int qwq=0,qaq=0;
	for(int i=0;i<x[0].size();++i) {
		if(x[0][i]!=x[1][i]) qwq++;
		if(x[0][i]!=x[2][i]) qaq++;
	}
	if((qwq!=1)||(qaq!=1)) return 0;
	return 1;
}
int cn[1005];
int main() {
	R(n);
	for(int i=1;i<=n;++i) {
		R(a[i]);
	}
	for(int i=1;i<=n;++i) {
		R(b[i]);
		if(a[i]!=b[i]) {
			x[1].pb(a[i]);
			x[2].pb(b[i]);
			s.insert(a[i]);
			s.insert(b[i]);
		} else {
			cn[b[i]]++;
		}
	}
	int ovo=0;
	for(int i=1;i<=n;++i) {
		if(!cn[i]) ovo++;
	}
	if(ovo==1) {
		for(int i=1;i<=n;++i) {
			if(a[i]==b[i]) {
				Ps(a[i]);
			} else {
				for(int i=1;i<=n;++i) {
					if(!cn[i]) {
						Ps(i);
					}
				}
			}
		}
		puts("");
		return 0;
	}
	int cnt=0;
	for(auto i:s) {
		if(!cn[i])
		x[0].pb(i);
	}
	do {
		if(check()) {
			for(int i=1;i<=n;++i) {
				if(a[i]==b[i]) {
					Ps(a[i]);	
				} else {
					Ps(x[0][cnt++]);
				}
			}
			puts("");
			return 0;
		} else {
			next_permutation(x[0].begin(),x[0].end());
		}
	}while(1);
}

100

101

//This sourcecode is under GPLv3

//http://yeguanghao.xyz

#include <bits/stdc++.h>

#define rep(name,start,end,step) for(int name=start;name<=end;name+=step)

using namespace std;

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

#define Ps(x) printf("%d ",x)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define PROB

inline void R(int &x) {

x=0; int f=1; char ch=getchar();

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

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

x*=f;

}

void Redirect() {

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

#ifndef YGHDEBUG

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

#endif

}

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

int n;

int a[1005];

int b[1005];

set<int> s;

vector<int> x[3];

bool check() {

if(x[1]==x[0]) return 0;

else if(x[2]==x[0]) return 0;

int qwq=0,qaq=0;

for(int i=0;i<x[0].size();++i) {

if(x[0][i]!=x[1][i]) qwq++;

if(x[0][i]!=x[2][i]) qaq++;

}

if((qwq!=1)||(qaq!=1)) return 0;

return 1;

}

int cn[1005];

int main() {

R(n);

for(int i=1;i<=n;++i) {

R(a[i]);

}

for(int i=1;i<=n;++i) {

R(b[i]);

if(a[i]!=b[i]) {

x[1].pb(a[i]);

x[2].pb(b[i]);

s.insert(a[i]);

s.insert(b[i]);

} else {

cn[b[i]]++;

}

int ovo=0;

for(int i=1;i<=n;++i) {

if(!cn[i]) ovo++;

}

if(ovo==1) {

for(int i=1;i<=n;++i) {

if(a[i]==b[i]) {

Ps(a[i]);

} else {

for(int i=1;i<=n;++i) {

if(!cn[i]) {

Ps(i);

}

puts("");

return 0;

}

int cnt=0;

for(auto i:s) {

if(!cn[i])

x[0].pb(i);

}

do {

if(check()) {

for(int i=1;i<=n;++i) {

if(a[i]==b[i]) {

Ps(a[i]);

} else {

Ps(x[0][cnt++]);

}

puts("");

return 0;

} else {

next_permutation(x[0].begin(),x[0].end());

}

}while(1);

}

C. An impassioned circulation of affection

You are required to compute the longest segment of the array, after modify at most k numbers. There are $2*10^5$ queries and the max number of the array is less than 27. So we can use a prefix array to store how much steps we need to do to make the array from 1 to i are all the same. Then we use a binary search to find the answer. The overall complexity is $O(NQlogN+N*color)$

//This sourcecode is under GPLv3
//http://yeguanghao.xyz
#include <bits/stdc++.h>
#define rep(name,start,end,step) for(int name=start;name<=end;name+=step)
using namespace std;
#define Pn(x) printf("%d\n",x)
#define Ps(x) printf("%d ",x)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define PROB
inline void R(int &x) {
	x=0; int f=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
void Redirect() {
	freopen(PROB".in","r",stdin);
#ifndef YGHDEBUG
	freopen(PROB".out","w",stdout);
#endif
}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int pre[1505][27];
int ans[1505][27];
int n;
int a[1505];
bool check(int col,int pos,int l,int cost) {
	if(pos+l-1>n) return 0;
	return (pre[min(pos+l-1,n)][col]-pre[pos-1][col])<=cost;
}
int main() {
	memset(ans,-1,sizeof ans);
	R(n);
	for(int i=1;i<=n;++i) {
		char ch=0; while(!isalpha(ch))ch=getchar();
		a[i]=ch-'a'+1;
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=26;++j) {
			if(a[i]==j) {
				pre[i][j]=pre[i-1][j];
			} else {
				pre[i][j]=pre[i-1][j]+1;
			}
		}
	}
	int t; R(t);
	while(t--) {
		int p,c; R(p);
		char ch=0; while(!isalpha(ch)) ch=getchar();
		c=ch-'a'+1;
		if(ans[p][c]!=-1) {
			Pn(ans[p][c]);
			continue;
		} 
		if(check(c,1,n,p)) {
			for(int i=p;i<=n;++i) {
				ans[i][c]=n;
			}
			Pn(ans[p][c]); 
			continue;

		} else {
			int an=0;
			for(int i=n;i;--i) {
				int l=0,r=n;
				while(r-l>1) {
					int mid=(l+r)>>1;
					if(check(c,i,mid,p)) l=mid;
					else r=mid;
				}
				an=max(an,l);
			}
			ans[p][c]=an;
			Pn(ans[p][c]);
		}
	}
}

//This sourcecode is under GPLv3

//http://yeguanghao.xyz

#include <bits/stdc++.h>

#define rep(name,start,end,step) for(int name=start;name<=end;name+=step)

using namespace std;

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

#define Ps(x) printf("%d ",x)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define PROB

inline void R(int &x) {

x=0; int f=1; char ch=getchar();

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

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

x*=f;

}

void Redirect() {

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

#ifndef YGHDEBUG

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

#endif

}

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

int pre[1505][27];

int ans[1505][27];

int n;

int a[1505];

bool check(int col,int pos,int l,int cost) {

if(pos+l-1>n) return 0;

return (pre[min(pos+l-1,n)][col]-pre[pos-1][col])<=cost;

}

int main() {

memset(ans,-1,sizeof ans);

R(n);

for(int i=1;i<=n;++i) {

char ch=0; while(!isalpha(ch))ch=getchar();

a[i]=ch-'a'+1;

}

for(int i=1;i<=n;++i) {

for(int j=1;j<=26;++j) {

if(a[i]==j) {

pre[i][j]=pre[i-1][j];

} else {

pre[i][j]=pre[i-1][j]+1;

}

int t; R(t);

while(t--) {

int p,c; R(p);

char ch=0; while(!isalpha(ch)) ch=getchar();

c=ch-'a'+1;

if(ans[p][c]!=-1) {

Pn(ans[p][c]);

continue;

}

if(check(c,1,n,p)) {

for(int i=p;i<=n;++i) {

ans[i][c]=n;

}

Pn(ans[p][c]);

continue;

} else {

int an=0;

for(int i=n;i;--i) {

int l=0,r=n;

while(r-l>1) {

int mid=(l+r)>>1;

if(check(c,i,mid,p)) l=mid;

else r=mid;

}

an=max(an,l);

}

ans[p][c]=an;

Pn(ans[p][c]);

}

D. An overnight dance in discotheque

Give you $N$ circles, and you need to divide them into two categories. And you are asked to calculate the maximum sum of xor-sum of these circles. Since there are only 2000 circles, so we can easily build the tree with brute force. Then the greedy strategy is that divide all the son of root to another category, and others remain the same. The complexity is $O(N^2)$ . It is noticeable that we can do this problem in $O(NlogN)$ complexity with scanning lines and use a balanced tree to maintain them.

//This sourcecode is under GPLv3
//http://yegunanghao.xyz
#include <bits/stdc++.h>
#define rep(name,start,end,step) for(int name=start;name<=end;name+=step)
using namespace std;
#define Pn(x) printf("%d\n",x)
#define Ps(x) printf("%d ",x)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define PROB
inline void R(int &x) {
	x=0; int f=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
void Redirect() {
	freopen(PROB".in","r",stdin);
#ifndef YGHDEBUG
	freopen(PROB".out","w",stdout);
#endif
}
#define rank rax
#define x first.first
#define y first.second
#define r second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> Cir;
typedef vector<int> node;
const int maxn=1005;
node s[1005];
Cir c[1005];
int rank[1005];
bool AinB(Cir a, Cir b) {
	ll k=1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y)-1ll*(b.r-a.r)*(b.r-a.r);
	if(k!=0) {
		return k<0;
	} else {
		return b.r>a.r;
	}
}
bool AinB(int u,int w) {
	return AinB(c[u],c[w]);
}
bool cmr(const Cir &a,const Cir &b) {
	return a.se>b.se;
}
void dfs(int k) {
	for(int i=0;i<s[k].size();++i) {
		rank[s[k][i]]=rank[k]+1;
	}
	for(int i=0;i<s[k].size();++i) {
		if(rank[s[k][i]]!=rank[k]+1) continue;
		for(int j=i+1;j<s[k].size();++j) {
			if((rank[s[k][j]]==rank[k]+1)&&AinB(s[k][j],s[k][i])) {
				s[s[k][i]].pb(s[k][j]);
			}
		}
		dfs(s[k][i]);
	}
}
int n;
int main() {
	R(n);
	for(int i=1;i<=n;++i) {
		int xi,yi,ri;
		R(xi); R(yi); R(ri);
		c[i]=mp(mp(xi,yi),ri);
	}
	sort(c+1,c+n+1,cmr);
	for(int i=1;i<=n;++i) {
		if(!rank[i]) {
			rank[i]=1;
			for(int j=i+1;j<=n;++j) {
				if(i==j) continue;
				if(!rank[j]) {
					if(AinB(j,i)) {
						s[i].pb(j);
					}
				}
			}
			dfs(i);
		}
	}
	ll ans=0;
	for(int i=1;i<=n;++i) {
		if((rank[i]<=2)||(rank[i]%2==0)) {
			ans+=(ll)c[i].r*c[i].r;
		} else {
			ans-=(ll)c[i].r*c[i].r;
		}
//		printf("%d %d %d %d\n",c[i].x,c[i].y,c[i].r,rank[i]);
	}
	printf("%.10f\n",3.1415926535*ans);
}

100

//This sourcecode is under GPLv3

//http://yegunanghao.xyz

#include <bits/stdc++.h>

#define rep(name,start,end,step) for(int name=start;name<=end;name+=step)

using namespace std;

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

#define Ps(x) printf("%d ",x)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define PROB

inline void R(int &x) {

x=0; int f=1; char ch=getchar();

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

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

x*=f;

}

void Redirect() {

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

#ifndef YGHDEBUG

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

#endif

}

#define rank rax

#define x first.first

#define y first.second

#define r second

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

typedef pair<pii,int> Cir;

typedef vector<int> node;

const int maxn=1005;

node s[1005];

Cir c[1005];

int rank[1005];

bool AinB(Cir a, Cir b) {

ll k=1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y)-1ll*(b.r-a.r)*(b.r-a.r);

if(k!=0) {

return k<0;

} else {

return b.r>a.r;

}

bool AinB(int u,int w) {

return AinB(c[u],c[w]);

}

bool cmr(const Cir &a,const Cir &b) {

return a.se>b.se;

}

void dfs(int k) {

for(int i=0;i<s[k].size();++i) {

rank[s[k][i]]=rank[k]+1;

}

for(int i=0;i<s[k].size();++i) {

if(rank[s[k][i]]!=rank[k]+1) continue;

for(int j=i+1;j<s[k].size();++j) {

if((rank[s[k][j]]==rank[k]+1)&&AinB(s[k][j],s[k][i])) {

s[s[k][i]].pb(s[k][j]);

}

dfs(s[k][i]);

}

int n;

int main() {

R(n);

for(int i=1;i<=n;++i) {

int xi,yi,ri;

R(xi); R(yi); R(ri);

c[i]=mp(mp(xi,yi),ri);

}

sort(c+1,c+n+1,cmr);

for(int i=1;i<=n;++i) {

if(!rank[i]) {

rank[i]=1;

for(int j=i+1;j<=n;++j) {

if(i==j) continue;

if(!rank[j]) {

if(AinB(j,i)) {

s[i].pb(j);

}

dfs(i);

}

ll ans=0;

for(int i=1;i<=n;++i) {

if((rank[i]<=2)||(rank[i]%2==0)) {

ans+=(ll)c[i].r*c[i].r;

} else {

ans-=(ll)c[i].r*c[i].r;

}

// printf("%d %d %d %d\n",c[i].x,c[i].y,c[i].r,rank[i]);

}

printf("%.10f\n",3.1415926535*ans);

}

E. An unavoidable detour for home

This problem is rather interesting to think, but boring to code. I think the original editorial is clearly enough. Carefully classification, and then do the normal DP. There are total 10 situations.

//This sourcecode is under GPLv3
//http://yeguanghao.xyz
#include <bits/stdc++.h>
#define rep(name,start,end,step) for(int name=start;name<=end;name+=step)
using namespace std;
#define Pn(x) printf("%d\n",x)
#define Ps(x) printf("%d ",x)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define PROB
inline void R(int &x) {
	x=0; int f=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
void Redirect() {
	freopen(PROB".in","r",stdin);
#ifndef YGHDEBUG
	freopen(PROB".out","w",stdout);
#endif
}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define dp f
ll dp[2][55][55][55][55];
int a[55];
int n;
#define cur c
const int mod=(int)1e9+7;
int main() {
	R(n);
	for(int i=1;i<=n;++i) R(a[i]);
	int c=1,nex=0;
	dp[1][a[1]==2][a[1]==3][a[2]==2][a[2]==3]=1;
	for(int i=2;i<n;++i) {
		memset(dp[nex],0,sizeof dp[nex]);
		for(int p1=0;p1<=n;++p1) {
			for(int p2=0;p1+p2<=n;++p2) {
				for(int c1=0;p1+p2+c1<=n;++c1) {
					for(int c2=0;p1+p2+c1+c2<=n;++c2) {
						ll v=dp[cur][p1][p2][c1][c2];
						// new level
						if(p1+p2==0) {
							dp[cur][c1][c2][0][0]+=v;
							dp[cur][c1][c2][0][0]%=mod;
							continue;
						}
						// stay on 
						for(int lc=1;lc<=2;++lc) {// we solve a 1plug or 2plug ? 
							int cnt;
							if(lc==1) {
								cnt=p1;
								if(p1<=0) {
									continue;
								}
								p1--;
							} else {
								cnt=p2;
								if(p2<=0) continue;
								else {
									++p1;
									p2--;
								}
							}
							// let's dicuss type of new vertex
							if(a[i+1]==2) {
								f[nex][p1][p2][c1+1][c2]+=v*cnt;
								f[nex][p1][p2][c1+1][c2]%=mod;
								if(c1>=1) {
									f[nex][p1][p2][c1-1][c2]+=v*cnt*c1;
									f[nex][p1][p2][c1-1][c2]%=mod;
								}
								if(c2>=1) {
									f[nex][p1][p2][c1+1][c2-1]+=v*cnt*c2;
									f[nex][p1][p2][c1+1][c2-1]%=mod;
								}
							} else {
								f[nex][p1][p2][c1][c2+1]+=v*cnt;
								f[nex][p1][p2][c1][c2+1]%=mod;
								//1 plug*1
								if(c1>=1) {
									f[nex][p1][p2][c1][c2]+=v*cnt*c1;
									f[nex][p1][p2][c1][c2]%=mod;
								}
								// 1 plug2
								if(c2>=1) {
									f[nex][p1][p2][c1+2][c2-1]+=v*cnt*c2;
									f[nex][p1][p2][c1+2][c2-1]%=mod;
								}
								//2 plug1
								if(c1>=2) {
									f[nex][p1][p2][c1-2][c2]+=v*cnt*(c1)*(c1-1)/2;
									f[nex][p1][p2][c1-2][c2]%=mod;
								}
								//1 plug1 1plug2
								if(c1>=1&&c2&&1) {
									f[nex][p1][p2][c1][c2-1]+=v*cnt*(c1)*c2;
									f[nex][p1][p2][c1][c2-1]%=mod;
								}
								//2 plug2
								if(c2>=2) {
									f[nex][p1][p2][c1+2][c2-2]+=v*cnt*c2*(c2-1)/2;
									f[nex][p1][p2][c1+2][c2-2]%=mod;
								}
							}
							if(lc==1) p1++;
							else {
								p2++;p1--;
							}
							continue;
						}
					}

				}
			}
		}
		c^=1;
		nex^=1;
	}
	std::cout<<dp[cur][0][0][0][0] <<endl;
}

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

//This sourcecode is under GPLv3

//http://yeguanghao.xyz

#include <bits/stdc++.h>

#define rep(name,start,end,step) for(int name=start;name<=end;name+=step)

using namespace std;

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

#define Ps(x) printf("%d ",x)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define PROB

inline void R(int &x) {

x=0; int f=1; char ch=getchar();

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

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

x*=f;

}

void Redirect() {

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

#ifndef YGHDEBUG

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

#endif

}

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

#define dp f

ll dp[2][55][55][55][55];

int a[55];

int n;

#define cur c

const int mod=(int)1e9+7;

int main() {

R(n);

for(int i=1;i<=n;++i) R(a[i]);

int c=1,nex=0;

dp[1][a[1]==2][a[1]==3][a[2]==2][a[2]==3]=1;

for(int i=2;i<n;++i) {

memset(dp[nex],0,sizeof dp[nex]);

for(int p1=0;p1<=n;++p1) {

for(int p2=0;p1+p2<=n;++p2) {

for(int c1=0;p1+p2+c1<=n;++c1) {

for(int c2=0;p1+p2+c1+c2<=n;++c2) {

ll v=dp[cur][p1][p2][c1][c2];

// new level

if(p1+p2==0) {

dp[cur][c1][c2][0][0]+=v;

dp[cur][c1][c2][0][0]%=mod;

continue;

}

// stay on

for(int lc=1;lc<=2;++lc) {// we solve a 1plug or 2plug ?

int cnt;

if(lc==1) {

cnt=p1;

if(p1<=0) {

continue;

}

p1--;

} else {

cnt=p2;

if(p2<=0) continue;

else {

++p1;

p2--;

}

// let's dicuss type of new vertex

if(a[i+1]==2) {

f[nex][p1][p2][c1+1][c2]+=v*cnt;

f[nex][p1][p2][c1+1][c2]%=mod;

if(c1>=1) {

f[nex][p1][p2][c1-1][c2]+=v*cnt*c1;

f[nex][p1][p2][c1-1][c2]%=mod;

}

if(c2>=1) {

f[nex][p1][p2][c1+1][c2-1]+=v*cnt*c2;

f[nex][p1][p2][c1+1][c2-1]%=mod;

}

} else {

f[nex][p1][p2][c1][c2+1]+=v*cnt;

f[nex][p1][p2][c1][c2+1]%=mod;

//1 plug*1

if(c1>=1) {

f[nex][p1][p2][c1][c2]+=v*cnt*c1;

f[nex][p1][p2][c1][c2]%=mod;

}

// 1 plug2

if(c2>=1) {

f[nex][p1][p2][c1+2][c2-1]+=v*cnt*c2;

f[nex][p1][p2][c1+2][c2-1]%=mod;

}

//2 plug1

if(c1>=2) {

f[nex][p1][p2][c1-2][c2]+=v*cnt*(c1)*(c1-1)/2;

f[nex][p1][p2][c1-2][c2]%=mod;

}

//1 plug1 1plug2

if(c1>=1&&c2&&1) {

f[nex][p1][p2][c1][c2-1]+=v*cnt*(c1)*c2;

f[nex][p1][p2][c1][c2-1]%=mod;

}

//2 plug2

if(c2>=2) {

f[nex][p1][p2][c1+2][c2-2]+=v*cnt*c2*(c2-1)/2;

f[nex][p1][p2][c1+2][c2-2]%=mod;

}

if(lc==1) p1++;

else {

p2++;p1--;

}

continue;

}

c^=1;

nex^=1;

}

std::cout<<dp[cur][0][0][0][0] <<endl;

}

A. An abandoned sentiment from past

B. An express train to reveries

C. An impassioned circulation of affection

D. An overnight dance in discotheque

E. An unavoidable detour for home

Leave a Comment Cancel Reply