【BZOJ4766】文艺计算姬 – 徐亦轲的博客

蒟蒻不会用基尔霍夫矩阵。。蒟蒻只会打表。。

~~打表发现答案为$n^{m-1}m^{n-1}$~~

把它的基尔霍夫矩阵写出来大概就是

$$\begin{bmatrix}
m&0&\cdots&-1&-1\\
0&m&\cdots&-1&-1\\
\vdots&\vdots&\ddots&\vdots&\vdots\\
-1&-1&\cdots&n&0\\
-1&-1&\cdots&0&n\\
\end{bmatrix}$$

去掉最后一行最后一列

把其他所有行加到第$n$行可以得到一个只有前$n$位为$1$的向量

用它去消掉后$m-1$行的$-1$就变成了上三角矩阵。主对角线乘积即为答案。

// <4766.cpp> - Tue Mar  7 19:53:11 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=100001;
const int INF=1e9;
lol p;
lol qc(lol x,lol y){
    lol res=0;
    while(y){
        if(y&1)res=(res+x)%p;
        x=(x+x)%p;
        y>>=1;
    }
    return res;
}
lol qpow(lol x,lol y){
    lol res=1;
    while(y){
        if(y&1)res=qc(res,x);
        x=qc(x,x);
        y>>=1;
    }
    return res;
}
int main(){
    lol n=gl(),m=gl();p=gl();
    printf("%lld",qc(qpow(n,m-1),qpow(m,n-1)));
    return 0;
}

// <4766.cpp> - Tue Mar 7 19:53:11 2017

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

template<typename T>

inline void gg(T &res){

res=0;T fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

res*=fh;

}

inline int gi(){int x;gg(x);return x;}

inline lol gl(){lol x;gg(x);return x;}

const int MAXN=100001;

const int INF=1e9;

lol p;

lol qc(lol x,lol y){

lol res=0;

while(y){

if(y&1)res=(res+x)%p;

x=(x+x)%p;

y>>=1;

}

return res;

}

lol qpow(lol x,lol y){

lol res=1;

while(y){

if(y&1)res=qc(res,x);

x=qc(x,x);

y>>=1;

}

return res;

}

int main(){

lol n=gl(),m=gl();p=gl();

printf("%lld",qc(qpow(n,m-1),qpow(m,n-1)));

return 0;

}