欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU4990 Reading comprehension【矩阵快速幂】

程序员文章站 2022-07-12 09:42:17
...

题意:偶数项f[i] = 2f[i-1],奇数项f[i] = 2f[i-1]+1


思路:f[i] = f[i-1] + 2f[i-2] + 1 直接一个公式,矩阵快速幂

开始我没有发现这个通项公式,我看到的是偶数项f[i] = 4f[i-2] + 2,快速幂偶数项,奇数项f[i] = f[i+1] / 2,好像有点道理,但是
仔细想想这里可是取模的。
没事瞎搞什么除法,奇数项f[i] = 4f[i-2] + 1 奇推偶 乘2 是不挺好的

告诉我们一个道理:除法不是好东西,尽量避免!


直接一个公式的

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<list>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
#include<numeric>
#include<functional>
using namespace std;
typedef long long ll;
const int maxn = 105;

ll MOD,a[maxn];
int N;
struct data
{
	ll s[maxn][maxn];
}res,tp;

void init()
{
	memset(res.s,0,sizeof res.s);
	memset(tp.s,0,sizeof tp.s);
	for(int i = 1; i <= N; i++)
		res.s[i][i] = 1;
	tp.s[1][1] = 1;tp.s[1][2] = 2;tp.s[1][3] = 1;
	tp.s[2][1] = 1;
	tp.s[3][3] = 1;
	/*for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <= N; j++)
			printf("%d%c",tp.s[i][j],j == N?'\n':' ');
	}*/
}

struct data mat(struct data &x,struct data &y)
{
	struct data temp;
	memset(temp.s,0,sizeof temp.s);
	for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <= N; j++)
		{
			for(int k = 1; k <= N; k++)
			{
				temp.s[i][j] += x.s[i][k] * y.s[k][j];
				temp.s[i][j] %= MOD;
			}
		}
	}
	return temp;
}

int main(void)
{
	ll n,m;
	while(scanf("%I64d%I64d",&n,&m)!=EOF)
	{
		MOD = m;
		N = 3;
		a[1] = 1;
		a[2] = 0;
		a[3] = 1;
		init();
		ll temp = n;
		temp--;
		while(temp)
		{
			if(temp&1) res = mat(res,tp);
			temp >>= 1;
			tp = mat(tp,tp); 
		}
		ll ans = 0;
		for(int i = 1; i <= N; i++)
		{
			ans += res.s[1][i] * a[i];
			ans %= MOD;
		}
		ans = ( (ans%MOD)+MOD ) % MOD;
		printf("%I64d\n",ans);
	}
	return 0;
}

快速幂奇数项,推偶数项

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<list>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
#include<numeric>
#include<functional>
using namespace std;
typedef long long ll;
const int maxn = 105;

ll MOD,a[maxn];
int N;
struct data
{
	ll s[maxn][maxn];
}res,tp;

void init()
{
	memset(res.s,0,sizeof res.s);
	memset(tp.s,0,sizeof tp.s);
	for(int i = 1; i <= N; i++)
		res.s[i][i] = 1;
	tp.s[1][1] = 4;tp.s[1][2] = 1;
	tp.s[2][1] = 0;tp.s[2][2] = 1;
	/*for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <= N; j++)
			printf("%d%c",tp.s[i][j],j == N?'\n':' ');
	}*/
}

struct data mat(struct data &x,struct data &y)
{
	struct data temp;
	memset(temp.s,0,sizeof temp.s);
	for(int i = 1; i <= N; i++)
	{
		for(int j = 1; j <= N; j++)
		{
			for(int k = 1; k <= N; k++)
			{
				temp.s[i][j] += x.s[i][k] * y.s[k][j] % MOD;
				temp.s[i][j] %= MOD;
			}
		}
	}
	return temp;
}

int main(void)
{
	ll n,m;
	while(scanf("%I64d%I64d",&n,&m)!=EOF)
	{
		MOD = m;
		N = 2;
		a[1] = 0;
		a[2] = 1;
		init();
		ll temp = n;
		temp = (temp+1) / 2;                                                           
		while(temp)
		{
			if(temp&1) res = mat(res,tp);
			temp >>= 1;
			tp = mat(tp,tp); 
		}
		ll ans = 0;
		for(int i = 1; i <= N; i++)
		{
			ans += res.s[1][i] * a[i] % MOD;
			ans %= MOD;
		}
		if(n%2 == 0)
			ans *= 2;
		ans = ( (ans%MOD)+MOD ) % MOD;
		printf("%I64d\n",ans);
	}
	return 0;
}