POJ3734 Blocks（组合计数+快速幂）

题目链接

题意：n 个方块排成一排，用蓝黄红绿 4 种颜色涂色。要求涂红和绿的方块个数都为偶数，问有多少种涂色方案。

只要推导出通项公式即可：

首先将这排方框分成两个部分:   1.用蓝黄两种颜色上色   2.用红绿两种颜色上色。

前面的部分上色的方法数：2^(n-k)。(k 为偶数,k > 0)其他部分上色的方法数位:C(k,0)+C(k,2)+…C(K,4)+C(k,k) = 2^(k-1).(二项式系数的偶数项之和与奇数项之和相等)

得出 K 个方框上红绿的方法数：2^(n-k) * 2^(k-1) = 2^(n -1).

所以

ans = C(n,0)*2^(n)+C(n,2)*2^(n-1)+C(n,4)*2^(n-1)+… C(n,k) *2^(n-1) ….

=  2^(n-1)* (2+C(n,2)+C(n,4)+… C(n,k) …)

= 2^(n-1) *( 1+C(n,0)+C(n,2)+C(n,4)+… C(n,k) …)

= 2^(n-1) *(1+2*(n-1) )

= 2^(n-1)+4^(n-1)

当 n=0，ans=0; 当 n=1，ans=2。

然后用快速幂优化。

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MOD = 10007;
int n;
long long quickmod(long long a, long long n, long long MOD){
    long long r = 1;
    while(n){
        if(n&1){
            r = (a*r)%MOD;
        }
        a = (a*a)%MOD;
        n >>= 1;
    }
    return r;
}

long long cal(){
    long long ans = (quickmod(2, n-1, MOD)+quickmod(4, n-1, MOD))%MOD;
    return ans;
}

int main(){
    //freopen("a.txt", "r", stdin);
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        if(n == 0) cout << "0" << endl;
        else if(n == 1) cout << "2" << endl;
        else cout << cal() << endl;
    }
    return 0;
}