http://acm.hdu.edu.cn/showproblem.php?pid=4990

既然分奇偶,就考察 的关系,稍微推一下即有:
为奇数时,有
为偶数时,有
注意特判 m == 1

(只贴出与题目有关的代码,宏定义见 GitHub

ll powsum(ll a, ll r, ll mod)
{
    ll ans = 1LL, tmp = 1LL;
    for (; r; r >>= 1)
    {
        if (r & 1) ans = (ans * a + tmp) % mod;
        tmp = tmp * (1LL + a) % mod;
        a = a * a % mod;
    }
    return ans;
}

ll solve(ll n, ll m)
{
    if (m == 1) return 0;
    if (n & 1) return powsum(4, (n - 1) / 2, m);
    return powsum(4, (n - 2) / 2, m) * 2 % m;
}

int main()
{
    ll n, m;
    while (~SLL(n, m)) PL(solve(n, m));
    return 0;
}

Comments

comments powered by Disqus