hdu 2065 红色病毒问题

本文主要是介绍hdu 2065 红色病毒问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

考虑生成函数
令 $G(x) = (1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} \cdots)^2 * (1 + \frac{x^2}{2!} + \frac{x^4}{4!} \cdots)^2$
考虑 $e^x = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} \cdots$
$e^{-x} = 1 - \frac{x}{1!} + \frac{x^2}{2!} - \frac{x^3}{3!} + \frac{x^4}{4!} \cdots$
则 $G(x) = e^{2x} + (\frac{e^x-e^{-x}}{2})^2$
化简可得 $\begin{align*} G(x) &=e^{2x}* \frac{e^{2x} + e^{-2x}+ 2}{4} \\ &= \frac{e^{4x} + 2*e^{2x}+ 1}{4}\\ &= \frac{(1 + \frac{4*x}{1!} + \frac{16*x^2}{2!} + \frac{64*x^3}{3!} + \frac{256*x^4}{4!} \cdots) + 2* (1 + \frac{2*x}{1!} + \frac{4*x^2}{2!} + \frac{8*x^3}{3!} + \frac{16*x^4}{4!} \cdots) + 1}{4}\\ &= (\frac{1}{4} + \frac{x}{1!} + \frac{4*x^2}{2!} + \frac{16*x^3}{3!} + \frac{64*x^4}{4!} \cdots) + (\frac{1}{2} + \frac{x}{1!} + \frac{2*x^2}{2!} + \frac{4*x^3}{3!} + \frac{8*x^4}{4!} \cdots) + \frac{1}{4} \end{align*}$
所以综上第 $n$ 项答案为 $4^{n-1}+2^{n-1} (mod\ 100)$
c++代码如下：

#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i = x ; i <= y; ++ i)
#define repd(i,x,y) for(register int i = x ; i >= y; -- i)
using namespace std;
typedef long long ll;
template<typename T>inline void read(T&x)
{char c;int sign = 1;x = 0;do { c = getchar(); if( c == '-' ) sign = -1; }while(!isdigit(c));do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));x *= sign;
}const int mod = 100;
int ksm(int x,ll y)
{int ans = 1;while(y){if(y&1) ans = ans * x %mod;x = x*x %mod;y >>= 1;}return ans;
}int main()
{int t; ll n;while(true){read(t);if(t == 0) break;rep(i,1,t){read(n);printf("Case %d: %d\n",i,(ksm(2,n-1)+ksm(4,n-1))%mod );}puts("");}return 0;    
}