View Code of Problem 1087

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod=10007;
int pow_mod(int a,int b)
{
    int s=1;
    while(b)
    {
        if(b&1)
            s=(s*a)%mod;
        a=(a*a)%mod;
        b=b>>1;
    }
    return s;
}
int main()
{
    int T,tt=0;
    cin>>T;
    while(T--)
    {
        int n,ans;
        cin>>n;
        if(n&1)ans=(pow_mod(2,n-1)-1)*pow_mod(3,mod-2)%mod+2;
        else ans=(pow_mod(2,n-1)-2)*pow_mod(3,mod-2)%mod+2;
        cout<<"Case #"<<++tt<<": "<<(ans%mod+mod)%mod<<endl;
    }
    return 0;
}
/*
    就是打表+找规律
    得出的结果是f[n]=f[n-2]+2^(n-3),这里的结果间隔2，所以要分奇偶，f[1]=f[2]=2;
    n为偶数,f[n]=(2^(n-1)-2)/3+2;
    n为奇数,f[n]=(2^(n-1)-1)/3+2;
    这里需要解决的只有除法取余:
    1.可以用乘法的逆来解决，当然可知当成定理来用(a/b)%mod=(a*b^(mod-2))%mod,mod为素数
原理是费马小定理：a^(mod-1)%mod=1,又a^0%mod=1,所以a^(-1)=a^(mod-2),推出a/b=a*b^(-1)=a*b^(mod-2)
    2.上面的方法适合b比较大的时候，这里的b=3.很小，可知直接(a/b)%mod=(a%(mod*b)/b)%mod
    
    一开始自己不想推公式，百度别人的，。。被坑了。。
*/