NKOJ 4385 简单计算（矩阵乘法）

发表于 |
字数统计: 425字 | 阅读时长 ≈ 2min

P4385简单计算

问题描述

给你三个整数 N, x, 和 M, 计算$\sum_{k=1}^{N}k^xx^k$

输入格式

一行，三个整数N, x, 和 M,

输出格式

一行，一个整数，表示计算结果

样例输入 1

100 1 10000

样例输出 1

5050

样例输入 2

3 4 1000

样例输出 2

444

提示

1 ≤ N, M ≤ 2*10^9
1 ≤ x ≤ 50.

注意到x很小，因此对$k^x$二项式展开，考虑推到$(k+1)^x$，显然发现可以利用矩阵乘法进行递推。至于$x^k$，只需要将构造的矩阵中每个数都乘上$x$即可。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll n,m,p,A[60][60],ans[60][60];
void C(ll x[60][60],ll y[60][60])
{
	ll z[60][60],i,j,k;
	memset(z,0,sizeof(z));
	for(i=0;i<=m+1;i++)
	for(j=0;j<=m+1;j++)
	for(k=0;k<=m+1;k++)z[i][j]=(z[i][j]+x[i][k]*y[k][j]%p)%p;
	memcpy(x,z,sizeof(z));
}
void KSM(ll b)
{
	int i;
	for(i=0;i<=m+1;i++)ans[i][i]=1;
	while(b)
	{
		if(b&1)C(ans,A);
		b>>=1;C(A,A);
	}
	memset(A,0,sizeof(A));
	for(i=0;i<=m;i++)A[0][i]=m;
	C(A,ans);
	printf("%lld",A[0][m+1]);
}
int main()
{
	int i,j,k;
	scanf("%lld%lld%lld",&n,&m,&p);
	for(i=0;i<=m;i++)A[0][i]=1;
	for(i=1;i<=m;i++)
	for(j=1;j<=i;j++)A[j][i]=(A[j-1][i-1]+A[j][i-1])%p;
	for(i=0;i<=m;i++)
	for(j=0;j<=i;j++)A[j][i]=A[j][i]*m%p;
	A[m][m+1]=A[m+1][m+1]=1;
	KSM(n);
}