题目大意：
F(1)=A， F(2)=B, F(i)=C*F(i-2)+D*F(i-1)+p/i(向下取整)
给定A B C D p n
求F(n)
构造
矩阵A * 矩阵B = 矩阵C
┌ F(n-2) F(n-1) 1 ┐ ┌ 0 C 0 ┐ ┌ F(n-1) F(n) 1 ┐
| 0 0 0 | * | 1 D 0 | = | 0 0 0 |
└ 0 0 0 ┘ └ 0 p/i 1 ┘ └ 0 0 0 ┘
那么当A为第一项时 A*(B^n)=第n项
因为p/i向下取整所以在 1~n的范围中 p/i的数值是多段相等的
如n=10 p=15 那么1~n中 p/i为 15 7 5 3 3 2 2 1 1 1
改变B中的p/i 分别求B^len 即 B^1 B^1 B^1 B^2 B^2 B^3
已知 p / i = x 那么len = min( p / ( p / i ) , n ) 都是int型向下取整
就得到了分块的 B^n
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define LLINF 0x3f3f3f3f3f3f3f3f3f #define LL long long #define mem(i,j) memset(i,j,sizeof(i)) const int N=3; const int mod=1e9+7; LL A,B,C,D,p,n; struct MAT { LL a[N][N]; MAT(){ mem(a,0); } MAT operator*(MAT p) { MAT res; for(int i=0;i<N;i++) for(int j=0;j<N;j++) for(int k=0;k<N;k++) res.a[i][j]=(res.a[i][j]+a[i][k]*p.a[k][j])%mod; return res; } }Ans,Pow; MAT mod_pow(MAT A,int x) { MAT res; res.a[0][0]=res.a[1][1]=res.a[2][2]=1; while(x) { if(x&1) res=res*A; A=A*A; x>>=1; } return res; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%lld%lld%lld%lld%lld%lld",&A,&B,&C,&D,&p,&n); Ans.a[0][0]=A, Ans.a[0][1]=B, Ans.a[0][2]=1; Pow.a[1][0]=Pow.a[2][2]=1; Pow.a[0][1]=C, Pow.a[1][1]=D; for(int x=3,px;x<=n;x=px+1) { px= p/x ? min(p/(p/x),n):n; Pow.a[2][1]=p/x; MAT t=mod_pow(Pow,px-x+1); // x~px的值都为p/x Ans=Ans*t; } printf("%lld\n",Ans.a[0][1]); } return 0; } View Code
转载于:https://www.cnblogs.com/zquzjx/p/10360768.html
