本文共 1735 字，大约阅读时间需要 5 分钟。
利用二项式定理，可以可以将x^k*k^x展开得x^(k-1)*(1+k-1)^x从而得到递推关系，构造出矩阵直接快速幂就好了。
#include #include #include #include #include #include #include #include #include #include using namespace std; #define MP make_pair#define PB push_backtypedef long long LL;typedef unsigned long long ULL;typedef vector VI;typedef pair PII;typedef pair PDD;const int INF = INT_MAX / 3;const double eps = 1e-8;const LL LINF = 1e17;const double DINF = 1e60;const int maxn = 65;int N, M, x;struct Matrix { int n, m; LL data[maxn][maxn]; Matrix(int n = 0, int m = 0): n(n), m(m) { memset(data, 0, sizeof(data)); } void print() { for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cout << data[i][j] << " "; } cout << endl; } }};Matrix operator * (Matrix a, Matrix b) { Matrix ret(a.n, b.m); for(int i = 1; i <= a.n; i++) { for(int j = 1; j <= b.m; j++) { for(int k = 1; k <= a.m; k++) { ret.data[i][j] += a.data[i][k] * b.data[k][j]; ret.data[i][j] %= M; } } } return ret;}Matrix pow(Matrix val, LL p) { Matrix ret(val.n, val.m); for(int i = 1; i <= val.n; i++) ret.data[i][i] = 1; while(p) { if(p & 1) ret = ret * val; val = val * val; p >>= 1; } return ret;}int main() { while(cin >> N >> x >> M) { if(N < 0) break; Matrix A0(x + 2, 1), A(x + 2, x + 2); for(int i = 1; i <= x + 1; i++) A0.data[i][1] = x; A.data[x + 1][1] = 0; A.data[1][1] = x; for(int i = 2; i <= x + 1; i++) { for(int j = 1; j <= i; j++) { A.data[i][j] = (A.data[i - 1][j] + A.data[i - 1][j - 1]) % M; } } A.data[x + 2][x + 1] = A.data[x + 2][x + 2] = 1; A0 = pow(A, N) * A0; cout << A0.data[x + 2][1] << endl; } return 0;}
转载于:https://www.cnblogs.com/rolight/p/4056050.html