现在有一长度为N的字符串,满足一下条件:
(1) 字符串仅由A,B,C,D四个字母组成;
(2) A出现偶数次(也可以不出现);
(3) C出现偶数次(也可以不出现);
计算满足条件的字符串个数.
当N=2时,所有满足条件的字符串有如下6个:BB,BD,DB,DD,AA,CC.
由于这个数据肯能非常庞大,你只要给出最后两位数字即可.
(1) 字符串仅由A,B,C,D四个字母组成;
(2) A出现偶数次(也可以不出现);
(3) C出现偶数次(也可以不出现);
计算满足条件的字符串个数.
当N=2时,所有满足条件的字符串有如下6个:BB,BD,DB,DD,AA,CC.
由于这个数据肯能非常庞大,你只要给出最后两位数字即可.
直接用公式： 4^n-1+2^n-1;
#include<stdio.h>
#include<string.h>
int fun(int m,__int64 n)
{
int res=1;
while(n)
{
if(n&1)
res=res*m%100;
m=m*m%100;
n>>=1;
}
return res;
}
int main()
{
int ncase,i=1;
__int64 n;
while(scanf("%d",&ncase),ncase)
{
for(i=1;i<=ncase;i++)
{
scanf("%I64d",&n); //n没有定义成__int64,超时，
printf("Case %d: %d\n",i,(fun(4,n-1)+fun(2,n-1))%100);
}
puts("");
}
return 0;
}