算法题

假设有这样一种字符串，它们的长度不大于 26 ，而且若一个这样的字符串其长度为 m ，则这个字符串必定由 a, b, c ... z 中的前 m 个字母构成，同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为 5 ，那么它一定是由 a, b, c, d, e 这 5 个字母构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些字母也就确定了，唯一的区别就是这些字母的前后顺序而已。

现在我们用一个由大写字母 A 和 B 构成的序列来描述这类字符串里各个字母的前后顺序：

如果字母 b 在字母 a 的后面，那么序列的第一个字母就是 A （After），否则序列的第一个字母就是 B （Before）；
如果字母 c 在字母 b 的后面，那么序列的第二个字母就是 A ，否则就是 B；
如果字母 d 在字母 c 的后面，那么 …… 不用多说了吧？直到这个字符串的结束。

这规则甚是简单，不过有个问题就是同一个 AB 序列，可能有多个字符串都与之相符，比方说序列“ABA”，就有“acdb”、“cadb”等等好几种可能性。说的专业一点，这一个序列实际上对应了一个字符串集合。那么现在问题来了：给你一个这样的 AB 序列，问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多大？注意，只要求个数，不要求枚举所有的字符串。

 最朴素的做法是把字母的所有排列情况列一下，符合题意的计数器+1，不过这种做法的计算量增长速度太快了，26个字母就要26!种排列，肯定无法在短时间内算出。没啥思路，那就穷举吧，穷举的时候能找到规律就好办了；由3个字母开始，再4个字母，穷举的过程果然有那么一点规律，抽象到一般就成了我最终使用的一个递归算法。

    列举的时候注意到，如果确定了第一个字母，那么顺序序列也会有相应的位置确定为A或者B。比如说，如果确定第一个字母为a，无论最终排列成什么情况，a肯定在b之前，于是序列中第一个字母为A；又比如第一个字母为c，则c肯定在d之前，也肯定在b之后，也就是说顺序序列第2，3个字母肯定为B，A。

    不妨假定一个序列X所对应的排列个数为F(X)。如果有一个顺序序列为ABAB，因为第一个字母为A，所以可能的一种排列为a????，????的排列必须满足BAB这个字串，这一共有F(BAB)种。同样可以验证b为首字母是不可能的，因为如果b是首字母，顺序序列必为BA??的形式；继续讨论c为首字母的情形： 原式中ABAB符合?BA?的要求，于是接下来问题是c????中的后????如何排列使得其满足a在b前（A）以及d在e后（B）这样的要求，可以把????看成4个空位，拆成两组分别有2个空位一共有C(4,2)中拆法，每种拆法中，一组中成员的顺序分别有F(A)=1和F(B)=1种，根据乘法原理，首字母为c的排列就可能有C(4,2)*F(A)*F(B)。。。不难发现对每个首字母都可以进行这样的递归处理，最后合并起来就是所有情况。

    数据结构的选择上，可以令A=0,B=1，则顺序序列转化为一个整数，这在处理问题上将大大简化操作。最后程序如下@VC6。其中solve2是朴素方法验证。（超过10亿为-1的那个要求没做）

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int combine( int m, int n )
{
 if( m < n )
  return -1;
 if( n > m / 2 )
  n = m - n;

 int ans = 1;
 for( int i = 1; i <= n; i++ )
  ans = ans * ( m - n + i ) / i;
 return ans;
}

int solve( int x, int n )
{
 int ans = 0;
 if( n == 1 || n == 0 )
  return 1;
 else if( n == 2 )
 {
  if( (x&3) == 1 || (x&3) == 2 ) // AB,BA有2种
   return 2;
  else // AA,BB只有一种
   return 1;
 }
 else
 {
  if( !(x&(1<<(n-1))) ) //首位是0(A)
   ans += solve( x, n-1 );
  if( x&1 ) //末尾是1(B)
   ans += solve( x >> 1, n-1 );
  for( int i = 0; i <= n - 2; i++ )
   if( (((x>>(i+1))&1)==1) && ((((x>>i)|0)&1)==0) ) //某一位起连续两个字母为BA
    ans += combine( n, i+1 ) * solve( x, i ) * solve( x >> (i+2), n-i-2 );
 }
 return ans;
}

int solve2( int x, int n )
{
 int i,cntr,inter,lad=1,ans=0;
 vector<char> C;
 vector<int> M;
 n++;
 for( i = 1; i <= n; i++ )
 {
  C.push_back( char('a'+i-1) );
  M.push_back( i-1 );
  lad *= i;
 }
 cntr = 0;
 do
 {
  inter = 0;
  for( i = 0; i < n; i++ )
   M[ int(C[ i ] - 'a') ] = i;
  for( i = 0; i < n-1; i++ )
  {
   inter <<= 1;
   if( M[ i ] > M[ i + 1 ] )
    inter |= 1;
  }
  if( inter == x )
   ans++;
  next_permutation( C.begin( ), C.end( ) );
  cntr++;
 }while( cntr < lad );

 return ans;
}

int main( )
{
 // BABABABABA->10,1010,1010->0x2aa
 cout << solve2( 0x2aa, 10 ) << endl;
 cout << solve( 0x2aa, 10 ) << endl;
 return 0;
}