Steven_MengのBlog

题目传送门

$10pt$

输出$0$,出题人还是很良心的

$30pt$

最简单的暴搜

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
#include <bits/stdc++.h>
#define MAXN 1000005
#define MOD 1000000007
using namespace std;
inline int read() {
int x=0,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();
}
return x*f;
}
int ans,n;
int num[MAXN];
void dfs(int i,int a,int b,int c,int d){
if (a<0||b<0||c<0||d<0) return ;
if (i==n+1&&a==0&&b==0&&c==0&&d==0) {
ans=(ans+1)%MOD;
return ;
}
if (num[i-1]==0){
num[i]=0;
dfs(i+1,a-1,b,c,d);
num[i]=1;
dfs(i+1,a,b,c-1,d);
}
else {
num[i]=0;
dfs(i+1,a,b,c,d-1);
num[i]=1;
dfs(i+1,a,b-1,c,d);
}
}
int main(){
n=read();
int a=read(),b=read(),c=read(),d=read();
num[1]=0;
dfs(2,a,b,c,d);
num[1]=1;
dfs(2,a,b,c,d);
printf("%d\n",ans);
}

$100pt$

我们考虑$a,b,c,d$对$B$,$G$的贡献,发现贡献$sumb=2a+c+d$,$sumg=2b+c+d$
其中中间部分的贡献算了两次,头和尾的贡献只算了一次,如果知道首尾的字母,就能知道整个序列中$B,G$的个数。

我们再把序列抽象成一段一段的$B$,$G$
如$…..GB…..BG……GB……BG…..$
我们发现$BG$,$GB$只出现在交界处。
所以我们发现一个很简单的性质:$abs(c-d)<=2$。
再yy一下
发现若$c==d$,那么序列首尾都为$G$或者都为$B$,
若$c==d+1$,那么序列首部为$B$,尾部为$G$,
若$c+1==d$,那么序列首部为$G$,尾部为$B$,
根据这个性质,我们就可以求出$B,G$的数量,若总数$>n$,则排列数为$0$

剩下的部分组合数爆推一波就可以了:
我们发现知道了头尾的字母,就知道了$B$区间和$G$区间的段数和位置。
考虑插板法,将$A$个字母分成$s1$段,每段不为$0$,总方法数:$C^{s1-1}_{A-1}$
把插入$B$的方法数和插入$G$的方法数相乘即可。


代码细节比较多

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
#include <bits/stdc++.h>
#define MAXN 2000005
#define MOD 1000000007
#define int long long
using namespace std;
inline int read() {
int x=0,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();
}
return x*f;
}
inline int Abs(int a){
return a>0?a:-a;
}
int fac[MAXN],inv[MAXN];
inline int ksm(int b,int k){
int ans=1;
while (k){
if (k&1) ans=(ans*b)%MOD;
b=(b*b)%MOD;
k>>=1;
}
return ans;
}
inline void Init(){
fac[0]=1;
for (register int i=1;i<MAXN;++i){
fac[i]=(fac[i-1]*i)%MOD;
}
}
inline int C(int n,int m){
if (n==0) return 1;
if (n==-1&&m==-1) return 1;
return fac[m]*ksm(fac[n],MOD-2)%MOD*ksm(fac[m-n],MOD-2)%MOD;
}
int n;
inline int Solve(int A,int B,int s1,int s2){//s1段A个数 s2段B个数
if (A+B!=n) return 0;
return C(s1-1,A-1)*C(s2-1,B-1)%MOD;
}
//还有BB,GG,BG,GB的总数,分别为a,b,c,d
#undef int
int main(){
#define int long long
Init();
n=read();int a=read(),b=read(),c=read(),d=read();
if (Abs(c-d)>=2){
puts("0");
return 0;
}
int sumb=a*2+c+d;
int sumg=b*2+c+d;
int ans=0;
//算出汉子妹子总数(相邻的算重复)
if (c==d){//两种情况:头尾为BB,或者GG
if (sumb&1||sumg&1) {
puts("0");
return 0;
}
else {
ans+=Solve((sumb+2)/2,sumg/2,c+1,c);
ans+=Solve(sumb/2,(sumg+2)/2,c,c+1);
}
}
else{//头尾一定为BG或GB
if ((!(sumb&1))||(!(sumg&1))){
puts("0");
return 0;
}
else {
ans+=Solve((sumb-1)/2+1,(sumg-1)/2+1,max(c,d),max(c,d));//两种情况合起来写
}
}
printf("%lld\n",ans);
}

p.s.可以在介里下载数据点击下载

 评论