http://acm.timus.ru/problem.aspx?space=1&num=1276
用 ans[numaa][numab][numba][numbb][0] 表示用 numaa个AA numab个AB numba个BA numbb个BB 以 A为结尾的种类数量
用 ans[numaa][numab][numba][numbb][1] 表示用 numaa个AA numab个AB numba个BA numbb个BB 以 B为结尾的种类数量
然后根据结尾是A还是B 进行向后更新数量
代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<queue>
#include<stack>
#include <iomanip>
using namespace std;
#define LL long long
const int INF=0x3f3f3f3f;
const int N=45;
LL ans[20005][2];
int aa,ab,ba,bb;
int F(int i,int j,int l,int r)
{
int x=r;
x+=(l*bb);
x+=(j*ba*bb);
x+=(i*ab*ba*bb);
return x;
}
int main()
{
//freopen("data.in","r",stdin);
int n,k;
while(cin>>n>>k)
{
ab=0;aa=0;ba=0;bb=0;
string stmp;
int locomotive;
cin>>stmp;
if(stmp=="AA") locomotive=0;
if(stmp=="AB") locomotive=1;
if(stmp=="BA") locomotive=2;
if(stmp=="BB") locomotive=3;
for(int i=1;i<=n;++i)
{
cin>>stmp;
if(stmp=="AA") ++aa;
if(stmp=="AB") ++ab;
if(stmp=="BA") ++ba;
if(stmp=="BB") ++bb;
}
++aa;++ab;++ba;++bb;
memset(ans,0,sizeof(ans));
if(locomotive==0||locomotive==2)
ans[0][0]=1;
else
ans[0][1]=1;
LL sum=0;
for(int i=0;i<aa;++i)
for(int j=0;j<ab;++j)
for(int l=0;l<ba;++l)
for(int r=0;r<bb;++r)
if(i+j+l+r<=k)
{
int x=F(i,j,l,r);
if(i+j+l+r==k)
{
if(locomotive==0||locomotive==1)
sum+=ans[x][0];
else
sum+=ans[x][1];
}
if(ans[x][0]!=0)
{
if(i+1<aa)
ans[F(i+1,j,l,r)][0]+=ans[x][0];
if(j+1<ab)
ans[F(i,j+1,l,r)][1]+=ans[x][0];
}
if(ans[x][1]!=0)
{
if(l+1<ba)
ans[F(i,j,l+1,r)][0]+=ans[x][1];
if(r+1<bb)
ans[F(i,j,l,r+1)][1]+=ans[x][1];
}
}
if(sum==0)
cout<<"NO"<<endl;
else
{cout<<"YES"<<endl;cout<<sum<<endl;}
}
return 0;
}
