呜呜。这题太难受了，还不知道以怎样的方式写能把其中的巧妙思维方式解释清楚。
先把做法的表象讲讲吧：
考虑翻折容斥。我以为这个做不了，实际是可以的啊！把 \(+1,-1,0\) 分别记作 A,B,X。则要求相当于，固定 A,B,X 分别的个数（记为 \(a,b,x\)），但要求不能出现连续的 AA 或者 BB 且前缀和非负的方案数。
很多同学会沿如下方向去想：注意到 X 只有分割作用，因此直接将其分成了 \(x+1\) 段，每段都形如 ABABABABA... 或 BABABABAB...，然后用一些多项式把它们套起来。笔者场上就这么想的，最后 \(n^3\) 遗憾离场。
这样为什么不优呢？主要是因为我们多加了以一个维度，就要多枚举一个量，复杂度自然就上来了。因此我们要把这个字符串当成一个整体考虑。
前缀和非负这个条件，从整体上，还是只能从翻折容斥的角度考虑，因为其它法子好像都不怎么行得通。在这题里，比普通的翻折容斥增加的要求只有：不能相邻 AA 和 BB。
看着像一个不能刻画的信息。不过实际上，我们还要想办法找找方法。总方案数我们记为 \(f(a,b,x)\)。则答案应为 \(f(a,b,x)\) 减如下一个量：
- 考虑到，一共走了 \(a+b\) 个有效步，走到了 \(a-b\)，现在要翻折为 \(-2-(a-b)=b-a-2\)，因此要走 \(b-1\) 个 \(+1\) 和 \(a+1\) 个 \(-1\)。因为 AA 和 BB 有人为的对称性，因此转换之后要求基本不会有变化。
- 唯一的变化在于，第一个翻折点那里。显然降为 \(-1\) 时需要一个 B，也就是下一个字母不能是 B，只能为 A 或 X。所以剩余方案数应该是：在第一处 \(<0\) 位置之后一个字符只能为 B 或 X。
- 情况一：为 B。此时注意到把这相邻两个 B 改成一个 B 不会有任何变化，因为我们还是可以定位出这个进入 \(<0\) 的位置，从而恢复原序列。因此答案就是 \(f(b-1,a+1-1,x)\)。
- 情况二：为 X。此时我们也把这个 X 去掉，通过新字符串也是可以还原出来的，对应的是 \(f(b-1,a+1,x-1)\)。
- 然而，有可能原来这里出现了 BXB 状物，去掉了之后变成了 BB，并不会在后面的 \(f\) 函数中统计到。因此这里要特殊考虑，其实可以把 XB 一起去掉就好了。答案是 \(f(b-1,a+1-1,x-1)\)。
这样，就把答案转化成了 \(O(1)\) 个 \(f(a,b,x)\) 加加减减。现在考虑一个 \(f\) 怎么求？这个仍然没那么好做。
一种想法，还是按 X 分段。然后你不出意外地又寄了，复杂度仍然要平方。
所以你只能考虑另一个办法：容斥。考虑所有相邻不合法的位置，我们钦定其中一些。也就是把这个字符序列分出段来，每一段记录具体信息：是几个 A 或是几个 B 或是 X。容斥系数显然就是 \((-1)^{\sum (len-1)}\)。段内的大小顺序要先确定好（两个 \(1\) 只有一种排法，一个 \(1\) 一个 \(2\) 有两种，这个可以直接拆成不定方程解来刻画）。因此，设分别有 \(a',b',x\) 段，则方案数为 \(\dfrac{(a'+b'+x)!C(a-1,a'-1)C(b-1,b'-1)}{a'!b'!x!}\)。
结果你发现，还是平方优化不掉，流泪！
最后说出最终做法，很神奇：考虑 \(a=0\) 时的特殊（要特判的）情况：这也可以理解为经典不定方程解数，答案为 \(C(x+1,b)\)。你会发现，钦定完 A 的分段后，我们可以把它理解为和 X 类似的东西，加在一起。于是答案就是：\(C(a-1,a'-1)C(x+a',x)C(a'+x+1,b)\) 即为其方案数！
最后总复杂度线性。太厉害啦，膜拜膜拜。
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int powdv(int x,int y=mod-2){
int ans=1;
while(y){
if(y&1)ans=1ll*ans*x%mod;
y>>=1,x=1ll*x*x%mod;
}
return ans;
}
int di[20000005],id[20000005];
void init(int n){
di[0]=1;
for(int i=1;i<=n;++i)di[i]=1ll*i*di[i-1]%mod;
id[n]=powdv(di[n]);
for(int i=n-1;i>=0;--i)id[i]=1ll*id[i+1]*(i+1)%mod;
}
int C(int n,int m){
if(n<0||m<0||n<m)return 0;
return 1ll*di[n]*id[m]%mod*id[n-m]%mod;
}
int suan(int a,int b,int x){
if(x<0)return 0;
if(a==0&&b==0)return 1;
if(a==0||b==0)return C(x+1,a+b);
int ans=0;
for(int i=0;i<=a-1;++i){
ans=(ans+1ll*C(a-1,i)*(i%2?mod-1:1)%mod*C(x+a-i,x)%mod*C(a-i+x+1,b))%mod;
}
return ans;
}
int main(){
int n,a,b;
scanf("%d%d%d",&n,&a,&b);
init(n);
int x=n-a-b;
int ans=suan(a,b,x);
ans=(ans-suan(b-1,a,x))%mod;
ans=(ans-suan(b-1,a+1,x-1))%mod;
ans=(ans-suan(b-1,a,x-1))%mod;
printf("%d\n",(ans+mod)%mod);
return 0;
}