Background

dts脑洞第2期

Description

将一个n棱锥的每个顶点染上一种颜色，有m种颜色可供使用，使得同一条棱的两端点异色，问有多少种不同的染色方式。
请回答方案数对k取模的结果，k将在输入中给出，数据保证k是一个质数。

Format

Input

输入包含多组数据，请处理到文件结束
每组数据1行，包含n,m,k三个数

Output

对于每组数据，输出一行一个数，方案数对k取模的结果

Sample 1

Input

3 4 10007

Output

9

Limitation

1s, 4194304KiB for each test case.

Hint

每组输入不超过10^5组数据
对于100%的数据，每组n,m,k满足，3≤n≤2^60,4≤m≤2^60,k≤2^30

C++ Code

#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

namespace dts
{
    typedef long long ll;
    
    ll n,m,key;
    
    ll qp(ll x,ll y,ll key)
    {
        ll ans=1;
        for (ll i=x,j=y;j>0;i=(i*i)%key,j/=2)
            if (j&1)
                ans=(ans*i)%key;
        return ans;
    }
    
    void main()
    {
        while (~scanf("%lld%lld%lld",&n,&m,&key))
        {
            m%=key;
            if (m-2<0)
                m+=key;
            ll ans=(m-1)*((qp(m-2,n-1,key)+((n&1)?-1:1))%key)%key;
            printf("%lld\n",ans);
        }
    }
};

int main()
{
    dts::main();
}

Source

Vijos Original