正题

题目链接:http://poj.org/problem?id=3734

题目大意

用思种颜色给\(n\)个格子染色，要求前两种颜色出现偶数次，求方案。

\(1\leq T\leq 100,1\leq n\leq 10^9\)

解题思路

反正是\(\text{EGF}\)的十分入门题了。

首先是\(\sum_{i=0}^{\infty}\frac{x^i}{i!}=e^x\)。

这题带标号计数所以求的是

\[(\sum_{i=0}^\infty\frac{x^{2i}}{2i!})^2\times (\sum_{i=0}^\infty\frac{x^i}{i!})^2
\]

嗯，后面那个就是\(e^x\)，前面那个怎么搞。

考虑点花里胡哨的东西，\(e^{-x}=\sum_{i=0}^\infty (-1)^i\frac{x^i}{i!}\)，然后我们就有

\[\sum_{i=0}^\infty\frac{x^{2i}}{2i!}=\frac{e+e^{-x}}{2}
\]

然后带进式子就是

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

然后\(e^{ax}=\sum_{i=0}^{\infty}a^i\frac{x^i}{i!}\)，所以展开一下项就是

\[[x^n]=\frac{4^n+2^n\times 2}{4}=4^{n-1}+2^{n-1}
\]

时间复杂度\(O(T\log n)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int P=10007;

int n,T;

int power(int x,int b){

	int ans=1;

	while(b){

		if(b&1)ans=ans*x%P;

		x=x*x%P;b>>=1;

	}

	return ans;

}

int main()

{

	scanf("%d",&T);

	while(T--){

		scanf("%d",&n);n--;n%=(P-1);

		printf("%d\n",(power(2,n)+power(4,n))%P);

	}

}

巴特西

POJ3734-Blocks【EGF】

正题

题目大意

解题思路

code

最新文章

热门文章