首页 > 代码库 > hdu 1588 Gauss Fibonacci(等比矩阵二分求和)

hdu 1588 Gauss Fibonacci(等比矩阵二分求和)

2024-09-04 16:40:12   221人阅读

题目链接：hdu 1588 Gauss Fibonacci

题意：

g(i)=k*i+b;

f(0)=0
f(1)=1
f(n)=f(n-1)+f(n-2) (n>=2)

让你求：sum(f(g(i)))for 0<=i<n

题解:

  1. S(g(i))
  2. = F(b) + F(b+k) + F(b+2k) + .... + F(b+nk)
  3. // 设 A = {1,1,0,1}, （花括号表示矩阵...）
  4. // 也就是fib数的变化矩阵，F(x) = (A^x) * {1,0}
  5. = F(b) + (A^k)F(b) + (A^2k)F(b)+….+(A^nk)F(b)
  6. // 提取公因式 F(b)
  7. = F(b) [ E +A^k + A^2k + ….+ A^nk] // (E表示的是单位矩阵)
  9. // 令 K = A^k 后
  10. E +A^k + A^2k + ….+ A^nk 变成 K^0+K^1+K^2+…+K^n

这里用到二分等比求和

技术分享 
 1 #include<bits/stdc++.h>
 2 #define mst(a,b) memset(a,b,sizeof(a))
 3 #define F(i,a,b) for(int i=a;i<=b;++i)
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 const int mat_N=2;
 8 int mo;
 9 struct mat{
10     ll c[mat_N][mat_N];
11     void init(){mst(c,0);}
12     mat operator*(mat b){
13         mat M;int N=mat_N-1;M.init();
14         F(i,0,N)F(j,0,N)F(k,0,N)M.c[i][k]=(M.c[i][k]+c[i][j]*b.c[j][k])%mo;
15         return M;
16     }
17     mat operator+(mat b){
18         mat M;int N=mat_N-1;
19         F(i,0,N)F(j,0,N)M.c[i][j]=(c[i][j]+b.c[i][j])%mo;
20         return M;
21     }
22     mat operator^(ll k){
23         mat ans,M=(*this);int N=mat_N-1;ans.init();
24         F(i,0,N)ans.c[i][i]=1;
25         while(k){if(k&1)ans=ans*M;k>>=1,M=M*M;}
26         return ans;
27     }
28 }A,B,C,E;
29 
30 // 等比二分求和(a+a^2+a^3+...+a^n)
31 mat calc(mat a, int n) {  
32     if (n==1)return a;  
33     if (n&1)return (a^n)+calc(a,n-1);  
34     return calc(a, n/2)*((a^(n/2))+E);  
35 } 
36 
37 int k,b,n;
38 
39 int main()
40 {
41     A=(mat){1,1,1,0};
42     E=(mat){1,0,0,1};
43     while(~scanf("%d%d%d%d",&k,&b,&n,&mo))
44     {
45         B=A^k;
46         C=calc(B,n-1)+(A^0);
47         C=(A^b)*C;
48         printf("%lld\n",C.c[0][1]);
49     }
50     return 0;
51 }
View Code

 

hdu 1588 Gauss Fibonacci(等比矩阵二分求和)


联系
我们