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;
}