自动搬运

查看原文

来自洛谷，原作者为

	zyl0926 我爱唱，跳，rap,打篮球。ค้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้

搬运于2025-08-24 23:14:23，当前版本为作者最后更新于2025-05-11 21:36:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

思路

首先 $1$ 是需要粉刷，$0$ 是无需粉刷。按题意是构建一个序列，$1$ 有几个，这个序列就有几个数，$0$ 没有任何作用。

根据题目，题目说：那么它右侧（第 $i+1$ 面墙∼第 $n$ 面墙）蓝色的墙的个数必须是偶数（包括 $0$ 个）。

这个序列是粉刷顺序，所以这个序列要满足：对于每个数 $a_i$，$a_{1}\sim a_{i-1}$ 大于 $a_i$ 的个数，必须是偶数个，不然序列不成立。

至此已经想到了 $20$ 分的写法：全排列然后验证。

但想拿满分，就要考虑构造。

既然要满足要求，我们考虑从 $1$ 开始填写只能先填写奇数相，那么正好前面有偶数相并且一定大于 $1$，满足要求。

例如 $1$ 的个数有 $5$ 个，T是可填写，F是不可填写。

填入最小数 $1$ 后，这个数将永久不会影响后面的填写，因为他是最小的数，这等于将序列长度永久减 $1$。

以此类推，依次填入剩下的数。

求一共有多少种不同的合法序列。

那，有 $n$ 个 $1$，$1$ 产生的贡献是 $\lceil \frac{n}{2} \rceil$，$2$ 产生的贡献是 $\lceil \frac{n-1}{2} \rceil$，$i$ 产生的贡献是 $\lceil \frac{n-i+1}{2} \rceil$，由于是要求多少种不同的合法序列，就是求排列数量，所以求得是贡献积，可以用递推。 递推公式是：

由于 $i$ 只用之前一项，所以不用定义数组，只用一个变量 $ans$ 就行了。

Code

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
//#define int long long
using namespace std;
const int mod=1e9+7;//模数
int n;
signed main(void){
	IOS;
	cin>>n;
    int k=0;//1的个数
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		k+=x;//x只会为1或0。如果x为1，则k加1，如果为0，1的个数不会增加，所以不用写判断
	}
    int ans=1;//初始值k=0、k=1或k=2的值
	for(int i=3;i<=k;i++){
		ans=(1ll*ans*((i+1)/2))%mod;//记得 *1ll 不然会爆int，会WA
	}
	cout<<ans<<endl;//输出答案
	return 0;
}

闲话

我与QinYulang师出同门，他用的是看着用暴力跑出来的一到十的答案找规律，我用的是老师的思路改编了一下，我记得老师的思路有一大部分不一样。