https://vjudge.net/problem/HDU-2065
题意：现在有一长度为N的字符串,满足一下条件:
(1) 字符串仅由A,B,C,D四个字母组成;
(2) A出现偶数次(也可以不出现);
(3) C出现偶数次(也可以不出现);
计算满足条件的字符串个数.
当N=2时,所有满足条件的字符串有如下6个:BB,BD,DB,DD,AA,CC.
由于这个数据肯能非常庞大,你只要给出最后两位数字即可.
题解：(1+x/1!+x2/2!+x3/3!……)2*(1+x2/2!+x4/4!+x6/6!……)2。题目就是要求出xn/n!的系数。
由泰勒公式(1+x/1!+x2/2!+x3/3!……)2*(1+x2/2!+x4/4!+x6/6!……)^2 = e2x*(1/4)*(ex+e-x)2=1/4(e4x+1+2e2x)，再将最后的公式做泰勒展开得到xn/n!的系数为4(n-1)+2^(n-1)
如图
#include <cstdio>
#include<string.h>
using namespace std;
typedef long long LL;
const LL mod=100;
LL fast_multi(LL a,LL b)
{
LL base=a,res=0;
while(b)
{
if(b&1) res=(res+base)%mod;
b>>=1;
base=(base+base)%mod;
}
return res;
}
LL pow_mod(LL a,LL b)
{
LL base=a,res=1;
while(b)
{
if(b&1) res=fast_multi(res,base);
b>>=1;
base=fast_multi(base,base);
}
return res;
}
int main()
{
int t;
LL n;
while(scanf("%d",&t)!=EOF,t)
{
int cas=1;
while(t--)
{
scanf("%lld",&n);
LL res=(pow_mod(4,n-1)+pow_mod(2,n-1))%mod;
printf("Case %d: %lld\n",cas++,res);
}
printf("\n");
}
return 0;
}
