Alien Flowers

题意：

求含有A个"RR"，B个"RB"，C个"BB"，D个"BR"的字符串个数。

解法：

首先考虑"BR"与"RB"，我们可以首先"B","R"相间来排列进而满足B，D的限制。

这样，我们只需要考虑将"BB"和"RR"塞入初始得到的串即可，考虑隔板法。

PS：这题数据"0 0 0 0"有毒。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 #define LL long long
 6 #define P 1000000007LL
 7 #define N 100010
 8 
 9 using namespace std;
10 
11 int a,b,c,d;
12 LL fac[N*2];
13 
14 LL qpow(LL x,int n)
15 {
16     LL ans=1;
17     for(;n;n>>=1,x=x*x%P)
18         if(n&1) ans=ans*x%P;
19     return ans;
20 }
21 
22 LL C(int n,int m)
23 {
24     if(m==0) return 1LL;
25     return fac[n]*qpow(fac[n-m],P-2)%P*qpow(fac[m],P-2)%P;
26 } 
27 
28 int main()
29 {
30     fac[0]=1;
31     for(int i=1;i<2*N;i++) fac[i] = fac[i-1]*(LL)i%P;
32     while(~scanf("%d%d%d%d",&a,&b,&c,&d))
33     {
34         if(b==0 && d==0)
35         {
36             if(a!=0 && c!=0) puts("0");
37             else if(a!=0 || c!=0) puts("1");
38             else puts("2");
39             continue;
40         }
41         LL ans;
42         if(b==d)
43         {
44             ans = C(c+b-1,b-1)*C(a+b,b)%P;
45             ans += C(c+b,b)*C(a+b-1,b-1)%P;
46             if(ans>=P) ans-=P;
47             cout << ans << endl;
48         }
49         else if(b==d+1 || d==b+1)
50         {
51             b = max(b,d); 
52             ans = C(b+c-1,b-1)*C(b+a-1,b-1)%P;
53             cout << ans << endl;
54         }
55         else puts("0");
56     }
57     return 0;
58 }

View Code