Python3 解法, 执行用时: 53ms, 内存消耗: 7088K, 提交时间: 2021-11-26 19:45:02

# 这不是指数生成函数例题吗？
# EGF是\frac{e^{2 x}}{2}+\frac{e^{4 x}}{4}+\frac{1}{4}
# 反演结果是1/4[n==0]+2^n/2+4^n/4
mod=10007
def qpow(a,n):
    ans=1
    while n:
        if n&0x01:
            ans=ans*a%mod
        a=a*a%mod
        n=n>>1
    return ans         


t=int(input())
while t:
    t=t-1
    n=int(input())
    if n==0:
        print(1)
    else:
        print((qpow(2,n-1)+qpow(4, n-1))%mod)
        

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 488K, 提交时间: 2023-08-12 17:17:39

#include<bits/stdc++.h>
using namespace std;
const int mod=1e4+7;
int ksm(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }return ans;
}
void solve()
{
    int n;
    cin>>n;
    cout<<(ksm(4,n-1)+ksm(2,n-1))%mod<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
        solve();
}

C++ 解法, 执行用时: 4ms, 内存消耗: 480K, 提交时间: 2022-02-22 20:39:42

#include<bits/stdc++.h>
using namespace std;
const int mod=10007;
int qmi(int a,int k)
{
    int res=1;
    while(k){
        if(k&1)res=res*a%mod;
        a=a*a%mod;k>>=1;
    }
    return res;
}
int main()
{   int n,T;scanf("%d",&T);
    while(T--)scanf("%d",&n),printf("%d\n",(qmi(4,n-1)+qmi(2,n-1))%mod);
}