CF1674C的题解

osfly / 2023-08-25 / 原文

有意思的题目。

还是比较好想的。

先考虑 -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;
}