ACM字符串
.长度不能超过n
.字符串中仅包含大写字母
.生成的字符串必须包含字符串“ACM”，ACM字符串要求连在一块！ ok，是不是很简单？现在告诉你n的值，你来告诉我这样的字符串有多少个 输入 输入一个正整数T，代表有T组数据
接下来T行，每行一个正整数n，n<=。 输出 输出符合条件的字符串的数目 样例输入 样例输出
做题过程：
- 熬了三四个小时，WA了无数次！最终推出了组合数的公式！
- 首先暴力打表，嘿嘿！这样极大地压缩计算时间！
- 打表如下：
一：生成连续的7位绝对不含ACM的数据的个数！
ll Els[];//生成7位绝对不含ACM的数据
int a[]; void dfs(int now,int len)
{
if(now>len)
{
Els[len]++;
return ;
}
for( int i=; i<=; i++)
{
a[now]=i;
if(now>=&&a[now]==&&a[now-]==&&a[now-]==)
continue;
dfs(now+,len);
}
}
int main()
{ for(int i=; i<=; i++)
{
dfs(,i);
printf("i=%d, %lld\n",i,Els[i]);
} cout<<"生成连续的7位绝对不含ACM的数据"<<endl;
for(int i=; i<=; i++)
{
printf("i=%d, %lld\n",i,Els[i]);
} return ;
} 二：开始进行组合数学处理，并且处理误差！
- 误差是怎么回事呢？举个栗子当“n=6时，形如当只含有一个ACM时—— “ACM_ _ _”这种样子C（4,1）种组合数（把ACM捆绑成一块！），然后需要C(4,1) 乘于其余三个空位上的数字组合，这三种数字“因为不能再含有ACM”直接调用上面求出的Els[3], 但是这里存在了误差！
- 仔细考虑一下，当出现“_ACM_ _”的组合的这种情况时，其实有Els[1]*Els[2] 种！也就是说中间的“ACM”隔开了两边，我上面求的那么“Els”的真实意思是“生成连续的7位绝对不含ACM的数据个数”！Els[1]*Els[2] -Els[3] = 1 ,这里的误差就是1！以此类推！
- 同理，其他的情况也是如此！多的位数可以跑循环进行枚举！手写就有点麻烦了！
#define ll long long
ll F[]; //n的阶乘
//ll f[12];
///chart表示连续的绝对不含ACM连续的字符串个数，就是上面求出的"Els 数组"
ll chart[]={, ,,, ,,, };
ll mistake[]; ///存储每个长度n的误差！
ll Cul(int m,int k) //计算C（m,k）的组合数
{
return F[m]/(F[k]*F[m-k] );
}
ll ans[]={,,,};
void init(){
F[]=;
for(int i=;i<=;i++) //n的阶乘！
F[i]=F[i-]*i;
memset(mistake,,sizeof(mistake));
mistake[]+= chart[]*chart[]*- *chart[];
mistake[]+= chart[]*chart[]*+chart[]*chart[]- *chart[];
mistake[]+= chart[]*chart[]*+chart[]*chart[]*- *chart[];
mistake[]+= chart[]*chart[]*+chart[]*chart[]*+chart[]*chart[] - *chart[];
mistake[]+= chart[]*chart[]* +chart[]*chart[]*chart[] - chart[]*; for(int i=;i<=;i++) ///__A_____
mistake[]+=chart[i]*chart[-i]-chart[];
for(int j=;j<=;j++){
for(int i=;i+j<=;i++) ///_A__A__(空出j个位置和i个位置和4-i-j个位置！！)
mistake[]+=chart[j]*chart[i]*chart[-i-j]-chart[];
} }
int main(){ init(); for(int j=;j<=;j++)
{
int n=j;
int num=n/;
ans[j]=ans[j-];
for(int i=;i<=num;i++){ //单个的，结果需要累加！！
ans[j]+=Cul(i+n-i*,i)*chart[n-i*] ;
}
// printf("j=%d, %lld\n",j,ans[j]);
ans[j]+= mistake[j];
// printf("+mis:: j=%d, %lld\n",j,ans[j]);
} int T;
scanf("%d",&T); while(T--){
int n;
cin>>n; printf("%lld\n",ans[n]);
} return ;
}
官方题解是数位DP来写，数位DP其实就是记忆化搜索+深搜！建议学学！