poj 3734 Blocks【指数型生成函数】

指数型生成函数，推一推可得：

\[(1+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+...)^2+(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\frac{x^6}{6!}+...)^2
\]

\[=e^{2x}+(\frac{e^x+2^-x}{2})^2
\]

\[=e^{2x}+\frac{e^{2x}+e^{-2x}+2}{4}
\]

\[=\frac{e^{4x}+2e^{2x}+1}{4}
\]

因为

\[e^x=\sum_{i=0}^{inf}\frac{x^i}{i!},e^{4x}=\sum_{i=0}^{inf}\frac{(4x)^i}{i!}=\sum_{i=0}^{inf}\frac{4^ix^i}{i!}
\]

所以展开可得

\[=\frac{1}{4}+\frac{\sum_{i=0}^{inf}\frac{4^ix^i}{i!}+2*\sum_{i=0}^{inf}\frac{2^ix^i}{i!}}{4}
\]

\[=\frac{1}{4}+\frac{\sum_{i=0}^{inf}(4^i+2^{i+1})*\frac{x^i}{i!}}{4}
\]

前面的常数不用管，这样取i个的答案也就是第i项的系数就是\( 4ⁱ⁺²{i+1} \)

#include<iostream>

#include<cstdio>

using namespace std;

const int mod=10007;

int T,n;

int ksm(int a,int b)

{

	int r=1;

	while(b)

	{

		if(b&1)

			r=r*a%mod;

		a=a*a%mod;

		b>>=1;

	}

	return r;

}

int main()

{

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d",&n);

		printf("%d\n",(ksm(2,n-1)+ksm(4,n-1))%mod);

	}

	return 0;

}

巴特西

poj 3734 Blocks【指数型生成函数】

最新文章

热门文章