2019 牛客多校第一场 E ABBA
题目链接：https://ac.nowcoder.com/acm/contest/881/E
题目大意
问有多少个由 (n + m) 个 ‘A’ 和 (n + m) 个 ‘B’，组成的字符串能被分割成 (n + m) 个长度为 2 的子序列，其中恰好有 n 个 “AB”，和 m 个 “BA”。
分析1（DP）
首先，如果一个串是合法的，那么我们可以用贪心的思路找到一种必然正确的划分子序列的方法：前 n 个 A 分配给 AB，后 m 个 A 分配给 BA，B 同理。
设 dp[i][j] 表示有 i 个 A 和 j 个 B 的合法前缀方案数。
对于每一个前缀合法字符串，它下一个长度的前缀合法字符串有 2 种选择，在结尾加 A 或是加 B，为什么不在中间加？因为中间加的情况可以转化为另一个前缀合法字符串在结尾加字符，所以只要讨论在结尾加即可。
接下来讨论一下不合法情况，由于是在结尾加，比如说加 A，在加之前，A 的数量不能超过 B 的数量加 n，不然的话会出现多余的 A。B 同理。
最后就是状态转移方程了：
- dp[i][j] 由末尾加 A 得到，所以 dp[i][j] = dp[i][j] + dp[i - 1][j]。
- dp[i][j] 由末尾加 B 得到，所以 dp[i][j] = dp[i][j] + dp[i][j - 1]。
- dp[i][j] 不合法，为 0。
代码如下
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 5 #define Rep(i,n) for (int i = 0; i < (n); ++i) 6 #define For(i,s,t) for (int i = (s); i <= (t); ++i) 7 #define rFor(i,t,s) for (int i = (t); i >= (s); --i) 8 #define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i) 9 #define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i) 10 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 11 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) 12 13 #define pr(x) cout << #x << " = " << x << " " 14 #define prln(x) cout << #x << " = " << x << endl 15 16 #define LOWBIT(x) ((x)&(-x)) 17 18 #define ALL(x) x.begin(),x.end() 19 #define INS(x) inserter(x,x.begin()) 20 #define UNIQUE(x) x.erase(unique(x.begin(), x.end()), x.end()) 21 #define REMOVE(x, c) x.erase(remove(x.begin(), x.end(), c), x.end()); // ?? x ?????? c 22 #define TOLOWER(x) transform(x.begin(), x.end(), x.begin(),::tolower); 23 #define TOUPPER(x) transform(x.begin(), x.end(), x.begin(),::toupper); 24 25 #define ms0(a) memset(a,0,sizeof(a)) 26 #define msI(a) memset(a,inf,sizeof(a)) 27 #define msM(a) memset(a,-1,sizeof(a)) 28 29 #define MP make_pair 30 #define PB push_back 31 #define ft first 32 #define sd second 33 34 template<typename T1, typename T2> 35 istream &operator>>(istream &in, pair<T1, T2> &p) { 36 in >> p.first >> p.second; 37 return in; 38 } 39 40 template<typename T> 41 istream &operator>>(istream &in, vector<T> &v) { 42 for (auto &x: v) 43 in >> x; 44 return in; 45 } 46 47 template<typename T> 48 ostream &operator<<(ostream &out, vector<T> &v) { 49 Rep(i, v.size()) out << v[i] << " "[i == v.size()]; 50 return out; 51 } 52 53 template<typename T1, typename T2> 54 ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) { 55 out << "[" << p.first << ", " << p.second << "]" << " "; 56 return out; 57 } 58 59 inline int gc(){ 60 static const int BUF = 1e7; 61 static char buf[BUF], *bg = buf + BUF, *ed = bg; 62 63 if(bg == ed) fread(bg = buf, 1, BUF, stdin); 64 return *bg++; 65 } 66 67 inline int ri(){ 68 int x = 0, f = 1, c = gc(); 69 for(; c<48||c>57; f = c=='-'?-1:f, c=gc()); 70 for(; c>47&&c<58; x = x*10 + c - 48, c=gc()); 71 return x*f; 72 } 73 74 template<class T> 75 inline string toString(T x) { 76 ostringstream sout; 77 sout << x; 78 return sout.str(); 79 } 80 81 inline int toInt(string s) { 82 int v; 83 istringstream sin(s); 84 sin >> v; 85 return v; 86 } 87 88 //min <= aim <= max 89 template<typename T> 90 inline bool BETWEEN(const T aim, const T min, const T max) { 91 return min <= aim && aim <= max; 92 } 93 94 typedef long long LL; 95 typedef unsigned long long uLL; 96 typedef pair< double, double > PDD; 97 typedef pair< int, int > PII; 98 typedef pair< int, PII > PIPII; 99 typedef pair< string, int > PSI; 100 typedef pair< int, PSI > PIPSI; 101 typedef set< int > SI; 102 typedef set< PII > SPII; 103 typedef vector< int > VI; 104 typedef vector< double > VD; 105 typedef vector< VI > VVI; 106 typedef vector< SI > VSI; 107 typedef vector< PII > VPII; 108 typedef map< int, int > MII; 109 typedef map< int, string > MIS; 110 typedef map< int, PII > MIPII; 111 typedef map< PII, int > MPIII; 112 typedef map< string, int > MSI; 113 typedef map< string, string > MSS; 114 typedef map< PII, string > MPIIS; 115 typedef map< PII, PII > MPIIPII; 116 typedef multimap< int, int > MMII; 117 typedef multimap< string, int > MMSI; 118 //typedef unordered_map< int, int > uMII; 119 typedef pair< LL, LL > PLL; 120 typedef vector< LL > VL; 121 typedef vector< VL > VVL; 122 typedef priority_queue< int > PQIMax; 123 typedef priority_queue< int, VI, greater< int > > PQIMin; 124 const double EPS = 1e-8; 125 const LL inf = 0x7fffffff; 126 const LL infLL = 0x7fffffffffffffffLL; 127 const LL mod = 1e9 + 7; 128 const int maxN = 2e3 + 7; 129 const LL ONE = 1; 130 const LL evenBits = 0xaaaaaaaaaaaaaaaa; 131 const LL oddBits = 0x5555555555555555; 132 133 // dp[i][j] 表示有 i 个 A 和 j 个 B 的合法前缀方案数 134 int n, m, dp[maxN][maxN]; 135 136 int main(){ 137 //freopen("MyOutput.txt","w",stdout); 138 //freopen("input.txt","r",stdin); 139 //INIT(); 140 while(~scanf("%d%d", &n, &m)) { 141 dp[0][0] = 1; 142 Rep(i, n + m + 1) { 143 Rep(j, n + m + 1) { 144 if(!i && !j) continue; 145 dp[i][j] = 0; 146 if (i > 0 && j >= i - n) dp[i][j] = (dp[i - 1][j] + dp[i][j]) % mod; // 在最后加 A 147 if (j > 0 && i >= j - m) dp[i][j] = (dp[i][j - 1] + dp[i][j]) % mod; // 在最后加 B 148 } 149 } 150 151 printf("%d ", dp[n + m][n + m]); 152 } 153 return 0; 154 }
分析2（卡特兰数的折线法）
关于折线法：https://blog.csdn.net/qq_26525215/article/details/51453493
一共有四种情况：
- m = 0 && n = 0：此时答案为 1。
- m > 0 && n = 0：此时退化成纯卡特兰数问题，答案为${{2m}choose{m}} - {{2m}choose{m - 1}}$。
- m = 0 && n > 0：此时退化成纯卡特兰数问题，答案为${{2n}choose{n}} - {{2n}choose{n - 1}}$。
- m > 0 && n > 0：这种是卡特兰数的变化，对应在折线图上就是从一条线变成了上下两条边界线，答案为${{2(n + m)}choose{n + m}} - {{2(n + m)}choose{m - 1}} - {{2(n + m)}choose{n - 1}}$。
代码如下
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 5 #define Rep(i,n) for (int i = 0; i < (n); ++i) 6 #define For(i,s,t) for (int i = (s); i <= (t); ++i) 7 #define rFor(i,t,s) for (int i = (t); i >= (s); --i) 8 #define ForLL(i, s, t) for (LL i = LL(s); i <= LL(t); ++i) 9 #define rForLL(i, t, s) for (LL i = LL(t); i >= LL(s); --i) 10 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i) 11 #define rforeach(i,c) for (__typeof(c.rbegin()) i = c.rbegin(); i != c.rend(); ++i) 12 13 #define pr(x) cout << #x << " = " << x << " " 14 #define prln(x) cout << #x << " = " << x << endl 15 16 #define LOWBIT(x) ((x)&(-x)) 17 18 #define ALL(x) x.begin(),x.end() 19 #define INS(x) inserter(x,x.begin()) 20 #define UNIQUE(x) x.erase(unique(x.begin(), x.end()), x.end()) 21 #define REMOVE(x, c) x.erase(remove(x.begin(), x.end(), c), x.end()); // ?? x ?????? c 22 #define TOLOWER(x) transform(x.begin(), x.end(), x.begin(),::tolower); 23 #define TOUPPER(x) transform(x.begin(), x.end(), x.begin(),::toupper); 24 25 #define ms0(a) memset(a,0,sizeof(a)) 26 #define msI(a) memset(a,inf,sizeof(a)) 27 #define msM(a) memset(a,-1,sizeof(a)) 28 29 #define MP make_pair 30 #define PB push_back 31 #define ft first 32 #define sd second 33 34 template<typename T1, typename T2> 35 istream &operator>>(istream &in, pair<T1, T2> &p) { 36 in >> p.first >> p.second; 37 return in; 38 } 39 40 template<typename T> 41 istream &operator>>(istream &in, vector<T> &v) { 42 for (auto &x: v) 43 in >> x; 44 return in; 45 } 46 47 template<typename T> 48 ostream &operator<<(ostream &out, vector<T> &v) { 49 Rep(i, v.size()) out << v[i] << " "[i == v.size()]; 50 return out; 51 } 52 53 template<typename T1, typename T2> 54 ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) { 55 out << "[" << p.first << ", " << p.second << "]" << " "; 56 return out; 57 } 58 59 inline int gc(){ 60 static const int BUF = 1e7; 61 static char buf[BUF], *bg = buf + BUF, *ed = bg; 62 63 if(bg == ed) fread(bg = buf, 1, BUF, stdin); 64 return *bg++; 65 } 66 67 inline int ri(){ 68 int x = 0, f = 1, c = gc(); 69 for(; c<48||c>57; f = c=='-'?-1:f, c=gc()); 70 for(; c>47&&c<58; x = x*10 + c - 48, c=gc()); 71 return x*f; 72 } 73 74 template<class T> 75 inline string toString(T x) { 76 ostringstream sout; 77 sout << x; 78 return sout.str(); 79 } 80 81 inline int toInt(string s) { 82 int v; 83 istringstream sin(s); 84 sin >> v; 85 return v; 86 } 87 88 //min <= aim <= max 89 template<typename T> 90 inline bool BETWEEN(const T aim, const T min, const T max) { 91 return min <= aim && aim <= max; 92 } 93 94 typedef long long LL; 95 typedef unsigned long long uLL; 96 typedef pair< double, double > PDD; 97 typedef pair< int, int > PII; 98 typedef pair< int, PII > PIPII; 99 typedef pair< string, int > PSI; 100 typedef pair< int, PSI > PIPSI; 101 typedef set< int > SI; 102 typedef set< PII > SPII; 103 typedef vector< int > VI; 104 typedef vector< double > VD; 105 typedef vector< VI > VVI; 106 typedef vector< SI > VSI; 107 typedef vector< PII > VPII; 108 typedef map< int, int > MII; 109 typedef map< int, string > MIS; 110 typedef map< int, PII > MIPII; 111 typedef map< PII, int > MPIII; 112 typedef map< string, int > MSI; 113 typedef map< string, string > MSS; 114 typedef map< PII, string > MPIIS; 115 typedef map< PII, PII > MPIIPII; 116 typedef multimap< int, int > MMII; 117 typedef multimap< string, int > MMSI; 118 //typedef unordered_map< int, int > uMII; 119 typedef pair< LL, LL > PLL; 120 typedef vector< LL > VL; 121 typedef vector< VL > VVL; 122 typedef priority_queue< int > PQIMax; 123 typedef priority_queue< int, VI, greater< int > > PQIMin; 124 const double EPS = 1e-8; 125 const LL inf = 0x7fffffff; 126 const LL infLL = 0x7fffffffffffffffLL; 127 const LL mod = 1e9 + 7; 128 const int maxN = 1e5 + 7; 129 const LL ONE = 1; 130 const LL evenBits = 0xaaaaaaaaaaaaaaaa; 131 const LL oddBits = 0x5555555555555555; 132 133 LL fac[maxN]; 134 void init_fact() { 135 fac[0] = 1; 136 For(i, 1, maxN - 1) fac[i] = (i * fac[i - 1]) % mod; 137 } 138 139 //ax + by = gcd(a, b) = d 140 // 扩展欧几里德算法 141 inline void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d){ 142 if (!b) {d = a, x = 1, y = 0;} 143 else{ 144 ex_gcd(b, a % b, y, x, d); 145 y -= x * (a / b); 146 } 147 } 148 149 // 求a关于p的逆元，如果不存在，返回-1 150 // a与p互质，逆元才存在 151 inline LL inv_mod(LL a, LL p = mod){ 152 LL d, x, y; 153 ex_gcd(a, p, x, y, d); 154 return d == 1 ? (x % p + p) % p : -1; 155 } 156 157 inline LL comb_mod(LL m, LL n) { 158 LL ret; 159 160 if(m > n) swap(m, n); 161 162 ret = (fac[n] * inv_mod(fac[m], mod)) % mod; 163 ret = (ret * inv_mod(fac[n - m], mod)) % mod; 164 165 return ret; 166 } 167 168 LL n, m, ans; 169 170 int main(){ 171 //freopen("MyOutput.txt","w",stdout); 172 //freopen("input.txt","r",stdin); 173 //INIT(); 174 init_fact(); 175 while(~scanf("%lld%lld", &n, &m)) { 176 ans = comb_mod(n + m, 2 * (n + m)); 177 if(n) ans -= comb_mod(n - 1, 2 * (n + m)); 178 if(m) ans -= comb_mod(m - 1, 2 * (n + m)); 179 ans = (ans + 2 * mod) % mod; 180 printf("%lld ", ans); 181 } 182 return 0; 183 }