`
digiter
  • 浏览: 120724 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

hdu 3509

    博客分类:
  • ICPC
阅读更多
推导公式的题目,矩阵幂关键就在于构造系数矩阵
备忘:
S(n, k) - S(n - 1, k) = Fn ^ k
当Fn能够线性表示的时候,S(n, k) = S(n - 1, k) + Fn ^ k 不也是线性表示嘛!

Fn ^ k = sigma( C(k, i) * a^i * b^(k-i) * Fn-1^i * Fn-2^(k-i) ) 其中0 <= i <= k

备忘2:
构造矩阵系数的时候,要用 += 把相应的项的系数加上去,而不是直接 =

备忘3:
快速幂的复杂度很低,所以基本不用考虑常数

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v << ": " << (v) << endl
using namespace std;
typedef long long LL;

LL f1[52], f2[52], a[52], b[52], k, n, m;

LL C[52][52];
void make1() {
	C[0][0] = 1;
	for (int i = 1; i <= 50; ++i) {
		C[i][0] = C[i][i] = 1;
		for (int j = 1; j < i; ++j)
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % m;
	}
	a[0] = 1;
	for (int i = 2; i <= 50; ++i) a[i] = (a[i - 1] * a[1]) % m;
	b[0] = 1;
	for (int i = 2; i <= 50; ++i) b[i] = (b[i - 1] * b[1]) % m;
	f1[0] = 1;
	for (int i = 2; i <= 50; ++i) f1[i] = (f1[i - 1] * f1[1]) % m;
	f2[0] = 1;
	for (int i = 2; i <= 50; ++i) f2[i] = (f2[i - 1] * f2[1]) % m;
}

typedef LL matrix[52][52];
void copy(int size, matrix X, matrix Y) {
	for (int i = 0; i < size; ++i)
		for (int j = 0; j < size; ++j)
			Y[i][j] = X[i][j];
}
void mutiply(int size, matrix _X, matrix _Y, matrix Z) {
	matrix X, Y;
	copy(size, _X, X); copy(size, _Y, Y);
	for (int i = 0; i < size; ++i)
		for (int j = 0; j < size; ++j) {
			Z[i][j] = 0;
			for (int k = 0; k < size; ++k)
				Z[i][j] = (Z[i][j] + X[i][k] * Y[k][j]) % m;
		}
}
void ident(int size, matrix X) {
	for (int i = 0; i < size; ++i)
		for (int j = 0; j < size; ++j)
			X[i][j] = (i == j ? 1 : 0);
}
void power(int size, matrix _X, LL n, matrix Y)
{
	ident(size, Y);
	matrix X; copy(size, _X, X);
	while (n) {
		if (n & 1) mutiply(size, Y, X, Y);
		n >>= 1;
		if (n) mutiply(size, X, X, X);
	}
}
void print(int size, matrix X) {
	for (int i = 0; i < size; ++i) { 
		for (int j = 0; j < size; ++j)
			cout << X[i][j] << " ";
		cout << endl;
	}
}
void clear(int size, matrix X) {
	for (int i = 0; i < size; ++i)
		for (int j = 0; j < size; ++j)
			X[i][j] = 0;
}

matrix A;
void make2() {
	clear(k + 2, A);
	for (int i = 0; i <= k; ++i)
		for (int j = 0; j <= i; ++j)
			A[i][k - (i - j)] = (A[i][k - (i - j)] + C[i][j] * a[j] % m * b[i - j]) % m;
	for (int j = 0; j <= k; ++j)
		A[k + 1][j] = (A[k + 1][j] + C[k][j] * a[j] % m * b[k - j]) % m;
	A[k + 1][k + 1] = 1;
	
	//cout << "A" << endl; print(k + 2, A);
}

int main()
{
	int T;
	cin >> T;
	while (T--) {
		cin >> f1[1] >> f2[1] >> a[1] >> b[1] >> k >> n >> m;
		make1();
		make2();
		if (n == 1) {
			cout << f1[k] % m << endl;
			continue;
		} else if (n == 2) {
			cout << (f1[k] + f2[k]) % m << endl;
			continue;
		}
		
		LL p[52];
		for (int i = 0; i <= k; ++i)
			p[i] = f2[i] * f1[k - i] % m;
		p[k + 1] = (f2[k] + f1[k]) % m;
		matrix D;
		power(k + 2, A, n - 2, D);
		//cout << "D" << endl; print(k + 2, D);
		LL ans = 0;
		for (int j = 0; j <= k + 1; ++j)
			ans = (ans + D[k + 1][j] * p[j] % m) % m;
		cout << ans << endl;
	}
	return 0;
}
分享到:
评论

相关推荐

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    HDU DP动态规划

    【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    hdu2101解决方案

    hdu2101AC代码

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu.

    【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...

    Hdu1000—2169部分代码

    HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    HDU acm-PPT课件

    【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...

    hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084

    【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...

    HDU最全ac代码

    HDU(Hangzhou Dianzi University)是国内外知名的在线编程竞赛平台,主要服务于ACM/ICPC(国际大学生程序设计竞赛)以及相关的算法训练。"HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码...

    hdu动态规划算法集锦

    根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...

Global site tag (gtag.js) - Google Analytics