【Hdu1588】Gauss Fibonacci

Source and Judge

DYGG
HDU “Valentines Day” Open Programming Contest 2007-02-14
Hdu1588
Caioj1488

Problem

【Brief description】
g[i]=k*i+b。
f[0]=0,f[1]=1,f[i]=f[i-1]+f[i-2] (i>=2)
求f[ g[0] ]+f[ g[1] ]+…+f[ g[n-1] ]的值,结果需要mod M
【Input】
多组数据
四个整数k,b,n,M
【Output】
每行一个答案
【Limited conditions】
每个数不超过1,000,000,000.
【Sample input】
2 1 4 100
2 0 4 100
【Sample output】
21
12
【Sample explanation】

Record

30min

Analysis

请先思考后再展开

那个。。推公式的时候注意矩阵乘法操作顺序不可调转
$$
f[b]+f[k+b]+f[2\times k+b]…+f[(n-1)\times k+b]
$$
转化为矩阵A(通常计算斐波拉契的递推矩阵,自己推)
$$
A^b\times f[0]+A^{k+b}\times f[0]…+A^{(n-1)\times k+b}\times f[0]
$$
提取公因式$A^b\times f[0]$
$$
( A^0+A^k…+A^{(n-1)\times k} )\times A^b\times f[0]
$$
令$B=A^k$
$$
( B^0+ B^1…+B^{n-1} )\times A^b\times f[0]
$$
于是就变成了一个等比数列求和问题了

Code

请先思考后再展开
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//*******************主函数******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
//*******************全局常量****************
//*******************全局定义****************
struct martix
{
int row,col;
ll m[5][5];
martix()
{
memset(m,0,sizeof(m));
}
};
ll MOD;
//*******************实现******************
martix jia(martix a,martix b)
{
martix c;
c.row=a.row;c.col=a.col;
for(int i=1;i<=c.row;i++)
for(int j=1;j<=c.col;j++)
(c.m[i][j]+=a.m[i][j]+b.m[i][j])%=MOD;
return c;
}
martix cheng(martix a,martix b)
{
martix c;
int n=a.row,m=a.col,p=b.col;
c.row=n;c.col=p;
for(int i=1;i<=n;i++)
for(int j=1;j<=p;j++)
for(int k=1;k<=m;k++)
(c.m[i][j]+=a.m[i][k]*b.m[k][j])%=MOD;
return c;
}
martix pre()
{
martix c;c.row=c.col=2;
c.m[1][1]=c.m[2][2]=1;
return c;
}
martix power(martix a,int e)
{
martix ans=pre();
while(e>0)
{
if(e&1) ans=cheng(ans,a);
a=cheng(a,a);e>>=1;
}
return ans;
}
martix B;
martix sum(int k)
{
if(k==1) return B;
if(k&1) return jia(sum(k-1),power(B,k));
martix t=sum(k/2);
return jia( cheng(t,power(B,k/2)),t );
}
//*******************主函数******************
int main()
{
martix A;A.row=A.col=2;A.m[1][2]=A.m[2][1]=A.m[2][2]=1;
martix f0;f0.row=2;f0.col=1;f0.m[2][1]=1;
int k,b,n;
while(scanf("%d%d%d%lld",&k,&b,&n,&MOD)!=EOF)
{
B=power(A,k);
printf("%lld\n",cheng( jia(sum(n-1),pre()),cheng(power(A,b),f0) ).m[1][1]);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/7e2f.html
转载请注明出处,谢谢!