蒟蒻不会用基尔霍夫矩阵。。蒟蒻只会打表。。
打表发现答案为\(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\)就变成了上三角矩阵。主对角线乘积即为答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
// <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; } |
Orz