---

<font color = red , size = '4'>下列图表转载自 efreet

链接：传送门

题意：给出递推关系，求 f(k) % m 的值，

思路：

• 因为 k<2 * 10^9 , m < 10^5，O(n)算法应该是T掉了，当 k >= 10 时 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10)，可以理解为这是两个行列是乘积的值，经下面分析可知用矩阵快速幂可搞

• 下列三个表分别命名为矩阵0，矩阵1，矩阵2。

- 经过观察发现，当 k >= 10 时 f(k) = [ 矩阵1 ]^(k-9) * [ 矩阵2 ]

---

/*************************************************************************

    > File Name: hdu1757.cpp

    > Author:    WArobot

    > Blog:      http://www.cnblogs.com/WArobot/

    > Created Time: 2017年05月02日 星期二 19时25分30秒

 ************************************************************************/

#include<bits/stdc++.h>

using namespace std;

const int maxn = 11;

int MOD;

#define ll long long

#define mod(x) ((x)%MOD)

struct mat{

	int m[maxn][maxn];

}unit;

int n;

mat operator * (mat a,mat b){

	mat ret;

	ll x;

	for(int i=0;i<10;i++){

		for(int j=0;j<10;j++){

			x = 0;

			for(int k=0;k<10;k++)

				x += mod( (ll)a.m[i][k]*b.m[k][j] );

			ret.m[i][j] = mod(x);

		}

	}

	return ret;

}

// 初始化单位阵

void init_unit(){

	for(int i=0;i<10;i++)

		unit.m[i][i] = 1;

	return;

}

mat pow_mat(mat a,ll x){

	mat ret = unit;

	while(x){

		if(x&1)	ret = ret*a;

		a = a*a;

		x >>= 1;

	}

	return ret;

}

int main(){

	mat a , f;

	int aa[10];

	ll  k;

	init_unit();

	memset(f.m,0,sizeof(f.m));

	for(int i=0;i<10;i++)	f.m[i][0] = 9-i;

	while(cin>>k>>MOD){

		for(int i=0;i<10;i++)	cin>>aa[i];

		if(k<10)	printf("%lld\n",k);

		else{

			// 构建a矩阵

			for(int j=0;j<10;j++)	a.m[0][j] = aa[j];

			for(int i=1;i<10;i++){

				for(int j=0;j<10;j++){

					if(j+1==i)	a.m[i][j] = 1;

					else		a.m[i][j] = 0;

				}

			}

			mat ans = pow_mat(a,k-9);

			ans = ans*f;

			printf("%d\n",ans.m[0][0]%MOD);

		}

	}

	return 0;

}

最新文章

1. VC 鼠标滚轮事件控制绘图的问题
2. ORA-12899: value too large for column (actual: 27, maximum: 20)
3. JavaScript中对象的比较
4. OD调试篇10
5. history介绍及bash命令快速调用
6. 【BZOJ】2321: [BeiJing2011集训]星器（数学+特殊的技巧）
7. Java框架的思考
8. 关于Python中的设计模式
9. 【随手记-有空整理】使用PHPMailer和QQ邮箱实现邮件的自动发送
10. 理解free命令
11. Windows的文件权限 研究笔记
12. href的理解
13. git在本地向远程仓库创建分支
14. hover效果的几种方式
15. MYSQL 获取当前星期方法
16. 第三节：工厂+反射+配置文件(手写IOC)对缓存进行管理。
17. 如何找到Firefox的收藏夹,就像IE一样,出现在网页的侧面
18. Json循环引用问题
19. 实现一个简单的虚拟demo算法
20. Android中利用C++处理Bitmap对象

热门文章

1. 【BZOJ1125】【POI2008】poc - splay+哈希
2. 《代码敲不队》第八次团队作业：Alpha冲刺 第二天
3. js cookie 设置
4. telnet允许root用户登录
5. 计算机网络系统--常用DOS命令
6. WinSCP介绍、安装、使用
7. POJ 1948
8. exFAT格式
9. struts2提交多个对象带图片
10. HTML5 格式化方式以及应用