有意思的题目。
还是比较好想的。
先考虑 -1
的情况,可以想到,如果 \(t\) 的长度不为 \(1\),并且 \(t\) 里面还有 a
的话,那么这个新的 a
又能被下一个 \(t\) 替换,无限套娃。
剩下的,还是有两种情况:
-
如果 \(t\) 只有一个字符
a
,那么 \(s\) 无论怎么被替换都是一样的(全部都是a
),所以,这种情况输出1
。 -
如果不是第
1
种情况,那么最终的答案就为:\(\large C^0_n+C^1_n+C^2_n+C^3_n+...+C^n_n\)
其实上面这个式子很好理解,只要从 \(s\) 里分别选出 \(0\) 个,\(1\) 个,\(2\) 个,......,\(n\) 个
a
出来被替换就是最后的方案数。根据组合数的定义,可以知道上面的式子就是 \(\large2^n\)。
为了加快效率,可以使用
cmath
的pow
函数,也可以先预处理所有的 \(\large 2^i\) 的值。
code
#include<cstdio>
#include<cstring>
int q;
char s[100],t[100];
unsigned long long pow[100];
void init()
{
pow[0]=1;
for(int i=1;i<=50;i++) pow[i]=pow[i-1]*2;
}
int main()
{
init();
scanf("%d",&q);
while(q--)
{
scanf(" %s %s",s+1,t+1);
int le=strlen(s+1);
int len=strlen(t+1);
//-1
if(len>1)
{
bool yes=0;
for(int i=1;i<=len;i++)
if(t[i]=='a')
{
yes=1;
break;
}
if(yes)
{
printf("-1\n");
continue;
}
else printf("%lld\n",pow[le]);
}
else
{
if(t[1]=='a') printf("1\n");
else printf("%lld\n",pow[le]);
}
}
return 0;
}
标签:int,题解,long,CF1674C,pow,100,include
From: https://www.cnblogs.com/osfly/p/17657941.html