POJ 3734 Blocks

POJ_3734

    这个题目是《程序设计中的组合数学》中的一个例题，对于要求是偶数的，该项可以写成(exp(x)+exp(-x))/2，不做要求的可以写成exp(x)，把4项乘起来化简可得生成函数G(x)=(exp(4*x)+2*exp(2*x)+1)/4，所以x^n/(n!)那项的系数就是(4^n+2*2^n)/4，也就是(2^(n-1)+1)*2^(n-1)，之后用快速幂取模求得结果即可。

#include<stdio.h>
#include<string.h>
#define D 10007
int pow_mod(int n)
{
    int ans;
    if(n == 1)
        return 2;
    ans = pow_mod(n / 2);
    ans = ans * ans % D;
    if(n & 1)
        ans = ans * 2 % D;
    return ans;
}
void solve()
{
    int i, j, k, n, ans;
    scanf("%d", &n);
    ans = 1;
    -- n;
    if(n)
        ans = pow_mod(n);
    ans = (ans + 1) * ans % D;
    printf("%d\n", ans);
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t --)
    {
        solve();
    }
    return 0;
}